Word Ladder is a pretty popular game invented by Lewis Carroll, who is better known as the author of Alice in Wonderland.

In a word ladder puzzle you must make the change occur gradually by changing one letter at a time. At each step you must transform one word into another word, you are not allowed to transform a word into a non-word. For instance, the word “FOOL” can be transformed into the word “SAGE” as

FOOL
POOL
POLL
POLE
PALE
SALE
SAGE

There are many variations of the word ladder puzzle. For example you might be given a particular number of steps in which to accomplish the transformation, or you might need to use a particular word. In this section we are interested in figuring out the smallest number of transformations needed to turn the starting word into the ending word.

However, the best possible solution of the Word Ladder problem is using graphs, and with Neo4j, it is even easier.

Here is an outline of where we are going:

• Represent the relationships between the words as a graph.
• Use the graph algorithm known as breadth first search to find an efficient path from the starting word to the ending word.

Building the word ladder graph

Our first problem is to figure out how to turn a large collection of words into a graph. What we would like is to have a relation from one word to another if the two words are only different by a single letter. If we can create such a graph, then any path from one word to another is a solution to the word ladder puzzle.

Writing the words onto the graph is another beautiful problem altogether.

We could use several different approaches to create the graph we need to solve this problem. Let’s start with the assumption that we have a list of words that are all the same length. As a starting point, we can create a vertex in the graph for every word in the list. To figure out how to connect the words, we could compare each word in the list with every other. When we compare we are looking to see how many letters are different. If the two words in question are different by only one letter, we can create an edge between them in the graph. For a small set of words that approach would work fine; however let’s suppose we have a list of 5,110 words. Roughly speaking, comparing one word to every other word on the list is an O(n2)algorithm. For 5,110 words, n2 is more than 26 million comparisons.

We can do much better by using the following approach. Suppose that we have a huge number of buckets, each of them with a four-letter word on the outside, except that one of the letters in the label has been replaced by an underscore. For example, consider the image below, we might have a bucket labeled “pop_.” As we process each word in our list we compare the word with each bucket, using the ‘_’ as a wildcard, so both “pope” and “pops” would match “pop_.” Every time we find a matching bucket, we put our word in that bucket. Once we have all the words in the appropriate buckets we know that all the words in the bucket must be connected.

In java, this can be implemented using a Map as the obvious solution.. see the snippet below

for (String word : words) {
 for (int wordIndex = 0; wordIndex < word.length(); wordIndex++) {
   String keyWord = word.substring(0, wordIndex)+"_"+word.substring(wordIndex+1,word.length());
   if(!wordMap.containsKey(keyWord)){
    wordMap.put(keyWord, new ArrayList<String>());
   }
   wordMap.get(keyWord).add(word);
 }
}

Once we have the ‘well crafted’ map ready, it is easy to write this into a neo4j database.

• For every word, a separate node is introduced
• For every word under the same bucket, a relationship is made

Note : Neo4j don’t support the use of non-directional relationships. So, we go ahead and create a directional relationship and ignore the direction when we traverse the graph.

To write to the graph easily, a wrapper like the one shown below can be used,

public class WordGraph {

Map<String, Node> nodeMap;
GraphDatabaseService graphDb;

public WordGraph(){
  graphDb = NeoDatabaseHandler.getGraphDatabase();
  nodeMap = new HashMap<String, Node>();
}

private Node getNode(String word){
  if(!nodeMap.containsKey(word)){
   Node node = graphDb.createNode(NeoHelper.WordLabel.WORD);
   node.setProperty("word", word);
   nodeMap.put(word, node);
  }
  return nodeMap.get(word);
}

public void addEdge(String parentWord, String childWord){
  Node parentNode = getNode(parentWord);
  Node childNode = getNode(childWord);
  parentNode.createRelationshipTo(childNode, NeoHelper.RelationshipTypes.MOVE);
}
}

Whenever we need an edge created, we just call the method, addEdge and it will take care of the rest.

So, we iterate over the buckets and write the words and their relationships to the graph,

for (List<String> mappedWordsParent : wordMap.values()) {
  for (String parentWord : mappedWordsParent) {
    for (String childWord : mappedWordsParent) {
      if(!childWord.equals(parentWord)){
        wordGraph.addEdge(parentWord, childWord);
      }
    }
  }
}

The graph created using a minimum set of words will look like the one below, (apologies for the clutter in the relationship names)

Once, we have the graph ready, we can do a decent traversal to get the required path. Let us assume, we are trying to find a path from fool to sage

The graph algorithm we are going to use is called the “breadth first search” algorithm. Breadth first search (BFS) is one of the easiest algorithms for searching a graph.

From a very neat post that i came across

Given a graph G and a starting vertex s, a breadth first search proceeds by exploring edges in the graph to find all the vertices in G for which there is a path from s. The remarkable thing about a breadth first search is that it finds all the vertices that are a distance k from s before it finds any vertices that are a distance k+1. One good way to visualize what the breadth first search algorithm does is to imagine that it is building a tree, one level of the tree at a time. A breadth first search adds all children of the starting vertex before it begins to discover any of the grandchildren.

Implementing this on our own, let us save that for another day. Neo4j provides a neat Traversal Framework.

Lets have a look at the code,

graphDb
.traversalDescription().breadthFirst()
                       .relationships(NeoHelper.RelationshipTypes.MOVE)
                       .evaluator(Evaluators.includeWhereEndNodeIs(endNode))
                       .traverse(startNode)

It’s pretty straight forward. We traverse through relationships named Move ( which is the only relationship we have in the Graph ). We use an Evaluator, which decides what to be returned as the output of a traversal, and in this case, we pass the node corresponds to the endword. So, whenever the traversal reaches the endword ( in this case sage), it returns the corresponding path. The complete code can be found in github.

Once, we have the path, printing it to standard out yields,

fool
pool
poll
pall
pale
sale
sage

Which is pretty much what we expected.

Much content has been adopted from this book, which is the ONE place you can start to understand data structures in python.