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: 3-letters with a better list (spoiler) by Charlie)

Absolutely, Charlie, if you want to see Mathematica code. I know this isn't particularly useful to super coders. For Mathematica users, I could just send the notebook to anyone interested (do we have email capability via this site?)

A description might be better; I created a graph from the Scrabble list using the one-letter change as the edge rule (built-in function). I took the largest connected component (which eliminated only a few isolated words). Then I created the adjacency matrix (about a million entries for the 3-letter words problem, but awfully sparse) and computed all the diameter paths watching for the entries that stay zero the longest in each row under powers of the matrix.

Mathematica is good at handling sets and has gotten better at sparse matrices (still doesn't hold a candle to Matlab), but at the 4-letter word problem, none of this is going to work since we move from almost 1000 words to over 5000 words. The number of edges in the largest component is over 32,000. However, I do have code that can compute the shortest path spanning tree rooted from a given word. It takes three minutes to do this, so if I let a PC run for about 11 days, I can tell you the longest 4-letter minimal meld paths.

Does anybody have any thoughts on upper and lower bounds? What do we expect to find for the 4-letter case? Any guesses??? I have found a path of 16 words in the 4-letter group, if that helps (assuming Scrabble words).

Edited on January 25, 2005, 9:26 pm

Posted by owl on 2005-01-25 21:22:49