Every Sunday morning on NPR puzzle master Will Shortz presents word puzzles. In today's lecture we are going to construct a program designed to solve one of the puzzles previously featured on that broadcast.
In this puzzle we are given a list of several pairs of six letter words. For each pair of words we have to find a two letter prefix such that when that same prefix is added to each word in the pair the resulting words are also valid English words. For example, given the pair
parent petite
we can add the prefix 'ap' to form the words
apparent appetite
I have prepared a text file named 'problems.txt' that contains a list of these word puzzle problems. Our task in this lecture is to construct a program that can solve all of the puzzles in the list.
Like many word puzzles, this puzzle can be solved by a brute force search strategy. Specifically, we will do this:
Our solution strategy requires us to have a dictionary of valid eight letter words. To make this dictionary easier to work with I have constructed a Dictionary class in the Dictionary.java file.
package prefixes;
import java.io.File;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
public class Dictionary {
private Set<String> words = new TreeSet<String>();
public Dictionary(int length) {
Scanner input = null;
try {
input = new Scanner(new File("words.txt"));
} catch(Exception ex) {
ex.printStackTrace();
return;
}
while(input.hasNext()) {
String word = input.next();
if(word.length() == length) {
words.add(word);
}
}
input.close();
}
public boolean contains(String word) {
return words.contains(word);
}
}
Why have I chosen to construct a class? I have two primary motivations:
All classes have internal data that they store in member variables. Our Dictionary class will store a list of valid words in a TreeSet of Strings. As we saw in the previous lecture, the TreeSet class offers a fast contains() method that we can use to check whether or not a given String is a valid word. This in turn will allow us to offer a contains() method in our class that will check whether or not a given String is a valid word.
When we construct a class we will have the opportunity to construct one or more constructors that we can use to initialize the data in our member variables. In this case we need to open a text file containing a list of valid English words and put words from that list in our internal list of valid words. For this problem another concern we will have is looking for valid words of a given length. To solve our word puzzle we will be forming eight letter words only, so we can limit our dictionary to only valid eight letter English words. The constructor takes a length parameter that we can use to specify what length words we want to limit our word list to. The main loop in the constructor checks each word coming in from the word list to see whether or not it has the correct length. Only words with the correct length will make their way into our internal list of words. Furthermore, by making length a parameter of the constructor we can easily repurpose this Dictionary class for other problems. In the homework assignment for today's lecture I will ask you to look for valid six letter words instead of the eight letter words we are working with here.
The Dictionary class needs a list of English words to work with. I used the list of words that I found online at websites.umich.edu/~jlawler/wordlist.html.
Here now is the code for the puzzle solving program.
package prefixes;
import java.io.File;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Prefixes {
private static Dictionary dictionary;
public static void main(String[] args) {
dictionary = new Dictionary(8);
List<String> problems = new ArrayList<String>();
Scanner input = null;
try {
input = new Scanner(new File("problems.txt"));
} catch(Exception ex) {
ex.printStackTrace();
return;
}
while(input.hasNext()) {
String first = input.next();
String second = input.next();
solveProblem(first,second);
}
}
public static void solveProblem(String word1,String word2) {
System.out.println("Working on " + word1 + " and " + word2 + ":");
char A[] = new char[2];
for(char ch1 = 'a';ch1 <= 'z';ch1++) {
A[0] = ch1;
for(char ch2 = 'a';ch2 <= 'z';ch2++) {
A[1] = ch2;
String prefix = new String(A);
String fullWord1 = prefix + word1;
String fullWord2 = prefix + word2;
if(dictionary.contains(fullWord1) && dictionary.contains(fullWord2)) {
System.out.println(fullWord1);
System.out.println(fullWord2);
return;
}
}
}
System.out.println("No solutions found.");
}
}
The main program here handles the logistics of setting up the dictionary and reading the individual problems from a text file.
The actual puzzle-solving logic is broken out into a second method, solveProblem().
One small problem I had to solve here was figuring out how to form new strings by attaching a two letter prefix to our two words. If we can get the two letter prefixes to form a string we can simply concatenate that prefix with our words by using the familiar string + operator. Another thing that I knew I would be doing would be to cycle through all possible two letter prefixes by using a loop structure like this:
for(char ch1 = 'a';ch1 <= 'z';ch1++) {
for(char ch2 = 'a';ch2 <= 'z';ch2++) {
// Form a prefix string from chars ch1 and ch2
}
}
The solution to my problem was to look at the list of all possible constructors for the String class in the documentation for the String class. One of those constructors allows us to initialize a String from an array of chars. Given that, I then used this logic to construct the prefix string and concatenate it with the two words in the puzzle:
char A[] = new char[2];
for(char ch1 = 'a';ch1 <= 'z';ch1++) {
A[0] = ch1;
for(char ch2 = 'a';ch2 <= 'z';ch2++) {
A[1] = ch2;
String prefix = new String(A);
String fullWord1 = prefix + word1;
String fullWord2 = prefix + word2;
// Now search the dictionary to see if these are both valid words.
// If they are, print the solution and return
}
}
Besides writing programs to solve word puzzles we can also write programs to generate word puzzles. In this assignment you will write a program to generate a much larger list of examples of word problems of the same type we just solved.
Specifically, you will write a program to do this:
Here are some examples of groups that I found in my solution to this problem:
alarming alfresco almighty although altruism apparent appetite appraise approved filament fireside scavenge scoffing scouting scrabble scramble screamer scrubber
You should be able to find many more word groups.
Here is a helpful hint that will make your solution run much faster: take advantage of the fact that the word list you have is in alphabetical order.