Previous "Word Meld" puzzles consisted of a pair of words for which to find the shortest sequence of common words, each differing from the previous by only one letter, which began with one word of the pair and ended with the other.
For this problem, find the pair of words that has a shortest solution of maximum possible length.
(In reply to
re: thoughts by owl)
Finding the shortest path between two points is most efficiently done
with a depth-first or breadth-first search of the spanning tree.
In our case, since we are searching for the shortest path between every
two pair of points, if we perform a breadth-first search on the word
list, we can avoid much redundant computation (depth-first search often
searches sub-optimal paths, wheras breadth-first does not). The
algorithm goes something like this:
Take a path (could be just one word) in the list and find all length
n+1 paths. If a smaller path between the beginning word and the
end word exists, delete that path(keeping our path list alphabetized by
path start then path end allows this check to be efficient).
Otherwise add the path to the path list (our original path remains in
the path list). If we iterate completely through the path list
without adding a path, we have found all shortest paths, and now we
simply have to find the longest path in our path list.
With a
large data set, this program will require a running time of order
(branching factor * dictionary size * branch generation speed), and
will likely be too large to fit in main memory.
A few
optimizations can make this problem tractable. For instance, we
can store our initial paths of one edge as a tree in main memory to
provide fast branch generation, and we can store paths in our file in
reverse order, save the first element (i.e. 1->2->3->4 is
stored as 1 4 3 2) This way, the last element is easily
accessable for comparison. We can also find optimal paths for
each start word separately (though we still need to generate our
complete 1-edge-path list). If we take this approach, we also
note that the shortest path from A->B is the inverse of the shortest
path B->A, so we can partially fill in the path lists of other words.
Edited on January 22, 2005, 9:11 pm
re(2): thoughts
