May 1998 Programmer's Challenge
EggLob
Mail solutions to:
<mailto:progchallenge@mactech.com>,
and copy
<mailto:bob_boonstra@mactech.com>
Due Date: 11:59PM, ET, 1 May 1998
What could he mean by "EggLob", you ask. Well nothing, except that
it is an anagram of "Boggle®, the Parker Brothers game that is
the inspiration for this month's Challenge. Boggle is played with 16
six-sided letter cubes and a 4x4 tray into which the cubes are
shaken. The object is win as many points as possible by joining
letters horizontally, vertically, or diagonally to form words. Longer
words win more points. This month your Challenge is to solve a game
like Boggle, with a few twists.
The prototype for the code you should write is:
#if defined (__cplusplus)
extern "C" {
#endif
long Boggle(
long dimension, /* puzzle is square, of size dimension, 4x4 to
7x7 */
char puzzle[], /* letter at (row,col) is in
puzzle[col+dimension*row] */
long dictSize, /* number of words in dictionary */
const char *dictionary[], /* legal words to use */
char *wordsFound[], /* return pointers to the words you found
*/
void *privStorage /* 20MB of storage for your use */
);
#if defined (__cplusplus)
}
#endif
Our first twist on the standard Boggle game is that the puzzle
dimension will vary from 4x4 up to 7x7, inclusive. Your Boggle
routine will provided the puzzle, a dimension x dimension array of
characters. The second twist is that you are allowed to cheat, up to
a point, anyway. You can cheat by picking up any of the cubes and
exchanging it with any other cube. You can do this as many times as
you like. You can exchange cubes, however, you cannot turn a cube so
that a different letter is on top. (I've reduced your temptation to
cheat in this fashion by not telling you what is on the other five
faces of a cube.) Once you have rearranged the puzzle to your liking,
you should find as many words as possible from the dictionary of
dictSize words, copy the pointers to the words you find from the
dictionary into the wordsFound array, and return the number of words
you found. Your rearranged puzzle should replace the original puzzle
and be returned to the calling routine.
Words are formed from letters that are adjacent vertically,
horizontally, or diagonally. No letter from the puzzle may be used
more than once within a single word. Words within other words are
legal and scored separately. For purposes of matching against the
dictionary and for scoring, the letter "Q" represents the two letters
"QU". The dictionary may vary in size and content from puzzle to
puzzle.
Words are awarded points based on length. No points are scored for
words of fewer than 3 letters. Words of 3 or 4 letters earn 1 point,
words of 5 letters earn 2 points, words of 6 letters earn 3 points,
words of 7 letters earn 5 points, and words of n letters (n>7)
earn 5 + 6*(n-7) points. Points are deducted based on how long your
Boggle routine executes; 1 point will be deducted for every 20ms that
your code executes on my 8500/200. Negative point totals are
possible. Entries that do not return after a reasonable time (e.g., 5
minutes) will be terminated and assigned the associated negative
score. Entries that claim to have found words that cannot legally be
formed using the rearranged puzzle will similarly penalized.
The Challenge winner will be the entry that accumulates the
largest point total in a sequence of puzzles.
The privStorage parameter will point to 20MB of preallocated
storage for your use. The privStorage will be initialized to zero
prior to the first call to Boggle. The same privStorage value will be
provided on each subsequent call, and the contents of your private
storage will persist from one call to the next.
This will be a native PowerPC Challenge, using the CodeWarrior Pro
(Release 2) environment. Solutions may be coded in C, C++, or Pascal.
Thanks to Ernst Munter for suggesting this Boggle variant.
|