word-ladder

Another university group project, this time for a course in artificial intelligence. The program’s purpose is solving word ladder puzzles - getting from one word to another by changing a single letter at a time, with every intermediate step a real word (cold, cord, word, ward, warm). The real point of the program was to explore two very different search strategies against the same problem and compare them.

The A* version is the more straightforward strategy. Each node is a word, its neighbors are every word in the dictionary one letter away, and the heuristic is Hamming distance to the target: how many letters still differ, which never overestimates the steps remaining, since a step can only fix one letter at a time. Filtering the dictionary down to words of the right length first keeps the branching manageable.

The genetic algorithm approach is more interesting (I think). A chromosome is an entire candidate ladder, start word to end word, with random junk in between; fitness scores each adjacent pair by how close the two words are, rewarding single-letter steps heavily, penalizing repeats, and docking points for length so ladders don’t sprawl. Then the usual operators, plus a few specific to the shape of this problem: growth and shrink mutations that insert or remove a word mid-ladder, seeding the initial population with words one letter off the endpoints, and targeted mutation of whichever link in the chain is the weakest. Most of those are toggles, which is what the comparison scripts exist to test.

The code is here on GitHub.