Setup

As always, register for the lab using the registration tool: https://register.caltech.codes. Then, follow the same instructions as last time to clone the repository and use IntelliJ.

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.

Submitting Your Code for Credit

Your code will be autograded when you submit it to gitlab. You may submit to gitlab as many times as you like, and only the last submission will be counted.

Committing and Pushing to the Repository

A “commit” is version control language for a chunk of changes that mean something when grouped together. Importantly, commits will only stay locally on your machine until you push them to the gitlab server.

Task 3. To commit to the repository, click the green checkmark on the top-right of IntelliJ’s interface. A window will pop up and ask you to type in a message. Choose some meaningful description of your feature, then click the little down arrow next to the “Commit” button on the bottom right of the dialog.
Choose “Commit and Push” in the little menu that pops up. If IntelliJ asks you if you’re sure you want to commit and push, say yes.

Checking the Results on `gitlab`

When you go to https://gitlab.caltech.edu, you should see your lab02 repository listed. Click on it. All the way on the right, there should be a red “X”, an orange “pause” symbol, a blue “time” symbol, or a green “check” symbol. This symbol indicates the status of the automated tests which will check the correctness of your code. Click on it. On the new page, you should see a table, and under “status”, there should be another symbol. Click on it. The new page will list the “categories” of tests for this repository. These will be some combination of “A”, “B”, “C”, and “D”. These letters indicate what grade you earned on the assessment for passing those tests. If you click on one of them, it will detail for you which sub-tests you passed and failed which might help you debug.

It is good practice to always check gitlab after submitting a project or lab in this course.

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