mathr / blog / #

Word edit graphs

Word edit graphs

Word edit graphs Haskell source code

Inspired by this comment in the #haskell IRC channel on freenode:

2011-04-09 21:11 erus_ i wanna write a program that can find a path from one word to another by only (changing one letter at a time) or (adding or removing 1 letter) and still leaving a word in the dictionary

I spent altogether too much time this weekend writing a program that finds all such shortest paths in the form of a graph. The algorithm starts with two one-node graphs, and grows them blindly in all possible directions until they intersect (or there are no more useable words). Then it works back from the intersections, discarding the paths that led to nowhere, and outputs the result as a .dot file.

The program can work with more than two words, too, I quite like this one.