PA #6: State Word Search

Introduction

As the crossword editor at the New York Times, Will Shortz is the world's most famous puzzle expert. On February 19th, 2012 he presented the following puzzle during the puzzle segment of NPR's Weekend Edition:

The word marten, as in the animal, consists of the beginning letters of Mississippi, Arkansas, Texas, and New Mexico. And you can actually drive from Mississippi to Arkansas to Texas to New Mexico, in that order. What is the longest common English word you can spell by taking the beginning letters of consecutive states in order, as you travel through them? My answer has eight letters. Maybe you can better mine. The longest answer will win.

The winner of this challenge was Roger Buch of Louisville Kentucky. Here is an excerpt from the transcript of the next week's show in which Mr. Buch describes his approach to solving the problem:

SHORTZ: Hey, Roger. Congratulations.

BUCH: Hello, Will. Thanks. Glad to finally talk with you.

MARTIN: So, Roger, you sent in the word omissions as your answer. How
did you figure it out?

BUCH: A lot of time staring at a globe with North America facing me.

MARTIN: Really?

BUCH: My globe has been sitting by my sofa for a week now. Any
commercial when I'm watching TV, looking over that globe, tracing my
finger around the country to come up with another word.

Mr. Buch is clearly not a computer scientist. No self-respecting computer scientist would solve this problem by hand when it would clearly be faster (and more fun) to write a program to solve it for us.

Your goal for this assignment is to write some recursive Java methods to support solving exactly the problem described above.

Provided Files

This problem can be broken into two parts:

Representing states and their adjacency relationships.
Searching for solutions.

We have provided helper code that addresses part 1). Your job is to handle part 2). The first step is to download the following files and make sure you understand how to use them:

StateGraph.java (Documentation) - This class represents a collection of State objects.
State.java (Documentation) - State objects maintain a list of neighboring states.
StateSpeller.java (Documentation) (INCOMPLETE) This class will contain the search code. You must complete the unfinished methods so that they are consistent with the provided JavaDoc comments.
StateSpellerTest.java Submission tests.
words.txt - the YAWL public domain word list containing 263,533 English words. It does not contain single-letter words or proper names.
states.txt - A text file containing a list of US states and their neighbors.

Program Requirements

You must complete the unfinished methods in StateSpeller.java without changing the existing method signatures. You will need to add additional private methods to handle the recursive searches.

According to the instructions above, valid solutions may pick up any (non-zero) number of letters from each state. The code would be simpler if we only considered the first letter from each state name. Under that requirement "tam" would be a solution:

tam
[Tennessee, Arkansas, Missouri]

but "team" would not qualify. StateSpeller.java includes methods for both the original version of the problem and the single-letter variation. You should solve the single-letter version first. Once you have completed that version, the multi-letter version should be relatively straightforward.

Hints/Advice

Understand the recursive structure of this problem. Recursion involves breaking a problem instance into one or more smaller instances of the same problem. In this case the problem is to find a path through a sequence of neighboring states that can be used to spell some arbitrarily long sequence of letters.
Imagine that my word is "canto" and that I am starting my search in California. My first step is to check the first letter of California against the first letter of "canto". Since they match, I can now break my original problem into the smaller problem of spelling "anto" by starting in any of the three states that neighbor California: Oregon, Nevada, or Arizona. If it is possible to spell "anto" by starting an any of those three states, then I know it is possible to spell "canto" by starting in California. How will I know whether it is possible to spell "anto" by starting in one of those states? I'll follow the same recursive logic I used in California: check the first letter, then recursively try out the neighboring states along with the remaining letters in the word.
Only use recursion where it makes sense. While the goal of this project is to give you a chance to practice recursive problem solving, you should still use loops where appropriate. For example, you will probably want to use a for loop to iterate over the possible starting states.
Work on the methods in the order they appear in StateSpeller.java. The logic for the three methods will be very similar, with each new method adding some additional complexity. For this project, don't worry if you have some code duplication between the methods.

The Longest Word

The methods in StateSpeller.java don't actually give us the longest possible word, they just allow us to check individual words to see if they can be spelled. Once those methods are finished, it should be straightforward to find the longest word through brute force: just check every word in the dictionary and keep track of the longest one that can be spelled. There is nothing to submit for this part of the assignment. Pride and glory will be yours if you can find a solution longer than Roger Buch's "omissions".

Extras

If you have extra time, there a number of possible extensions to this project:

What if you have an airline ticket that allows you to make one jump to a non-adjacent state?
What if you are allowed to use any portion of a states name in constructing a solution, not just the beginning.
What if you are allowed to revisit states, but you can only use letters that you didn't use on an earlier visit?

Submitting/Grading

Submit StateSpeller.java through Autolab by the project deadline. Your grade will be based on the following factors.

Autograding based on correctness:	90%
Instructor grading based on style and readability:	10%

You submission will need to conform to the course style guidelines except for the requirement that a method must have fewer than three return statements.