Word Games

A few months ago on a flight to San Diego I opened up an inflight magazine and found one of those MENSA puzzles.

The goal of the puzzle was to get from one word to another in four steps only being able to change a single letter at a time. I cannot remember the exact words, but I couldnt do it because I was unfamiliar with one of the intermediate words. In a nutshell, the game is as follows.

In 3 steps, get from MOOD to GOAT, only changing one letter in the word at each step.
A possible solution would be

MOOD
MOOT
BOOT
BOAT
GOAT


though they may be other solutions. The correct solution is the fastest one possible
This is an interesting problem, and I wondered whether it would be possible to create an application that would generate such puzzles. There are a number of prerequisites

1: A list of all valid english words (this is tougher than it sounds, there are multiple lists and they dont agree)
2: A way to specify word length and step length (I want a puzzle where the words are 4 characters long and the solution is 4 steps).

I begun playing around with it and came up with the basic generation code. For example, given a starting word of POT, create a Tree with all possible combinations. Because the tree could be arbitrarily deep, specify a termination length (a given path cannot be longer than X).

For example, assume the only valid 3 letter english word were [pot,pit,pet,lot,bot,pin,tin,tan,pep,bet] and given a start word of pot and a max depth of 5, here is the Tree structure built.

The total possible paths (irrespective of path length) are

[pot, pit, pin, tin, tan]
[pot, pet, pep]
[pot, pet, bet]
[pot, lot]
[pot, bot, bet]

In fact, the Groovy unit test for this code would look as below

@Test
void testGetAllPaths(){
	def allowedWords = ['pot','bot','lot','pet','pit','bet','pep','pin','tin','tan']
	Node node = new Node(null,'pot',allowedWords,0,5)
	def result = node.getAllPaths()
	assert result == [['pot', 'pit', 'pin', 'tin', 'tan'], ['pot', 'pet', 'pep'], ['pot', 'pet', 'bet'], ['pot', 'lot'], ['pot', 'bot', 'bet']]

}

The code for the Node class is below

package com.wordPath.utilities;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
 * This class represents a Tree structure of word combinations with a single letter in the word changed as you progress
 * down the tree structure
 * frog -> frag -> brag -> brat
 * @author wkimeria
 *
 */

public class Node {

	/**
	 *  Create tree starting from the given start word (value), terminate branches at specified level
	 * @param parent			Parent Node
	 * @param value				Node value
	 * @param allowedWords		List of allowed words (must be valid english words of a given length)
	 * @param level				level of this node in given tree structure. Root is 0
	 * @param requestedDepth 	Level at which to terminate branches
	 */

	String value;
	List children;
	Node parent;
	int level;
	boolean visited;

	Node(Node parent, String value, List allowedWords, int level,
			int requestedDepth) {
		List allowedWordsForPath = new ArrayList();
		allowedWordsForPath.addAll(allowedWords);
		allowedWordsForPath.remove(value);
		children = new ArrayList();
		this.value = value;
		this.level = level;		
		this.parent = parent;
		if (level >= requestedDepth-1) {
			return;
		}
		List variations = new ArrayList();
		int wordLength = value.length();
		for (int i = 0; i <= wordLength; i++) {
			variations.addAll(getVariations(value, i));
		}
		variations = getAllowedWords(variations, allowedWordsForPath);
		if (variations.size() != 0) {
			level++;
			for (String v : variations) {
				Node n = new Node(this, v, allowedWordsForPath, level,
						requestedDepth);
				children.add(n);
			}
		}
	}

	/**
	 * Given a list of words generated by combinations, remove invalid words and only
	 * return valid english words.
	 * @param words
	 * @param allowedWords
	 * @return
	 */
	List getAllowedWords(List words, List allowedWords) {
		List allowedWordsFound = new ArrayList();
		for (String w : words) {
			if (allowedWords.contains(w)) {
				allowedWordsFound.add(w);
				allowedWords.remove(w);
			}
		}
		return allowedWordsFound;
	}

	/**
	 * For a given word, get all variations with the letter at position s cycled
	 * @param word
	 * @param pos
	 * @return
	 */
	List getVariations(String word, int pos) {
		List variations = new ArrayList();
		if (word != null && pos < word.length()) {
			String letter = word.substring(pos, pos + 1);
			char next = (char) (letter.toCharArray()[0] + 1);
			char stop = (char) (next - 1);
			while (next != stop) {
				String current = word.substring(0, pos) + next
						+ word.substring(pos + 1, word.length());
				variations.add(current);
				next++;
				if (next == (char) 'z' + 1) {
					next = (char) 'a';
				}
			}
		}
		return variations;
	}

	/**
	 * Get a list of lists of all possible paths (essentially capturing each depth first search from root to leaf
	 * @return
	 */
	public List> getAllPaths() {
		List> paths = new ArrayList>();
		Deque queue = new LinkedList();
		queue.clear();
		queue.add(this);
		List currentPath = new ArrayList();
		Deque currentPathQueue = new LinkedList();
		while (!queue.isEmpty()) {
			Node n = queue.removeLast();
			if (n.children != null && n.children.size() > 0) {
				queue.addAll(n.children);
			} else {
				currentPathQueue = new LinkedList();
				currentPath = new ArrayList();
				Node walker = n;
				while (walker != null) {
					currentPathQueue.add(walker.value);
					walker = walker.parent;
				}
				while (!currentPathQueue.isEmpty()) {
					currentPath.add(currentPathQueue.removeLast());
				}
				paths.add(currentPath);				
			}
		}
		return paths;
	}

	/**
	 * Return string representation of Tree with value and node depth (uses Breadth First Search)
	 */
	public String toString() {
		String nodeValues = "";
		Queue queue = new LinkedList();		
		queue.clear();
		queue.add(this);
		while (!queue.isEmpty()) {
			Node n = queue.remove();
			String parent = "";
			if (n.parent != null) {
				parent = n.parent.value;
			}
			nodeValues += n.value + " " + n.level + " parent = " + parent
					+ "\n";
			if (n.children != null)
				queue.addAll(n.children);
		}
		return nodeValues;
	}
}

This class is not perfect. You could call it and start with a particularly unlucky word and building the Node could take an inordinate amount of time, but it is a first pass. The idea is to have a running process that generates puzzles and stores them, that way one could request a puzzle that starts with x word and ends with y word of length n, and get back a list of all puzzles that fit the given criteria

int wordLength = 4
int puzzleLength = 3
List allowedWords = new ArrayList<>()
getWordsOfLength(wordLength, allowedWords)
System.out.println("Words = " + allowedWords.size())
Double randomWordIndex = Math.random() * allowedWords.size()
for(String s:allowedWords){
	String randomWord = s;
	Node node = new Node(null, randomWord, allowedWords, 0, puzzleLength);
	println("--------------- Node built for ${s} ---------------------");
	List> paths = node.getAllPaths();
	for (List path : paths) {
		println(path);		//Save paths somewhere
	}
	System.out.println("Possible Paths = ${paths.size()}");
}

Ongoing code at

WordPath on GitHub