Wordsnakes

Dennis Shasha

Omniheurist Course

Computer Science


 

Description

Given a collection of words, a wordsnake is formed from some permutation of the list as follows. The wordsnake starts with the first word on the list. When you arrive at the ith word on the list, find that it is a consecutive substring of the wordsnake (i.e. completely contained in the wordsnake already constructed) or that its prefix of length k is identical to the suffix of length k of the wordsnake. Note that k could be 0. The score of the word is the square of the number of letters in the overlap with the wordsnake.

For example, the words "house" and "sea" have an overlap of 2 letters (hence a score of two squared or 4) in the given order because the suffix "se" of "house" is the prefix of "sea". On the other hand "beret" and "timber" have an overlap of 1 (and score of 1) in the given order because of the letter "t" but have an overlap of 3 (and score of 9) in the reverse order because of the letters "ber". Sometimes there is an overlap of zero characters as in "sea", then "house". So, some wordsnakes have higher scores than others.

In this contest, you will be presented with a list of 100 words which I will generate on the spot (and then maybe edit). Your job is to find a permutation and then construct them into a wordsnake having the highest score. You win if you do so. Here is the current best code for a slightly different problem (no containment was allowed).

On this list here was the best answer by Ben Wellington.

Here is a generator for words on a two letter alphabet.
Run it by typing
k wordsnakegenabab

Here is a generator for words from the unix dictionary.
Run it by typing
k wordsnakegenreal

Here is a good word in English found by Karven Lam: antiestablishmentarianism.
1 a
4 an
9 ant
16 ties
16 stab
9 tab
1 I
4 me
9 men
9 tar
81 establish
169 establishment
324 establishmentarian
441 establishmentarianism
289 antiestablishment
484 antiestablishmentarian