Archived

This topic is now archived and is closed to further replies.

LordN

Word Game Algorithm

Recommended Posts

I am writing a simple word game, where the computer randomly selects two four letter words, and the object is to go from the first word to the second word by changing only one letter at a time, like this: Go from "help" to "this" help hell hail tail tain (it''s a word) thin this Every step has to be a real word. I have a text file containing thousands of four letter words. My question is this: how can I write an algorithm that can automatically solve any such puzzle?

Share this post


Link to post
Share on other sites
A* will do it. Each word is a node. You generate a graph linking up all the words. A* will find the shortest path from one node in the graph to another. This could be extremely slow since each node would have dozens of edges to other nodes.

In addition, you could preprocess the graph and generate a 2D table. Each entry in the table is what word to go to next in order to get from the row''s word to the column''s word. The table would be huge (megabytes), but the results would be nearly instantaneous.

Share this post


Link to post
Share on other sites
Calling it A* is like calling a peanut butter sandwich ... something very complicated. Also, isn''t it more like Dijkstra''s? You can''t really say which node is going to get there first, heuristic won''t save you...

Just think of a tree, where each word node has children that are only 1 letter off for the parent (neighboring nodes in a search). No child node may have the same word as a parent (No doubling back in a search). Eventually, Mr. Tree will find the target word in one of the child nodes. That == "yey" condition.

Share this post


Link to post
Share on other sites
quote:
Original post by TSwitch
Calling it A* is like calling a peanut butter sandwich ... something very complicated. Also, isn''t it more like Dijkstra''s? You can''t really say which node is going to get there first, heuristic won''t save you...

Just think of a tree, where each word node has children that are only 1 letter off for the parent (neighboring nodes in a search). No child node may have the same word as a parent (No doubling back in a search). Eventually, Mr. Tree will find the target word in one of the child nodes. That == "yey" condition.


Building that tree could be, well, ugly--consider: hall->half->calf->call->hall is suddenly circular, four layers deep. Also, since hall can be a child of call and half, there''s a parenting issue. What you''d need to do, I guess, is to do a breadth-first search to build the tree dynamically (that is, use the given starting word as your root node; you can''t build a general-purpose tree beforehand); if a word is already in the tree, then it just isn''t added. This requirement (searching the tree to make sure you''re not putting in an already extant word) slows things down considerably. Doing some pre-processing to build up the possible relationship table would help; when a word is added to the tree, it should be removed from the table--this eliminates the need for searching the tree. In that case, it basically boils down to a breadth-first search (Dijkstra''s, as suggested) powered by a prebuilt table.

I agree that A* is very wrong for this problem--A* works for acyclic, weighted graphs (with a decent heuristic); this, however, is a cyclic, non-weighted graph with no good heuristic possible.

Hope that helps.

-Odd the Hermit

Share this post


Link to post
Share on other sites
quote:
Original post by Odd the Hermit
I agree that A* is very wrong for this problem--A* works for acyclic, weighted graphs (with a decent heuristic); this, however, is a cyclic, non-weighted graph with no good heuristic possible.



Oh yeah. I forgot about that damn heuristic.

Share this post


Link to post
Share on other sites