RandomStringChooser free response problem from the 2016 AP Computer Science A Exam.
RandomStringChooser is #1 from the from the 2016 AP Computer Science A Free Response problems.
https://secure-media.collegeboard.org/digitalServices/pdf/ap/ap16_frq_computer_science_a.pdf
Part (a) – RandomStringChooser class
public class RandomStringChooser
{
private ArrayList<String> valuesRemaining;
public RandomStringChooser(String[] values)
{
valuesRemaining = new ArrayList<String>();
for(String value : values)
valuesRemaining.add(value);
}
public String getNext()
{
if(valuesRemaining.size() == 0)
return "NONE";
int index = (int) (Math.random() * valuesRemaining.size());
return valuesRemaining.remove(index);
}
}
An ArrayList is an appropriate instance variable since it allows removal of selected elements.
Part (a) – RandomStringChooser class – alternate solution
public class RandomStringChooser
{
private String[] values;
private int valuesRemaining;
public RandomStringChooser(String[] vals)
{
values = new String[vals.length];
for(int i = 0; i < values.length; i++)
values[i] = vals[i];
valuesRemaining = values.length;
}
public String getNext()
{
if(valuesRemaining == 0)
return "NONE";
int index = (int) (Math.random() * valuesRemaining);
String selected = values[index];
values[index] = values[valuesRemaining - 1];
valuesRemaining--;
return selected;
}
}
An array can be used as an instance variable. Some effort is then required to ensure that each element can be selected only once. Note that the problem prohibits modification of the parameter passed to the constructor, so a copy must be made.
Part (b) – RandomLetterChooser constructor
public RandomLetterChooser(String str)
{
super(getSingleLetters(str));
}
It is permissible to call a static method within a call to a superclass constructor.
Alternatively, nothing in the problem description appears to prohibit declaring additional methods in part (a). A default constructor and a mutator method that accepts an array could be created.
Would it be possible to have a ArrayList for valuesRemaining, and then make each value false after it has been chosen?
You could conceivably maintain a parallel list of boolean values. If your random index referred to a number that was already chosen you could choose another random number. It would be more complex to code though (and substantially less efficient).
I didn’t do my code for part (a) like the two above so I just wanted to supply my code below, which I just tested in Eclipse and works to give the correct output (client code not provided). I just took the user’s array input in my constructor and set it to the parameter in the class and went from there. This solution seemed the easiest to do on the test and works well.
public class RandomStringChooser { private String[] array; public RandomStringChooser(String[] arr) { array = arr; } public String getNext() { if (array.length==0) { return "NONE"; } else { int index = (int) (Math.random() * array.length); String result = array[index]; String[] newArray = new String[array.length-1]; int i=0; for (String word: array) { if (!word.equals(result)) { newArray[i]=word; i++; } } array = newArray; return result; } } }I agree that this works and is logical. I find it more complex but if it made sense to you that’s what you’re going for on the Exam.
This is my first year teaching AP CS-A and I’m going over the practice problems now so that I can review them with my students. My understanding of this question implies there could be repeating words in the passed array, in which case Nathan’s solution would not work. I assume a hefty amount of partial credit would be given, though.
You can try it by passing in “wheels”, “wheels”, “on”, “bus”
Nathan’s solution would remove all copies of a string that appeared more than once in the array the first time it was returned by getNext. My solution would remove only a single copy of such a string when it was returned by getNext.
The phrasing in the question is: “Once a particular string has been returned from a call to getNext, it is no longer available to be returned from subsequent calls to getNext.”
I could see interpreting that to mean that each instance of the string is no longer available or that the value represented by the string is no longer available. Since the problem doesn’t otherwise clarify (or I missed it) I think Nathan’s solution is correct.
That portion is fairly ambiguous. It will be interesting to see how it’s scored. Thanks Brandon.
Why do you need to class super in part b? Isn’t the getSingleLetters method in the subclass?