Programming Problem #13
"Martian Boggle"

Martians love word games and play a version of the game Boggle. The Martian alphabet is the same as the English alphabet, with the exception that Y is never used as a vowel. Martian words have zero or more vowel/consonant pairs followed by two vowels; for example, 'epee', 'aria', 'ai', 'azanigoo' and 'uxayoqie' are all Martian words. The surprising thing is that every such combination of letters is a valid Martian word, and hence the Martians have an infinite vocabulary.

Martian Boggle is played using a 4x4 grid of letters. The goal is to find as many distinct words as possible within the grid. A word is in the grid if it is possible to spell the word by starting at a square and then moving either vertically, horizontally or diagonally one square at a time, without reusing a square. (A square may be used at most once per word, but it may be used again in a different word.) Your job is to determine the total numbers of words in a grid and find a word of maximum length.

The input consists of one or more grids separated by a blank line. For each grid, find the total number of distinct words in the grid (words that occur multiple times in the grid are only counted once), and find any word of maximum length. Output a line containing the total number of words right-justified in a field of width three, then one space, then any word of maximum length.

Input must be read from the file "prob13.in", and output must be written to the file "prob13.out". All output to the screen will be ignored.

Example Input

<BOF>
suty
kkar
ezzx
pkbu

abcd
efgh
ijkl
mnop
<EOF>

Example Output

  7 ezau
 20 ojifae
A version of this problem originally appeared in the 1986 Rocky Mountain Regionals.

Dr. Eric Shade