WORDSNAKE
Seek High Scoring Wordsnakes

WORDSNAKE is a FORTRAN90 program which tries to find a good solution to the "Wordsnake Puzzle".

WORDSNAKE is given a list of words and tries to arrange them in a list so that the end of one word has maximum overlap with the beginning of the next word. The entire list is called a "wordsnake", and is scored by squaring the overlaps of each consecutive pair, and adding. We allow the wordsnake to "wraparound", so there's one extra score for overlap from the last word to the first.

Usage:

wordsnake wordlist

• wordlist is a file containing a list of words, one per line, to be made into a wordsnake.

Licensing:

The computer code and data files made available on this web page are distributed under the GNU LGPL license.

Languages:

WORDSNAKE is available in a FORTRAN90 version.

Related Data and Programs:

ANAGRAM, a C++ program which determines anagrams of a string, by James Cherry;

PUZZLES, FORTRAN90 programs which were used to solve various puzzles.

SUBANAGRAM, a FORTRAN90 program which finds words which are anagrams formed from some of the letters of a given master word.

WORDS, a dataset directory which contains lists of words;

Reference:

1. Dennis Shasha,
   Wordsnakes,
   Dr Dobb's Journal,
   July 2000, pages 143-144.

Source Code:

• wordsnake.f90, the source code;

Examples and Tests:

• wordsnake_input.txt, a sample wordlist;
• wordsnake.txt, the output file.

List of Routines:

• MAIN is the main program for WORDSNAKE.
• FILE_RECORD_COUNT counts the number of records in a file.
• FILE_RECORD_READ reads the records in a file.
• GET_UNIT returns a free FORTRAN unit number.
• I4_MODP returns the nonnegative remainder of integer division.
• I4_RANDOM returns a random integer in a given range.
• I4_SWAP switches two integer values.
• I4_SWAP3 swaps three integer values.
• I4_UNSWAP3 unswaps three integer values.
• I4_WRAP forces an integer to lie between given limits by wrapping.
• I4VEC_IDENTITY sets an integer vector to the identity vector A(I)=I.
• LOWER returns a lowercase version of a string.
• OVERLAP_TABLE computes a table of the overlap between pairs of words.
• PERM_RANDOM selects a random permutation of N objects.
• S_OVERLAP determines the overlap between two strings.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• UPPER returns an uppercase version of a string.
• WORDSNAKE seeks a high scoring permutation of a set of words.
• WORDSNAKE_PRINT prints a wordsnake.
• WORDSNAKE_SCORE computes the score for a given wordsnake.
• WORDSNAKE_SEARCH_GREEDY constructs a wordsnake using a greedy algorithm.
• WORDSNAKE_SEARCH_INSERT tries to improve the score by inserting a word.
• WORDSNAKE_SEARCH_SWAP2 tries to improve the score by swapping 2 words.
• WORDSNAKE_SEARCH_SWAP3 tries to improve the score by swapping 3 words.
• WORDSNAKE_SEARCH_TRANSPOSE tries to improve the score using transpositions.