Scramble Word Solution

The first free response question on the 2014 AP Computer Science exam had students working with an ArrayList of String references. You’re going to implement a method that scrambles a String based on a given set of rules and then uses that method to scramble strings in an ArrayList, or remove them if they don’t scramble.

Part A

For part A we’re tasked with implementing a method that scrambles a string following these rules

• If there’s an A followed by something else, swap them.
• Once a letter has been swapped, it shouldn’t be swapped again.

Here’s a couple of examples from the question

• TAN becomes TNA – the A in the second position swaps with the N
• WHOA stays WHOA – nothing after the A, so nothing to swap
• EGGS stays EGGS – no As, nothing to swap
• AARDVARK becomes ARADVRAK – The first A doesn’t swap because it’s followed by another A

I’m not all that crazy about the solution I have here. It works, but just something doesn’t feel right about it. Seems like there should be a cleaner way to solve this problem.

public static String scrambleWord( String word ) {
/* To be implemented in Part A */
String out = "";
for (int i=0; i<word.length(); i++) {
String letter = word.substring(i, i+1);
if (letter.equals("A") && i < word.length() - 1) {
String nextLetter = word.substring(i+1, i+2);
if (!nextLetter.equals("A")) {
out += nextLetter;
i++;
}
}
out += letter;
}
return out;
}

I started out with an empty string named out. We’ll be concatenating onto this as the method goes and then returning it at the end. I’ve also seen solutions where they change the order of the letters in word without another variable, but I generally try to stay away from doing that.

Next the code loops through the length of word because we need to consider every character.

Inside the loop the code pulls out a single character at position i and stores it as letter so that we can work with it later. If letter is an A and there is more to the string we pull nextLetter off as well. We have to make sure that i < word.length() - 1 because otherwise the substring call to get nextLetter could cause a StringIndexOutOfRange exception.

Then we look at nextLetter to see if it’s an A. If it is, we shouldn’t swap and the if is skipped.

If nextLetter isn’t an A it gets appended to out. And then the code increments i so that the next letter is skipped. That next letter will be the A from letter, and according to the problem description it shouldn’t be swapped again.

At the end of the loop we concatenate letter onto out. If there was a swap it’s going on after nextLetter. If there’s not a swap, it just gets tacked on where it was.

Part B

Next up is the ArrayList portion.

For part B we’re implementing a method called scrambleOrRemove that goes through a List of String references. For each element we get the scrambled version. If the scrambled and non-scrambled version are the same – EGGS or WHOA in the examples above – it’s removed from the list. If it’s scrambled we store the scrambled version instead of the original.

Important note here is that we’ve already done the scramble method, so we shouldn’t reimplement it in part B. We should just call it.

public static void scrambleOrRemove( List<String> wordList ) {
/* To be implemented in Part B */
for (int i=wordList.size() - 1; i>=0; i--) {
String word = wordList.get(i);
String scrambled = scrambleWord(word);
if (word.equals(scrambled)) {
wordList.remove(i);
}
else {
wordList.set(i, scrambled);
}
}
}

I like to go backwards through Lists when considering removals. It makes it easier to not skip elements when consecutive elements should be removed. So that’s what I did here, going from wordList.size() - 1 to >= 0.

Inside the loop the code pulls off the current element and stores it as word. It then calls the scrambleWord method and stores that back into scrambled.

If word.equals(scrambled) it means that it didn’t scramble, so we remove that element from the list.

If they are not equal then the string was scrambled and we set position i in wordList to the new, scrambled version.

Thoughts

Three common mistakes I’ve seen when we’ve done this FRQ in class

First, a lot of students forget to set the scrambled version back into wordList in part B. Not a huge deal, other than probably losing a point off of the problem. But it’s common.

Next, students will often skip elements to remove. This happens if you go forward through a list and remove elements, but don’t decrement the counter at the same time. When that happens, your code skips elements and doesn’t ever consider whether they should be removed or scrambled.

And last, and this is the most common, is students returning the modified List in part B. It’s a void, which means it cannot return a value. But also remember that since wordList is coming in as a reference, any changes to it inside the method will also affect it outside the method.