RandomStringChooser free response answer 7

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.

7 thoughts on “RandomStringChooser free response answer

  1. Reply APCS student May 5,2016 11:58 pm

    Would it be possible to have a ArrayList for valuesRemaining, and then make each value false after it has been chosen?

    • Reply Brandon Horn May 6,2016 8:02 am

      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).

  2. Reply Nathan Cooper Jones May 6,2016 1:20 am

    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; 
    		}
    	}
    }
    
    • Reply Brandon Horn May 6,2016 8:09 am

      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.

  3. Reply Shawn M. Hanes May 6,2016 3:49 pm

    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”

    • Reply Brandon Horn May 6,2016 4:24 pm

      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.

      • Reply Shawn M. Hanes May 9,2016 8:14 am

        That portion is fairly ambiguous. It will be interesting to see how it’s scored. Thanks Brandon.

Leave a Reply