Re: Doublet fun

At 07:31 PM 9/4/01 -0500, Matthew Wickline wrote:
>I came across a puzzle. The type of puzzle is called "Doublet" and was
>invented by the wonderful Charles Dodgson (Lewis Carroll). You start
>with one word. You change one letter in that word to create another
>word. You change one letter in the resulting word to arrive at a third
>word. The goal is to keep changing one letter at a time and have a
>word at every stage as you move from a starting word to a goal word,
>using either a pre-determined number of intermediate words or as few
>intermediate words as possible.
>[snip]
>I thought folks might find fun with perl in seeing how elegant a
>program they can write to find the "best" solution for
>
>     S N A K E
>     : : : : :
>     : : : : :
>     : : : : :
>     C A M E L
>
>Maybe you want a program that finds the shortest solution the fastest.
>Maybe you want a program that finds the shortest solution with the
>most common words (none of those words we've never heard of before).
>
>Another challenge might be to write a program that finds particularly
>hard pairs of words... either they require oodles of steps, or they
>can be done in fewer steps, but only by using really obscure words.
>
>To aid in your fun, please find a Big-Ass list of five letter words
>(and non-words) with word-commonality, and definition information in
>many cases and assorted other meta-data. The list contains over
>120,000 five letter entries.
>
>     http://wickline.org/fivers.tar.gz

There are some weird words in there.  By using them, I was able to come up 
with 6 solutions with a separation of 5 words.  Each of them contained 
several words that I consider 'cheating'.

There are no solutions using Solaris /usr/dict/words.  Using the ENABLE 
word list, there are 3 solutions with a separation of 9 words:

SNAKE                   SNAKE                   SNAKE
SHAKE                   SHAKE                   SPAKE
SHAPE                   SHAPE                   SPIKE
CHAPE                   CHAPE                   SPIKS
CHAPT                   CHAPS                   SPINS
COAPT                   CHOPS                   SAINS
COMPT                   COOPS                   CAINS
COMET                   COMPS                   CARNS
COMES                   CAMPS                   CARES
CAMES                   CAMES                   CAMES
CAMEL                   CAMEL                   CAMEL

The distribution of other solutions (number of solutions with a particular 
number of intervening words) is:

10: 30
11: 82
12: 155
13: 152
14: 143
15: 114
16: 107
17: 83
18: 46
19: 45
20: 18
21: 21
22: 6
23: 7
24: 3
25: 2
26: 1
27: 1

Every single solution has CAMES as the penultimate word.  I have no problem 
with this as my wife and I work in stained glass :-)

The solution is a program I came up with the last time this game was played 
on this list, which means I'm not posting it because I saw some much better 
ones posted shortly afterward :-)  My approach was to form two trees of 
words starting from the beginning and end, each layer formed from the words 
that differ by one letter from the node above, and look to see when a word 
in one tree is found in the other.
--
Peter Scott
Pacific Systems Design Technologies
http://www.perldebugged.com

• Doublet fun by Matthew Wickline
• Re: Doublet fun by Peter Scott