[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionThe challenge of Word Ladders is to transform one word into another by changing one letter to make a new valid word at each step. For example, we can change CAT to DOG in 3 steps with the sequence CAT, COT, COG, DOG. Here's a program that solves word ladder puzzles. Background & TechniquesWordLadder is another graph searching exercise, this time the vertices are words that differ from adjoining vertices by a single letter. It uses the TDict class introduced in WordStuff1 to access a dictionary of valid words. For faster access, the words of a specific length are read from the dictionary and saved as a text file the first time that length is encountered. The text files are then loaded into WordList, a TStringlist object, as required. Depth-First SearchThe first implementation was a depth first search that uses recursion like this. The recursive routine, MakeDFLadder, takes two parameters - the starting word and the position that was changed to produce that word. The initial call is MakeDFLadder (fromword, 0). When we enter, we'll add the word to the SolutionListBox list, the list that is displayed to the user. We'll loop through WordList looking for valid words that differ from our starting word in only one letter position with that position not the same one we just changed. (This second condition was added to eliminate sequences like DOG, BOG, FOG, JOG, JAG ... which could have been shortened to DOG, JOG, JAG..., etc.) All the words that match and are not already in SolutionListBox list are placed in a temporary sorted stringlist of all candidates. The words are prefixed by the string representation of the number of letter positions that do not match the target word. This has the effect of putting words that that are closest to the solution at the beginning of the list and should lead us to a solution in a shorter time. For example, in our original CAT, COT, COG, DOG example, 02COT (differs from DOG in 2 positions) will appear before 03CAR and 03FAT (differing in all 3 letter positions) in our temporary list. While doing this, we might as well check to see if the difference from the target is one. If so, we have found a solution and might as well stop here. Otherwise, when the temp list is built, we'll loop through, stripping the numeric prefixes and making recursive calls to MakeDFLadder for each entry until a solution has been found (Result is true) or we've processed entire list. If we run out of words and no solution has been found, remove the word from SolutionListBox and exit. This will send back to the preceding level in the recursion. Breadth-First Search.While depth-first searches generally not find the shortest path to a solution, breadth-first will. We are checking all of the possible solutions of length 2, then all of length 3, etc. So if we find a solution at all, we know that there is none shorter. This search is not recursive. At each level we can make a new list of all the words that might lead us to the solution at the next level, we assign a numeric prefix and sort them by closeness to the target as we did with depth-first. Then, if we don't find a solution at this level, assign that next-level list to the current level list and repeat. The new problem is that when we do find a solution, we have no idea of how we got there!. The solution is to carry a "predecessors" list along with each word which contains the information about how we got to it. Then when we get to a solution, that list is the solution to be displayed. I'll leave it for the reader to study the code to see implementation details if interested. There is a common Solveit routine that serves as a wrapper for the code common code to both depth and breadth-first searches. Also the usual provisions to allow the user to stop execution for long searches. A MaxLevel user input field limits the length for both search types. I've provided a listbox with a roughly graded list of other word pairs, including one or two that may have no solutions (or maybe I just haven't allowed them to search deeply enough). Enjoy! Running/Exploring the Program
Suggestions for Further Explorations
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |