PA #3: 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:

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

I have provided 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 signatures. 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 straightforward.

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.
• 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?

Submitting/Grading

Submit StateSpeller.java through Web-CAT by the project deadline. Your grade will be based on the following factors, and may also be affected by the number of submissions that you make. See below for more details on how each component will be calculated.

Autograding based on correctness/testing of firstLetterWords:	60%
Autograding based on correctness/testing of anyWords:	20%
Autograding based on static analysis of style:	10%
Instructor grading based on style and readability:	10%

You do not need to submit your own unit tests for this project. Your code will be tested against instructor provided unit tests.

Autograding based on static analysis of style

Web-CAT will use checkstyle to analyze your code for conformance to the course style guide. I strongly suggest that you to install checkstyle for Eclipse on your own machine so that you can run your own style checks before submission. You can find the checkstyle configuration file that Web-CAT will use on the course supplemental material page.

Instructor grading based on style and readability

This portion of your grade will based on stylistic issues that cannot be checked automatically. This includes:

• Appropriate acknowledgment statement.
• Meaningful variable names.
• Clear documentation.
• Avoiding unnecessary code repetition.
• etc.

Submission penalties

Your grade will also be based on the number of submissions that you make. You may make one free submission per day. Beyond those free submissions, you may make up to six submissions with no penalty. Your grade will then be reduced by 3% after every six submissions:

Number of submissions	Penalty
1-6	0
7-12	-3%
13-18	-6%
...	...