The Wordsnake
Solution


The total number of characters in the original words is 254.

I found my solution using a program that I wrote. I tried using a sort of greedy algorithm to get started, then tried looking at all the simple ways of modifying the string that would improve the score, such as swapping two words, or breaking it at three places and reordering the pieces. Even then I had to hit it over the head with a random variation from time to time to get it restarted when it prematurely thought it had found a solution it couldn't improve. The solution I found can be summarized in the following list:

        Overlap  Score  Total  Words

           1       1      1    inven T errible
           3       9     10    terri BLE mish
           4      16     26    ble MISH apen
           3       9     35    misha PEN ultimate
           2       4     39    penultima TE nse
           2       4     43    ten SE em
           2       4     47    se EM erge
           5      25     72    e MERGE r
           3       9     81    mer GER iatric
           4      16     97    geria TRIC ky
           1       1     98    trick Y es
           2       4    102    y ES sential
           2       4    106    essenti AL ly
           1       1    107    all Y et
           2       4    111    y ET ernal
           2       4    115    etern AL as
           3       9    124    a LAS ting
           5      25    149    la STING er
           3       9    158    stin GER und
           3       9    167    ger UND erdevelop
           4      16    183    underdev ELOP ed
           3       9    192    elo PED iatric
           4      16    208    pedia TRIC e
           3       9    217    tr ICE r
           3       9    226    i CER tain
           2       4    230    certa IN credible
           3       9    239    incredi BLE nd
           4      16    255    b LEND ing
           3       9    264    lend ING rate
           4      16    280    ing RATE s
           3       9    289    ra TES silate
           4      16    305    tessi LATE r
           3       9    314    la TER restrial
           5      25    339    terres TRIAL s
           1       1    340    trial S udden
           3       9    349    sud DEN ude
           2       4    353    denu DE nse
           2       4    357    den SE a
      

Dennis Shasha's solution is:

        Overlap  Score  Total  Words

           1       1      1    inven T ense
           2       4      5    ten SE em
           2       4      9    se EM erge
           5      25     34    e MERGE r
           3       9     43    mer GER iatric
           4      16     59    geria TRIC ky
           1       1     60    trick Y es
           2       4     64    y ES sential
           2       4     68    essenti AL ly
           1       1     69    all Y et
           2       4     73    y ET ernal
           2       4     77    etern AL as
           3       9     86    a LAS ting
           5      25    111    la STING er
           3       9    120    stin GER und
           3       9    129    ger UND erdevelop
           4      16    145    underdev ELOP ed
           3       9    154    elo PED iatric
           4      16    170    pedia TRIC e
           3       9    179    tr ICE r
           3       9    188    i CER tain
           2       4    192    certa IN credible
           3       9    201    incredi BLE mish
           4      16    217    ble MISH apen
           3       9    226    misha PEN ultimate
           2       4    230    penultima TE rrible
           3       9    239    terri BLE nd
           4      16    255    b LEND ing
           3       9    264    lend ING rate
           4      16    280    ing RATE s
           3       9    289    ra TES silate
           4      16    305    tessi LATE r
           3       9    314    la TER restrial
           5      25    339    terres TRIAL s
           1       1    340    trial S udden
           3       9    349    sud DEN ude
           2       4    353    denu DE nse
           2       4    357    den SE a
      

Note that the solutions are essentially identical. The strings really differ only in their placement of the "superstrings": (Invent), (Tense...Incredible), (Blemish...Penultimate), (Terrible) and (Blend...Sea).

Back to The Wordsnake Puzzle.


Last revised on 10 October 2000.