So, in preperation for the computer contest (which you may remember I qualified for a while back), I did a 9 poit (the highest amount) problem. Turns out… it was really difficult. Edit: By the way, for anybody who can’t tell… this is in Java. You will also need JDK 1.5 (uses scanner).
My teacher had no idea how to do it, and as we were leaving, he thought of the phrase “breadth vs. depth search,” but I don’t think he knew exactly how to program it.
So, I showed the problem to my dad, and he immediately knew about the search algorithm, but wasn’t so good at programming it.
It’s taken us about three hours, but I present to you… our finished project!
import java.util.*;
import java.io.*;
public class pr93 {
public static void main (String args[]) throws IOException {
Scanner scanner = new Scanner (new FileReader ("pr93.txt"));
int dictionaryLength = scanner.nextInt();
ArrayList<String> words = new ArrayList<String>();
int testCases = scanner.nextInt();
scanner.nextLine();
for (int i=0; i<dictionaryLength; i++) {
words.add(scanner.nextLine());
}
for (int i=0; i<testCases; i++) {
ArrayList<Path> potentialPaths = new ArrayList<Path>();
ArrayList<Path> newPaths = new ArrayList<Path>();
boolean printed = false;
String start = scanner.next();
String goal = scanner.next();
for (int j=0; j<words.size(); j++) {
if (pr93.areLinked(words.get(j), start)) {
Path path = new Path (start, words.get(j));
potentialPaths.add(path);
}
}
for (int j=0; j<words.size()&&printed==false; j++) {
for (int m=0; m<potentialPaths.size(); m++) {
if (potentialPaths.get(m).isFinished(goal)) {
potentialPaths.get(m).printPath();
printed = true;
break;
}
}
potentialPaths = pr93.buildNewPaths(words, potentialPaths, newPaths);
}
System.out.println();
}
}
public static boolean areLinked (String word1, String word2) {
int different = 0;
StringBuffer wordOne = new StringBuffer(word1);
StringBuffer wordTwo = new StringBuffer(word2);
for (int i=0; i<word1.length(); i++) {
if (wordOne.charAt(i)!=wordTwo.charAt(i)) {
different++;
if (different>1) return false;
}
}
if (different==0) {
return false;
}
return true;
}
public static ArrayList<Path> buildNewPaths (ArrayList<String> words, ArrayList<Path> oldPaths, ArrayList<Path> newPaths) {
for (int j=0; j<oldPaths.size(); j++) {
String lastWord = oldPaths.get(j).lastWord();
for (int m=0; m<words.size(); m++) {
if (pr93.areLinked(lastWord, words.get(m)) &&
!oldPaths.get(j).hasWord(words.get(m))) {
Path newPath = new Path(oldPaths.get(j), words.get(m));
newPaths.add(newPath);
}
}
}
return newPaths;
}
}
class Path {
ArrayList<String> path = new ArrayList<String>();
public Path (String start, String end) {
path.add(start);
path.add(end);
}
public Path (Path oldPath, String word) {
path = new ArrayList<String>(oldPath.getPath());
path.add(word);
}
public void add (String word) {
path.add(word);
}
public ArrayList<String> getPath () {
return path;
}
public void printPath () {
for (int i=0; i<path.size(); i++) {
System.out.println(path.get(i));
}
}
public String toString () {
return path.toString();
}
public String lastWord () {
return path.get(path.size()-1);
}
public boolean isFinished (String goal) {
if (path.get(path.size()-1).equals(goal)) {
return true;
}
return false;
}
public boolean hasWord (String word) {
return path.contains(word);
}
}
[size=4]USAGE[/size]
It’s actually really simple. Given a dictionary, it will find the shortest path between two words. The sample input looks like this:
8 3
that
this
what
then
when
than
thin
thus
this that
what when
when then
The 8 represents the number of words in the dictionary (always all the same length), and the three represents how many chains you will need to find.
The sample output looks like this:
this
thin
than
that
what
that
than
then
when
when
then
Huzzah!
[whisper]I also could have taken the brute-force approach, but ■■■■ that wouldn’t have been nearly as pretty![/whisper]
