One of the 2016 AP Computer Science A questions, RandomLetterChooser , asked students to write a class declaration from scratch.
The constructor receives a parameter of non-null Strings
The class has a getNext() method that returns a random String from that list . Each element in the list can only be returned once, and after all of the elements have been returned, the getNext() method returns “NONE.”
There are many ways that students can solve this AP question and there are also many common pitfalls including
- aliasing the constructor’s parameter
- failing to ensure that all elements of the list have been returned prior to “NONE”
Students can also make their lives much more difficulty by their choice of data structure. In particular, an array makes this much more challenging than an ArrayList (the ArrayList code is at the very bottom btw)
Let’s examine several solutions to the first part of this question; some are 100% correct; some are partly correct.
Example Codeset 1:
What do you think about the code below?
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
public class RandomLetterChooser1 { private String[] words ; public RandomLetterChooser1( String[] words) { this.words = words; } public String getNext(){ if( words.length ==0) return "NONE"; int rand = (int)(Math.random() * words.length); while( words[rand] == null) rand = (int)(Math.random() * words.length); String word = words[rand]; words[rand]= null; return word; } } |
Well, there are two major problems with the first example above
- this.words becomes an alias of the parameter. So the student would lose points for modifying the original data structure.
- The logic for returning “NONE” is flawed. After all of the array values are changed to “null”, there is no way to get out of the loop on lines 18-19 that randomly selects elements in the array over and over again.
Score on the first part : 5 out of 7 (-1 for modifying original data, -1 for not ensuring a correct return value)
Ok, so let’s give this another try and see if we can’t fix these errors
Example Codeset 2:
What do you think about the code below?
Hint: the only changes are in the constructor.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
public class RandomLetterChooser2 { private String[] words ; public RandomLetterChooser2( String[] someWords ) { words = new String[someWords.length]; for( int i =0 ; i < someWords.length ;i++) words[i] = someWords[i] ; //copy values } public String getNext(){ if( words.length ==0) return "NONE"; int rand = (int)(Math.random() * words.length); while( words[rand] == null) rand = (int)(Math.random() * words.length); String word = words[rand]; words[rand]= null; return word; } } |
So, unlike the first example, here we are not creating an alias of the parameter (we’re making a copy into a new array) , so our only problem is the fact that we still run into an infinite loop after we have returned all the random values..
hmmm….
Score on the first part : 6 out of 7 (-1 for not ensuring a correct return value)
Example Codeset 3:
What do you think about the code?
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
public class RandomLetterChooser3 { private String[] words ; public RandomLetterChooser3( String[] someWords ) { words = new String[someWords.length]; for( int i =0 ; i < someWords.length ;i++) words[i] = someWords[i] ; //copy values } public String getNext(){ if( words.length ==0) return "NONE"; int rand = (int)(Math.random() * words.length); String randomWord = words[rand]; String[] updatedWords = new String[words.length-1]; int index=0; for( int i =0 ; i < words.length ;i++) { if( i != rand) //then copy { updatedWords [index] = words[i] ; index++; } } words= updatedWords; return randomWord; } } |
Yes, a lot has changed here and codeset3 works fine . We create a copy of the original data structure (so don’t lose points for modifying original data) and we correctly resize our array over and over, shrinking it by 1 by removing the value that we’ll return.
Score on the first part : 7 out of 7
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
import java.util.ArrayList; public class RandomLetterChooser4 { private ArrayList<String> words ; public RandomLetterChooser4( String[] someWords ) { words = new ArrayList<String>(); for( String word: someWords) words.add(word) ; } public String getNext(){ if( words.size() ==0) return "NONE"; return words.remove( (int)(Math.random() * words.size())); } } |
Score on the first part : 7 out of 7
As you can see from the code above, an arraylist greatly simplifies the solution but most students did not see that this data structure was much more ideal for the question and, instead, decided to use arrays.
