JAVA

public class WordPath {

private static class Node {

String word;

Node previous;

Node (String word) {

this.word = word;

}

}

static GUI ui = new GUI();

public static void main (String[] args) {

WordPath game = new WordPath();

String fn = null;

do {

fn = ui.getInfo("Enter dictionary file:");

if (fn == null)

return;

} while (!game.loadDictionary(fn));

String start = ui.getInfo("Enter starting word:");

if (start == null)

return;

while (game.find(start) == null) {

ui.sendMessage(start + " is not a word.");

start = ui.getInfo("Enter starting word:");

if (start == null)

return;

}

String target = ui.getInfo("Enter target word:");

if (target == null)

return;

while (game.find(target) == null) {

ui.sendMessage(target + " is not a word.");

target = ui.getInfo("Enter target word:");

if (target == null)

return;

}

String[] commands = { "Human plays.", "Computer plays." };

int c = ui.getCommand(commands);

if (c == 0)

game.play(start, target);

else

game.solve(start, target);

}

void play (String start, String target) {

while (true) {

ui.sendMessage("Current word: " + start + " " +

"Target word: " + target);

String word = ui.getInfo("What is your next word?");

if (word == null)

return;

if (find(word) == null)

ui.sendMessage(word + " is not in the dictionary.");

else if (!oneDegree(start, word))

ui.sendMessage("Sorry, but " + word +

" differs by more than one letter from " + start);

else if (word.equals(target)) {

ui.sendMessage("You win!");

return;

}

else

start = word;

}

}

static boolean oneDegree (String snow, String slow) {

if (snow.length() != slow.length())

return false;

int count = 0;

for (int i = 0; i

if (snow.charAt(i) != slow.charAt(i))

count++;

return count == 1;

}

List nodes = new ArrayList();

boolean loadDictionary (String file) {

try {

Scanner in = new Scanner(new File(file));

while (in.hasNextLine()) {

String word = in.nextLine();

Node node = new Node(word);

nodes.add(node);

}

} catch (Exception e) {

ui.sendMessage("Uh oh: " + e);

return false;

}

return true;

}

Node find (String word) {

for (int i = 0; i

if (word.equals(nodes.get(i).word))

return nodes.get(i);

return null;

}

void clearAllPrevious () {

for (int i = 0; i

nodes.get(i).previous = null;

}

void solve (String start, String target) {

clearAllPrevious();

Queue queue = new ArrayDeque();

Node startNode = find(start);

queue.offer(startNode);

while (!queue.isEmpty()) {

Node node = queue.poll();

ui.sendMessage("Polled");

System.out.println("DEQUEUE: " + node.word);

System.out.print("ENQUEUE:");

for (int i = 0; i

Node next = nodes.get(i);

if (next != startNode &&

next.previous == null &&

oneDegree(node.word, next.word)) {

next.previous = node;

queue.offer(next);

System.out.print(" " + next.word);

if (next.word.equals(target)) {

ui.sendMessage("Got to " + target + " from " + node.word);

String s = node.word + " " + target;

while (node != startNode) {

node = node.previous;

s = node.word + " " + s;

}

ui.sendMessage(s);

return;

}

}

}

System.out.println();

}

}

}

10. Add code to WordPath so it displays a message about how many times it polls the queue (Poll is expensive because you have the check the entire dictionary for neighbors. Add a class Nodecomparator that implements Comparator