HackMD
Collections in IB Computer Science
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Collections in IB book are explained a little bit messy. You can go from page 256 onwards.
Collections in PSEUDOCODE are an abstract of other "iterables" from other programming languages
Other iterables like lists, linkedlists, Calendars, Queues, Stacks, Binary trees.
For example in Java these are the UML diagram of collections. You can never have an instance of a collection but you can have an instance of an ArrayList that is an AbstractList, that is a List and an Abstract Collection and is a Collection and all of them are Iterables
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
The specifics of those collections are for HL but they share some stuff. In this case that we can iterate through them and that accessing to one specific element is not that fast.
In the case of the abstract (more high level) definition of the collection we're going to have some values and to access them we need to use a cursor.
Functions of a collection
You need to know and use these functions of a collection.
getNext()
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
That cursor is going to move (we don't need to know how) through the collection every time that we call the function "getNext()" and "getNext()" function is going to return the value that it was stored.
Example:
TREES //collection of tree names
output TREE.getNext() //outupts the next name that we have. For example "mapletree"
output TREE.getNext() //outputs the next name after mapletree". For example, "pine"
Each time that we call getNext() we are going to have the next element. So if we want to do something with it we should keep it in a variable.
HasNext()
To know if we have finished with the collection we can access to a function that is going to return a boolean that will return false in the case that we have finished the collection and true otherwise. That function is called "hasNext()"
Example:
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
If we have a TABLE collection and we call hasNext() is going to return true because we have still 2 more elements until the end of the collection.
resetNext()
Then to reset the cursor to the "first" position we call the function resetNext() that is a function that is not going to return nothing but it's going to make sure that the cursor is in the "first" position.
How to get the first item on the colection
If we have a collection of NIKESNEAKERS and we want to output just the first one this would be the code:
NIKESNEAKERS.resetNext()
output(NIKESNEAKERS.getNext())
They don't usually ask this kind of specific things of "give me the first 3 or last 5 elements", they usually go with all the collection.
addItem()
Finally to add a new item (a new value) we use "addItem()" sending the value that we want to add.
To write them we need to write the name of the collection (usually in Upper case), a dot and the name of the method. An example would be POTATOES.addItem(POTATO)
Example:
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
We're working on a sushi restaurant webpage and they have all the sushi dishes in a collection called DISHES.
We can start by outputting all of them. This is iterating through a collection. Pretty similar and standar if you know how to iterate through an array.
DISHES //collection
DISHES.resetNext()
loop while DISHES.hasNext()
output DISHES.getNext()
end loop
Another example
Let's do an iteration through a collection of STUDENTS. Let's output the name of the students that are inside the collection.
STUDENTS // collection
STUDENTS.resetNext()
loop while STUDENTS.hasNext()
output STUDENTS.getNext()
end loop
The importance of resetNext()
Why the resetNext()? It's not stricly necessary in terms of IB but is a good measure. Imagine that we want to iterate the Dishes twice. Once to output the values and the other that is going to call a function called translate to translate the dishes to the prefered language. If we don't use resetNext, when we finish the first loop the second one is not going to do nothing since hasNext is going to be false
DISHES //collection
loop while DISHES.hasNext() //This should work
output DISHES.getNext()
end loop
loop while DISHES.hasNext() //this doesn't work
output translate(DISHES.getNext(), Mandarin)
end loop
To solve that we reset the cursor using DISHES.resetNext()
DISHES //collection
DISHES.resetNext()
loop while DISHES.hasNext() //this works for sure
output DISHES.getNext()
end loop
DISHES.resetNext()
loop while DISHES.hasNext() //this works for sure
output translate(DISHES.getNext(), Mandarin)
end loop
In actual programming you probably are not going to be sure to know if this method has been called already so is a good safety measure to use it just before any loop through the collection.
Let's see if we want to count how many dishes are nigiris. We know that if a dish is a nigiri it will contain the string "nigiri".
For example, "tuna nigiri", "salmon nigiri", "shrimp nigiri".
For checking it out we can use the function containsSubstring(string s) that is going to return true if the string s is cointained in the string that is calling it.
Example
WORD = "chair"
WORD2 = "chicken"
WORD.containsSubstring("ch") // returns true
WORD.containsSubstring("airs") // returns false
WORD2.containsSubstring("ch") //returns true
WORD2.containsSubstring("chicken") //true
WORD3 = "roasted chicken"
WORD3.containsSubstring(WORD2) //true
WORD3.containsSubstring("potato") //false
It's common in the IB exam that they gave you the instructions of how a function works and they ask you to use it, like in this case containsSubstring().
To count how many nigiris we have we need to check if that word contains "nigiri". So let's do it. Remember that we want to output how many nigiris we have.
DISHES //collection
DISHES.resetNext()
COUNT = 0
loop while DISHES.hasNext()
if(DISHES.getNext().containsSubstring("nigiri")) then
COUNT = COUNT + 1
end if
end loop
output COUNT
Now the tricky part. We want to count how many nigiris or makis we have in the menu (and output them).
DISHES //collection
DISHES.resetNext()
COUNT = 0
loop while DISHES.hasNext()
CURRENTDISH = DISHES.getNext()
if(CURRENTDISH.containsSubstring("nigiri") OR CURRENTDISH.containsSubstring("maki")) then
COUNT = COUNT + 1
end if
end loop
output COUNT
We need to store the getNext value in a variable.
Rule of thumb: if you have an iteration and inside the loop you call getNext() twice or more times, you're probably doing it wrong (unless you're comparing pairs but it's unlikely). Use the temporary variable.
If you don't remember because you're stuck how to write the temporary variable you can do 2 loops.
DISHES //collection
DISHES.resetNext()
COUNT = 0
loop while DISHES.hasNext()
if(DISHES.getNext().containsSubstring("nigiri") then
COUNT = COUNT + 1
end if
end loop
DISHES.resetNext()
loop while DISHES.hasNext()
if(DISHES.getNext().containsSubstring("maki") then
COUNT = COUNT + 1
end if
end loop
output COUNT
I suggest to store the value from getNext even if it's going to be used once for safety. So the first counting (of only the nigiris) I'd write in an exam like this:
DISHES //collection
DISHES.resetNext()
COUNT = 0
loop while DISHES.hasNext()
CURRENT_DISH = DISHES.getNext()
if(CURRENT_DISH.containsSubstring("nigiri")) then
COUNT = COUNT + 1
end if
end loop
output COUNT
Continuing the example with STUDENTS
Let's say that we want to output how many students have their name that starts with J, L or M, using the method "startsWith()"
First attempt is wrong:
STUDENTS.resetNext()
C = 0
loop while STUDENTS.hasNext()
if STUDENTS.getNext().startsWith("L") or .startsWith("M") or .startsWith("J") then
C = C +1
end if
end loop
output C
Second attempt is also wrong
STUDENTS.resetNext()
C = 0
loop while STUDENTS.hasNext()
if STUDENTS.getNext().startsWith("L")
or STUDENTS.getNext().startsWith("M")
or STUDENTS.getNext().startsWith("J") then
C = C +1
end if
end loop
output C
Third attempt is the correct one
STUDENTS.resetNext()
C = 0
loop while STUDENTS.hasNext()
CURRENTSTUDENT = STUDENTS.getNext()
if CURRENTSTUDENT.startsWith("L")
or CURRENTSTUDENT.startsWith("M")
or CURRENTSTUDENT.startsWith("J") then
C = C +1
end if
end loop
output C
Exercise with students
Count how many people have a name that starts with L and ends with O
use startsWith and endsWith
Exercise
We have a collection with the names of all of our employees called NAMES.
We want to know how many of them are called "Alexei" and how many of them are called "Alexander". We want to know which name is more common.
Posible
Two loops version
NAMES //collection
ALEXEIS = 0
ALEXANDERS = 0
NAMES.resetNext()
loop while NAMES.hasNext()
if names.getNext() = "Alexei" then
ALEXEIS = ALEXEIS +1
end if
end loop
NAMES.resetNext()
loop while NAMES.hasNext()
if names.getNext() = "Alexander" then
ALEXANDERS = ALEXANDERS +1
end if
end loop
if ALEXANDERS > ALEXEIS then
output "there are more Alexanders than Alexeis"
else if ALEXANDERS = ALEXEIS then
output "there are the same number of Alexanders and Alexeis"
else
output "there are more Alexeis than Alexanders"
end if
One loop version
NAMES //collection
ALEXEIS = 0
ALEXANDERS = 0
NAMES.resetNext()
loop while NAMES.hasNext()
NAME = NAMES.getNext()
if NAME = "Alexei" then
ALEXEIS = ALEXEIS +1
else if NAME = "Alexander" then
ALEXANDERS = ALEXANDERS +1
end if
end loop
if ALEXANDERS > ALEXEIS then
output "there are more Alexanders than Alexeis"
else if ALEXANDERS = ALEXEIS then
output "there are the same number of Alexanders and Alexeis"
else
output "there are more Alexeis than Alexanders"
end if
Another one loop version courtesy of K.B
ALEXEI=0
ALEXANDER=0
NAMES.resetNext()
current=NAMES.getNext()
loop while current.hasNext()
if current= "Alexander" then
alexander= ALEXANDER +1
end if
if current= "Alexei" then
ALEXEI= ALEXEI+1
end if
current=current.getNext()
end loop
if ALEXANDER>ALEXEI then
output "Alexander is more common"
end if
if ALEXEI>ALEXANDER then
output "ALEXEI is more common"
end if
if ALEXEI=ALEXANDER then
output "equally common"
end if
Exercise similar to an exam: wizards club
(last pages of the document I submitted in teams in January 2024, 27 to be precise)
Howgarts (not the magic school, the other magic school) offers diffent wizards clubs for their students. Each student must choose one of these clubs (it's mandatory)
These are the 5 collections where we're storing the wizards IDs. When a wizard student joins in, a troll adds it's ID to the collection.
PotionsAndExplotions
SetupWizards
Tennis
SpellingSpells
AncientForbiddenLanguagesAndLatin
For example this could be the content of the Collections at a certain given time
PotionsAndExplotions = {122504,5524,65521,58756,36652}
SetupWizards = {9996545,6654,2235,8887,555}
Tennis = {2555,366668}
SpellingSpells = { 1525456,22589,2114,6995,2255,22236,222578,1112}
AncientForbiddenLanguagesAndLatin = {659979,2164654,22247,23368,47798,5554}
The method isIn(X, COL) is available where
- X is an integer representing an ID number
- COL is a collection that holds student ID numbers
This method will return true if the ID number X is inside the collection COL and false otherwise.
For example
isIn(22589,SpellingSpells) returns true
isIn(6654, Tennis) returns false
Exercise 1. Implement a method
Construct a method to implement isIn(X, COL)
Remember that we don't need to do for each specific club. Because we're going to have that specific club sent as a parameter.
Remember also that this is a collection. Not an array.
isIn (X, COL) //here we have to define the subprogram/function that will end in a "end method" line.
COL.resetNext()
loop while COL.hasNext()
CURRENT_ID = COL.getNext()
if CURRENT_ID = X then
return TRUE
end if
end loop
return FALSE // this return FALSE has to be OUTSIDE the loop
end method
Other variations would be these
isIn (X, COL) //here we have to define the subprogram/function that will end in a "end method" line.
PRESENT = False //this is a flag variable
COL.resetNext()
loop while COL.hasNext() AND NOT PRESENT
CURRENT_ID = COL.getNext()
if CURRENT_ID = X then
PRESENT = TRUE
end if
end loop
return PRESENT // this return FALSE has to be OUTSIDE the loop
end isIn
isIn (X, COL) //here we have to define the subprogram/function that will end in a "end method" line.
PRESENT = 0 //this is a flag variable but with a number
COL.resetNext()
loop while COL.hasNext() AND NOT PRESENT
CURRENT_ID = COL.getNext()
if CURRENT_ID = X then
PRESENT = 1
end if
end loop
if PRESENT == 1 then
return True
else
return False
end if
end isIn
Remember that this part is about defining the function, not using it. That's why it starts with the name of the method and ends with the end method or end isIn. It's like when we're implemnting the 4 lines of void dot or dash
Second part of the Exercise. Using a function that recieves a full collection
Next part of the exercise ask that it happens that some of the meetings of PotionsAndExplotions happens at the same time that SetupWizards and we have to construct a code that is going to tell how many of them are in both clubs so measures can be taken. (PotionsAndExplotions is expected to have preference but this is about internal school politics). Use the function isIn described before (in the exam they tell you that you need to use that function)
Solution:
The description of this algorithm is
We set up a counter to 0
Loop through the collection A, for each element in collection A check with isIn and collection B. If that returns true, then we upldate the counter adding 1. Else we keep looking through the collection A. When the loop is done we output the counter.
PotionsAndExplosions //collection
SetupWizards // collection
COUNTER = 0
SetupWizards.resetNext()
while SetupWizards.hasNext()
ID = SetupWizards.getNext()
if isIn(ID, PotionsAndExplosions) then
COUNTER = COUNTER +1
end if
end loop
output COUNTER
We can use the other collection also, here is another solution
Credit Y.C
Another variation is to count how many students are in Tennis, SpellingSpells and AncientForbiddenLanguagesAndLatin. In this case we need to use either a nested if solution or a composed statement because we want to know who are in the three of them at the same time.
Solution
Composite condition sollution
COUNTER = 0
AncientForbiddenLanguagesAndLatin.resetNext()
loop while AncientForbiddenLanguagesAndLatin.hasNext()
ID = AncientForbiddenLanguagesAndLatin.getNext()
if isIn(ID, Tennis) and isIn(ID, Spellingspells) then
COUNTER = COUNTER +1
end if
end loop
output COUNTER
Nested if solution (the name of the long collection is wrong but you get it)
Credit Y.C
Third part of the exercise. Now with parallel arrays.
The academic director Magdalena MacGeneral wants to see if there is any student that has not chosen yet any of the clubs.
They store the names of the wizards students (that are 120) in an array called SNAMES and their ids in another parallel array called SIDS.
The exercise is to create an algorithm that will output the names of the students that has not been enrolled to any clubs and, if all the students are in at least one club, there should be an appropiate message. You may use the method isIn from before.
For doing this we're going to split this problem into several parts.
- We state a flag variable where we supose that all the students are in a club.
- We need to loop through all the students IDs stored in SIDS (the 120).
- We need to check if they are not in a specific club. (all 5)
- If a student is not in any of them, we're going to output its name using SNAMES and the flag variable is going to be set as the opposite.
- After the loop we're going to check that flag variable to see if we didn't output any student's name. In that case we output a message.
This would be the description.
If they ask for the code this would be the possible answer.
flag = false
count= 0
loop for i from 0 to 119
flag = false
if isIn(SIDS[i], PotionsAndExplotions) then
flag = true
else if isIn(SIDS[i], SetupWizards) then
flag = true
else if isIn(SIDS[i], Tennis) then
flag = true
else if isIn(SIDS[i], SpellingSpells) then
flag = true
else if isIn(SIDS[i], AncientForbiddenLanguagesAndLatin) then
flag = true
end if
if flag= false
output SNAMES[i]
count= count +1
end if
end loop
if count = 0 then
output "there are no students who are not in a club"
end if
credit K.B.
FLAG = TRUE
loop for X from 0 to 119
if SIDS[X] not isIn (X, PotionsAndExplotions) then
if SIDS[X] not isIn (X, SetupWizards) then
if SIDS[X] not isIn (X, Tennis) then
if SIDS[X] not isIn (X, SpellingSpells) then
if SIDS[X] not isIn (X, AncientForbiddenLanguagesAndLatin) then
FLAG = FALSE
output ( SNAMES[X] + "is not in any group")
end if
end if
end if
end if
end if
end loop
if FLAG then
output ("All students are in clubs")
end if
credit V.G.
flag true
loop for i from 0 to 119
if not isIn(SIDS[i], PotionsAndExplotions) AND
not isIn(SIDS[i], SetupWizards) AND
not isIn(SIDS[i], Tennis) AND
not isIn(SIDS[i], SpellingSpells) AND
not isIn(SIDS[i], AncientForbiddenLanguagesAndLatin) then
flag = false
end if
end loop
if flag true then
output "the students are in the clubs"
end if
credit A.P.
There is another version creating an array of the collections.
FLAG = TRUE
ARRAY [5] = {PotionsAndExplotions, SetupWizards, Tennis, SpellingSpells, AncientForbiddenLanguagesAndLatin }
loop for X from 0 to 119
loop for Y from 0 to 4
if SIDS [X] not isIn (X, Y) then
FLAG = FALSE
output ( SNAMES[X] "is not in any group")
end if
end loop
end loop
if FLAG then
output ("All students are in clubs")
end if
Credit V.G.
Flights: Now with collections.
You have to implement the exercise 23 from here:
https://hackmd.io/GOWuknHrTJSBs6NsxEeDOA#Flag-variables-while-looking-into-arrays
Suposing that the nationalDestinations are stored in a collection and not in an array.
You can also use temporal collections if you need (For counting destinations will be easier)
First exercise is using the array so it's the same.
Next exercise is finding if an specific flight is national or international. Here you have the solution
PSEUDOCODE
flightDestinations[4500]
SpanishDestinations // collection
NATIONAL_DESTINATION = false
SpanishDestinations.resetNext()
loop while SpanishDestinations.hasNext()
CURRENT = SpanishDestinations.getNext()
if (flightDestination[2] = CURRENT)
NATIONAL_DESTINATION = true
break
end if
end loop
if NATIONAL_DESTINATION then NATIONAL_DESTINATION = true
output National
else
output international
end if
The next one about counting all the fights that are National.
flightDestinations[4500]
SpanishDestinations // collection
flag = false
count = 0
loop for i from 0 to 4499
SpanishDestination.resetNext()
loop while SpanishDestination.hasNext()
if (flightDestination[i] = SpanishDestination.getNext()) then
flag = true
break
end if
end loop
if flag then
count = count + 1
end if
end loop
output count
credits to CXJ
Count how many diffent locations we have in the array.
flightDestinations[4500] // given array
DISTINCT // empty collection
count = 1
new = true
DISTINCt.resetNext()
DISTINCT.addItem(flightDestinations[0])
loop for i from 1 to 4499
DISTINCT.resetNext()
loop while DINSTINCT.hasNext()
if (flightDestinations[i] = DISTINCT.getNext()) then
new = false
break
end if
end loop
if new then
DISTINCT.addItem(flightDestinations[i])
count = count + 1
end if
end loop
output count
