Word ladders - source code

This is a resource of the wordgame-programmers@egroups.com mailing list.



Click to subscribe to wordgame-programmers

Iterative deepening means repeatedly calling a fixed depth search routine with increasing depth until a time limit is exceeded or maximum search depth has been reached. The advantage of doing this is that you do not have to choose a search depth in advance; you can always use the result of the last completed search. Also because many position evaluations and best moves are stored in the transposition table, the deeper search trees can have a much better move ordering than when starting immediately searching at a deep level. Also the values returned from each search can be used to adjust the aspiration search window of the next search, if this technique is used.

• ladder & letterbank code in C/
  A dynamic programming solution (in plain C) to find lowest-cost ladder, allowing either letterswaps (scoring 1 pt) or letterbanks (scoring 3 pts).

  What is a letterbank? - take the unique letters in a word, and find another word which is made from only those letters, with each letter appearing at least once. Letters may be used multiple times. For example, ACCOUNT can be letterbanked to COCOANUT.

  The code pre-builds a table of all links from a word (whether transformed by letterswapping or letterbanking) and replaces word strings with indexes representing the words. The shortest-path solution works in graph space, and does not handle words at the letter level at all.

• ladder_thomas/
  Steve Thomas's C code to find shortest and toughest! word ladders. (Steve is also a writer of competitive Scrabble programs)
• ladder code in C++/
  C++ source to do a breadth-first search using C++ libraries
• pcladder/
  Complete source for a word-ladder game for PCs in non-portable Pascal. From PC Magazine.
• ladder/
  Portable ISO Pascal source for fixed length ladders (4 and 5 letters), with machine translation into C. (A good C translation would restructure the code and make the game length independent) Includes p2c translator for good measure!
  Fairly readable (in the pascal version) and good for learning the breadth-first-search algorithm. Fast.
• sgb/
  This is a general purpose package for graph algorithms from programming Guru Don Knuth. Like all his work, it is brilliant, but he doesn't have a clue about making it accessible (unless of course you install tangle, weave, cweb, Tex, etc etc first). If only he had written a webtohtml converter, life would have been so easy. Anyway, this is basically the same algorithm as the example above, but I don't recommend it for beginners. However, advanced programmers who have complex graph algorithm problems to handle, related to words, may find this an invaluable tool.
• rfrank/
  Similar to Knuth's algorithm, but a little more readable, is Roger Frank's code to implement word ladders in C⁺⁺
• craigcopi/
  Perl script to solve word ladders.
• Warwick Allison's word-ladder program
  Uses a pre-built trie.
• potm/old-problems/doublets.txt
  An old entry for the "Programmer of the Month" competition was just this problem. Unfortunately I can't find the old solutions.

• Switchback
  Like ladders, but allows reversals along with letter changes. In Perl.
• SuperDuperGhost (What is Ghost?)
  Mactech competition entries.
• Ghost
  Ghost for the Macintosh, in C. Has some strategy, not just random plays.
• Juxtaposition