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, you may find that it is a consecutive substring of the wordsnake (i.e. completely contained in the wordsnake already constructed) in which case you need not extend the wordsnake or you may choose or have to extend the wordsnake. If you extend it, you may extend it with the whole ith word or any suffix s of the ith word provided the prefix p of the ith word has the properties: ps = ith word and p is identical to the suffix of length |p| of the unextended wordsnake. For example, if the current wordsnake is "wombat" and the next word is "bats", then an acceptable new wordsnake would be "wombats" (maximum overlap) or "wombatbats".
The score of the word is the square of the number of letters in the overlap with the wordsnake before the wordsnake was added in. In the example above, "bat" would get 0 points when extending as "wombatbats" but would get 9 points for "wombats" because of the three letter overlap. 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 of the words and the position
of each word.
The architect will then construct them into a wordsnake.
For example, if you say:
wombat, 0
bats, 6
that will give the wordsnake "wombatbats" and a score of 0.
On the other hand,
wombat, 0
bats, 3
will give "wombats" and a score of 9.
You win if you get the highest score.
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 (no start position information is included here, but pack as tightly as possible)
Here is a calculation of an upper bound on the wordsnakes.
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.
antiestablishmentarian, 0
a, 0
an, 0
ant, 0
ties, 2
stab, 5
tab, 6
I, 3
me, 13
men, 13
tar, 16
establish, 4
establishment, 4
establishmentarian, 4
establishmentarianism, 4
antiestablishment, 0