May 98 Challenge
Volume Number: 14
Issue Number: 5
Column Tag: Programmer's Challenge
May 98 - Programmer's Challenge
by Bob Boonstra, Westford, MA
EggLob
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)
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 latest CodeWarrior environment.
Solutions may be coded in C, C++, or Pascal. Thanks to Ernst Munter for suggesting
this Boggle variant.
Three Months Ago Winner
One more time we congratulate Ernst Munter (Kanata, Ontario) for submitting the
winning Challenge entry, this time in the February Image Decoder Challenge. The
Challenge was to read a GIF image from a file, decode it, and return an offscreen
GWorld containing the image. Ernst's code was about 5% faster than the second place
entry by Patrick Varilly, and beat Patrick's entry in all but one of the test cases I
used.
A couple of keys to the extra speed in Ernst's code. First, notice that almost all of the
code is part of methods in the GIF class, and that all of those methods are inlined. This
wouldn't be a good general technique for all C++ code, but it provided an edge in this
application. Second, look closely at some of the loop constructs. For example, the
portion of the PutMore method dealing with the common case, where all of the decoded
pixels map into the current image line, compiles as follows with full speed
optimizations:
char* newDest=dest+len;
...
dest=newDest;
00000014: 7C050378 mr r5,r0
00000018: 88040006 lbz r0,6(r4)
0000001C: 9C05FFFF stbu r0,-1(r5)
stp=stp->prefix;
00000020: 80840000 lwz r4,0(r4)
00000024: 28040000 cmplwi r4,$0000
00000028: 4082FFF0 bne *-16 ; $00000018
The assignment via the predecremented pointer dest compiles to a single Store Byte
With Update (stbu) instruction, making this short loop considerably tighter than
other possible constructs. Very nice.
Patrick commented in his code that close to half of his execution time is spent in fread.
I remember having the same problem at least once when I competed in the Challenge
where I resorted to writing a streamlined version of fread. None of the entries to this
month's Challenge tried that technique, though.
Eleven different GIFs were used to test the solutions to this Challenge. The GIFs ranged
in size up to 1100x800 pixels, and up to 500KB in length. The table below lists the
total execution time in milliseconds for five selected test cases and the time for all test
cases combined. It also lists code size, data size, and the programming language used
for each entry. The number in parentheses after the entrant's name is the total
number of Challenge points earned in all Challenges to date prior to this one (Table 1).
Top Contestants
Here are the Top Contestants for the Programmer's Challenge, including everyone who
has accumulated more than 10 points during the past two years. The numbers below
include points awarded over the 24 most recent contests, including points earned by
this month's entrants.
1. Munter, Ernst (220 points)
2. Boring, Randy (73)
3. Cooper, Greg (61)
4. Lewis, Peter (51)
5. Mallett, Jeff (50)
6. Nicolle, Ludovic (44)
7. Rieken, Willeke (27)
8. Antoniewicz, Andy (24)
9. Gregg, Xan (24)
10. Murphy, ACC (24)
11. Day, Mark (20)
12. Higgins, Charles (20)
13. Hostetter, Mat (20)
14. Studer, Thomas (20)
15. Hart, Alan (14)
16. O'Connor, Turlough (14)
There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2)
being the first person to find a bug in a published winning solution or, (3) being the
first person to suggest a Challenge that I use. The points you can win are:
1st place 20 points
2nd place 10 points
3rd place 7 points