Archive for October, 2003
Kata Nineteen: Word Chains
Three things I love: word games, connecting things and writing code. So when I ran across Dave Thomas’
Kata Nineteen: Word Chains
post, I couldn’t not try to do it. (He’s got some other great kata too.)
adjacency matrix size: 35992 adjacency matrix time:87953ms "lead" to "gold": lead, load, goad, gold search time:219ms "ruby" to "code" ruby, rudy, rude, rode, code search time:125ms "code" to "ruby" code, rode, rude, rudy, ruby search time:110ms "java" to "code" java, lava, lana, lane, lone, cone, code search time:156ms "sean" to "deck" sean, bean, beak, beck, deck search time:141ms
I use a modified version of Dijkstra’s shortest path algorithm
in conjunction with a pre-calculated adjacency matrix for all the four-letter words.
Clearly the adjacency matrix construction takes up the bulk of the time for one search, but if you do multiple searches using the same
adjacency matrix then it becomes more effecient overall.
A more interesting variation would be to allow other edges besides single-letter changes. Edges represending the addition or
removal of a letter could be incorporated into the adjacency matrix, and those edges given different costs than single-letter
change edges. The code that produced the above results assumed all edges had equal costs.
It’s Halloween. I think I’ll go as a dork.