Word ladder is a game where, given two words, the player should find the shorter way to go from one word to the other changing only one letter at a time, always using valid words.
For example: from tap to bat: tap -> cap -> cat -> bat
In the last London Python Code Dojo we decided to solve this problem, limited to words of 3 letters.
After the Python Dojo I found the problem interesting and I did a quick code to paint a graph with all the 3 letter words to see the isolated words. For English, Spanish and Catalan, based on the dictionaries provided by Debian (packages wcatalan, wspanish and wbritish).
The generated graphics per language:
English:
In English, and based in the dictionaries from Debian, all the words are connected except “ems” and “emu” (see extra information).
Spanish:
In Spanish, all words are connected but “psi” and “phi”.
Catalan:
All words are connected!
Extra information:
I commented it in the Python-UK list, where we had a nice thread discussing, where even comments about Latin or Greek appeared (like the Vatican dictionary or here).
One more thing: Wikipedia says that Donald E. Knuth found this problem interesting. He studied the same that I did for 5-letter words. I should read his books.
Last thing: hats off for networkx Python module. We didn’t know how to use it and with the great documentation we added all the nodes and edges to the “graph” and asked for the shortest paths and graphics. Amazing!
Leave a Reply