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 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. 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.

Saro Getzoyan's solution (best in 2003)