Setup

Register for the lab using grinch: https://grinch.caltech.edu/register and clone the repository as explained in the setup instructions.

Goals and Outcomes

By the end of this lab, you will…

have more experience with recursive backtracking
have seen how small changes in a problem result in wildly different solutions and runtimes

The Anagrams Problem

An anagram is a word or phrase made by rearranging the letters of another word or phrase. In this lab, we differentiate between two types of anagrams of a String \(s\):

Word Anagrams are single words from a dictionary that are exact permutations of the letters of \(s\)
Phrase Anagrams are a list of one or more words from a dictionary that together (ignoring spaces and capitalization) form an exact permutation of the letters of \(s\)

As always, examples make this significantly more clear.

\[\begin{align} \require{extpfeil}\text{meat} &\xmapsto[\text{word}]{} \{\text{mate}, \text{meat}, \text{tame}, \text{team}\}\\ \text{meat} &\xmapsto[\text{phrase}]{} \{\text{mate}, \text{meat}, \text{tame}, \text{team}\}\\ \text{magikarp} &\xmapsto[\text{word}]{} \{\}\\ \text{magikarp} &\xmapsto[\text{phrase}]{} \{\text{karma pig}, \text{magi park}, \text{park magi}, \text{pig karma}\}\\ \text{listen} &\xmapsto[\text{word}]{} \{\text{listen}, \text{silent}, \text{tinsel}\}\\ \text{listen} &\xmapsto[\text{phrase}]{} \{\text{let sin}, \text{listen}, \text{lit sen}, \text{nil set}, \text{sen lit}, \text{sen til}, \text{set nil}, \text{silent}, \text{sin let}, \text{til sen}, \text{tinsel}\} \end{align}\]

Provided Helper Class: LetterBag

We have provided you with a simple LetterBag class which you will find helpful in your implementation.

public LetterBag(String s)

The LetterBag constructor takes in a String and creates a mapping between characters in that string and the number of times they appear in that string.

public LetterBag subtract(LetterBag other)

Takes in another LetterBag and creates a new LetterBag that represents the difference between this and other by subtracting the counts for each letter.

Note: this method returns null if there are more of any given character in other than in this.

public boolean isEmpty()

Checks if there are any letters in this LetterBag.

Solving the Phrase Anagrams Problem

One of the goals of this lab is to implement a recursive backtracking algorithm. As discussed in lecture, enumeration problems lend themselves very nicely to the recursive backtracking pattern.

public static printPhrases(String phrase, List<String> dictionary)

Prints all the phrase anagrams of phrase ignoring all non-lowercase letters.

You will need an accumulator like used in lecture. In this case, you will want to use a List of Strings.
You will need to keep track of “what letters are left to use” in a choice. (Hint: the LetterBag class could be useful here.)
It is very easy to get stuck on this type of problem. Please remember to use the members of course staff that are in the room. We will be especially helpful for this lab.

Task 1. Implement the printPhrases method using recursion.

At this point, if printPhrases is implemented properly, all of the PhraseAnagramsTests should pass.

Solving the Word Anagrams Problem

The second goal of this lab is to see how small changes in problems can allow more clever solutions which run significantly faster. Our phrase anagram solution effectively runs over all multisets of dictionary words.

This is extremely inefficient if all we care about is printing matching words. It’s possible to find the word anagrams of a phrase in time proportional to the size of the dictionary.

This time, you should use an algorithmic pattern centered around a data structure, rather than recursive backtracking. There are ways to make this very fast, but they are not necessary to get credit for this lab.

public static printWords(String phrase, List<String> dictionary)

Prints all the word anagrams of phrase ignoring all non-lowercase letters.

This method must run in time proportional to the size of the dictionary. You may not use recursion.

Task 2. Implement the printWords method without using recursion.

At this point, if printWords is implemented properly, all of the WordAnagramsTests should pass.

Checking the Results on `gitlab`

Task 3. Check to make sure you are passing all the tests on gitlab.

Getting Checked Off

At the end of every lab, you will need to call over a member of course staff to review your work. For you to receive credit for the lab, a staff member must check you off!