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 a Java program that solves exactly the problem described above. Notice that the problem statement is ambiguous: it doesn't specify whether or not we are allowed to reenter states. For the purposes of this assignment we will assume that reentering states is not allowed.

Provided Files

This problem can be broken into three parts:

Representing states and their adjacency relationships.
Determining which strings correspond to English words.
Searching for solutions.

We are providing helper code that addresses parts 1) and 2). Your job is to handle part 3). 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.
WordTree.java (Documentation) - This is a "dictionary" class that determines whether arbitrary strings correspond to English words.
WordNode.java - Helper class for WordTree. (You shouldn't need to interact with this class directly.)
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.
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.

Note that you will need to write your own driver class for testing.

Program Requirements

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

Rather than searching for the single longest admissible word, the methods in StateSpeller.java must return all solutions longer than some minimum value. The return values are ArrayLists of Strings where each string represents a single solution.

Each solution string must contain three pieces of information: the word, the length of the word, and the corresponding list of states. Here is an example of a correctly formatted entry:

team 4 [Tennessee, Arkansas, Mississippi]

Solution strings should not have any trailing spaces and should not be terminated with a newline. The solution strings may be returned in any order.

If the same word can be constructed using two separate state sequences, both should be returned. For example,

team 4 [Tennessee, Arkansas, Mississippi]

and

team 4 [Tennessee, Arkansas, Missouri]

are considered different solutions.

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 3 [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 simple.

Hints

The logic of these recursive searches will be similar to the code you wrote for the DirectorySizeCalculator class in the Experimenting with Recursion lab. It may be helpful to take another look at that code.
Keep in mind that an ArrayList is a reference type. Returning references to instance variables can lead to confusing bugs. You should return copies instead.
Feel free to add additional instance variables to the StateSpeller class. In particular, you will probably want to use an ArrayList to keep track of which states have been visited while constructing the current word: you can add a state to the list when your search visits the state, and remove it from the list when the search is finished with the state.
You don't need to write a method to convert an ArrayList of states to a string. The ArrayList toString method will return a correctly formatted string.

Extras

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

What is the longest possible word if we are allowed to revisit states?
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?

Honor Code

This work must conform to the JMU Honor Code and the specific requirements of this class. NO help may be provided by any student to another student. Authorized help is limited to your textbook, the TAs for any CS139 or CS239 section, and the professor for your section. Be sure to acknowledge any help that you do receive from a TA. We are using a plagiarism detection tool called MOSS this semester. All code is subject to evaluation by MOSS at the instructor's discretion.

Grading

Your program will be evaluated both on its correctness and conformance to the required Style elements.
You will achieve a grade of 70 points for a program that runs correctly and produces exactly the required output in the required format on time.
10 points will be based on your testing code. You must submit a driver class that includes calls to each of the public methods in StateSpeller.java.
The remaining 20 points will be based on your conformance to the Style Guide and other requirements of the assignment. Review the Style Guide before submitting your program and the grade sheet which is produced by the submit system.
All grades will be based on 100 points.
You may submit any number of times. The only one I will count is the one that corresponds to the hard-copy report that you turn in.
The hard-copy that you turn in will be the formatted version that I will check. Make sure it has no line wraps or other spacing issues.
Successfully submitted programs that are late will be graded, then the late penalty is assessed for each day late according to the following schedule.

For submissions after:

April 15 - 5 point penalty.
April 16 - 15 point penalty.
April 17 - 25 point penalty.
April 18 - 35 point penalty.
April 19 - 45 point penalty.
April 20 (5pm) - 55 point penalty.
April 22 - 100 point penalty.