WORDSNAKE - Seek High Scoring Wordsnakes

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.

Reference:

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

Files you may copy include:

• wordsnake.f90, the source code;
• wordsnake_prb.f90, a sample problem;
• wordsnake_prb.out, output from the sample problem;

The list of routines includes:

• I_MODP returns the nonnegative remainder of integer division.
• I_SWAP switches two integer values.
• I_SWAP3 swaps three integer values.
• I_UNSWAP3 unswaps three integer values.
• I_WRAP forces an integer to lie between given limits by wrapping.
• 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.
• 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.

Return to the FORTRAN software page.