Anagram Solver

Meta-information

Summary Anagram Solver -- use a dictionary of words to find all anagrams of a given phrase
Topics
 recursive backtracking
Audience
 Intended for CS2
Difficulty
 Intermediate difficulty, one week assignment
Strengths
 The greatest strength is that students really love to run the program once it's done. They particularly seem to love finding anagrams of names (their own name, their friends' names, their relatives' names). It also demonstrates how a complex task can be accomplished with a short program (fewer than 50 lines) using a powerful programming technique (recursive backtracking) and leveraging other components (Map, ArrayList, a custom LetterInventory class).
Weaknesses
 Because few lines of code are required to solve the problem, there is greater possibility for students to help each other too much. Also, the program can explode rather quickly for longer phrases (taking too long to find answers and producing too much output).
Dependencies
 In this form, the assignment assumes the existence of a class called LetterInventory that handles the low-level character details. This can be given as an earlier assignment, which makes this two assignments in one.
Variants
 As with all backtracking problems, this one can blow up quickly (run slowly, produce too much output). There are many optimizations that can be explored. One can also explore issues like limiting the output (number of words, excluding one-letter words, etc). And it's interesting to run the program with different dictionaries. This also makes a great Prolog problem.

Detailed Description

I was inspired to write this assignment by a web page called Andy's Anagram Solver. I was surprised to find how fun it was to generate anagrams of phrases even though the interface to the program is so simple (you enter a phrase, you pick a dictionary, it throws a huge output back at you). I showed this web page to other people who immediately wanted to grab my keyboard away so that they could type in their own phrases to scramble. That's when I realized that this program had the "fun to run" quality that is the hallmark of nifty assignments.

I first wrote this assignment in Prolog for a comparative programming languages course where the students wrote about 15 lines of code on top of some basic utility code that I provided. For anyone interested in the Prolog version, I include:

I translated this into a Java assignment intended for CS2. Almost 20 years ago a former Stanford colleague of mine named Steve Fisher convinced me that many recursive backtracking problems can be written concisely in a procedural language if you separate the low-level details from the recursive backtracking code. I followed that model in the anagrams program itself (separating off low level details into something called LetterInventory) and I showed them an example in class where I did the same kind of thing.

I use the "8 queens" problem as an example in lecture where a Board class does most of the low-level work of keeping track of the placement of queens, allowing us to write concise backtracking code that does the actual search. Below are the source files:

The code for the assignment itself ends up looking a lot like the 8 queens code, so I tell my students that it's important to study 8 queens and understand how it works before attempting the anagrams problem. Below are the resources for the assignment itself:

As mentioned earlier, the program assumes the existence of a class called LetterInventory. I turned this into an opportunity. Earlier in the quarter I was looking for a fairly simple "ArrrayList like" assignment. I knew I'd need the LetterInventory later on, so I assigned it early in the course. At the time, the students thought the program was a little on the stupid side ("Who would ever want this?"). When we got to anagrams and they saw how useful LetterInventory was, they changed their tune ("Wow, that thing I thought would be useless turned out to be really useful--maybe writing code that other people specify isn't such a waste of time after all"). I include below the resources for the LetterInventory assignment:

Sample solutions to all of these problems can be obtained from me (the Prolog version, AnagramSolver.java and LetterInventory.java).
Stuart Reges
Last modified: Wed Sep 7 16:16:40 PDT 2005

Extra info about this assignment: