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.

This seems a problem that's best approached through a computer solution.

It probably goes without saying this is really several problems: one for 4-letter words, one for 5-letter words, etc.  Then the best solutions for all the cases would be compared to get the best (maximum length) of all of these.

A given word can be connected, through change of one letter, to various other words, giving rise to a tree structure.  However, the branches of the tree may loop back to some prior point in a given sequence, leading to a closed loop.

It would seem a good start to create an index for each word, to all the words to which it can be connected.  Then the branches can be traversed more easily (quickly).

But then what does one look for?  At first thought, you'd look for words that could be a dead end on a meld, or by its traditional name, ladder. (For example, the word BOOK is not a dead end, as it can connect COOK and BOOT.) Then, for each such dead end found, traverse the branches leading from it until another dead end is reached or a loop back to a prior point in the word ladder.  However, the longest required chain might not end in a dead end, but rather in a loop at either end (topologically looking like a dog bone--a linear string in the middle, with a loop at either end).  Of course it would have loops and branches leading out from the middle also, to be investigated to see if they are longer.  So we can't just look for strict dead ends as starting places.

And once we find such a sequence, it has to be verified as the shortest sequence (meld, ladder, chain, whatever you want to call it) connecting the two end words.

An example of a loop, for example, would be: book, bock, back, bank, bonk, conk, cook ... and then back to book.  But if, say, BANK's connection to BAND (not in this loop) started a string that led to another such loop, it could be part of the answer, for either the word cook or book, as either would take three steps to get to BANK, and from there continue on to the other end.

 

Edited on January 22, 2005, 4:06 pm

Posted by Charlie on 2005-01-22 15:53:45