Feb 98 Challenge
Volume Number: 14
Issue Number: 2
Column Tag: Programmer's Challenge
Programmer's Challenge
by Bob Boonstra, Westford, MA
Image Decoder
This month's Challenge is much easier to state than it will be to implement. Your task
this month is to write a decoder for Graphics Interchange Format images. GIF is a data
stream-oriented file format used to define the transmission protocol of LZW-encoded
bitmap data. Your code will read a file containing a GIF and draw the image in an
offscreen graphics world. There are two versions of the GIF specification; this
Challenge includes only the earlier and more common GIF87a format, not the GIF89a
format. The format description is too long to include here, but you can find the GIF87a
specification
at:ftp://ftp.ncsa.uiuc.edu/misc/file.formats/graphics.formats/gif87a.doc
Other useful information on graphics formats in general is available
at:http://www.cis.ohio-state.edu/hypertext/faq/usenet/graphics/fileformats-faq/top
.html
The prototype for the code you should write is:
GWorldPtr ReadImage(FILE *inputFile);
The inputFile will have been opened for you in binary mode by the calling routine.
ReadImage should read and parse the image, create a GWorld with the appropriate color
table, draw the image in the GWorld, and return a GWorld pointer to the calling
routine. The solution that correctly decodes a variety of images in the least amount of
execution time will be the winner.
I thought for some time about the Compuserve / Unisys / LZW patent controverty
before selecting this topic for the Challenge. The LZW algorithm used in GIF
compression is patented by Unisys, and Unisys requires that any commercial software
product that uses this algorithm, including software that reads GIF images, requires a
license from Unisys. Freely distributed software does not require a license. Since the
Challenge doesn't result in a software product, much less a commercial product, I
decided to go ahead with this exploration of decoding efficiency.
This will be a native PowerPC Challenge, using the latest CodeWarrior environment.
Solutions must be coded in C, C++, or Pascal. This Challenge was suggested by Peter
Lewis, who earns 2 Challenge points for the suggestion.
Three Months Ago Winner
Congratulations to Jeff Mallett (Boulder Creek, CA) for submitting the winning
entry to the Pente(tm) Challenge. The objective was to accumulate, in minimum
execution time, the most points in a round-robin tournament of the board game
Pente(tm). With only three entries, the tournament required only six games for each
player to compete against each other player twice, once playing first and once playing
second. Both the winning entry and the third-place entry by Randy Boring employed an
alpha-beta search technique to find the best move, and both entries were successful in
winning most of their games. Jeff's entry, however, was more efficient about pruning
the search tree and therefore required significantly less execution time than Randy's
entry. Since a point was deducted for each second of execution time, the winning entry
lost significantly fewer points for inefficiency. In addition, the scoring algorithm in
Jeff's AddStone routine takes advantage of all three methods of scoring points:
captures, winning by placing 5 stones in a row, and leaving sequences of 4-in-a-row
on the board at the conclusion of a game. His solution earned more points as a result,
even though it won the same number of games as Randy's.
The table below lists the number of tournament wins, points earned, cumulative score,
code size, data size, and programming language 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.
Name Wins Points Score Code Data Language
Jeff Mallett (74) 3 33 32.03 4872 7923 C
Sebastian Maurer 0 10 9.97 4860 208 C++
Randy Boring (66) 3 23 -374.90 7672 2649 C
Top 20 Contestants
Here are the Top Contestants for the Programmer's Challenge. The numbers below
include points awarded over the 24 most recent contests, including points earned by
this month's entrants. The scores have been adjusted to correct an error made in
assigning points for the Stratego Challenge printed in the November issue.
Rank Name Points
1. Munter, Ernst 200
2. Boring, Randy 73
3. Cooper, Greg 61
4. Lewis, Peter 59
5. Mallett, Jeff 50
6. Nicolle, Ludovic 48
7. Murphy, ACC 34
8. Gregg, Xan 33
9. Antoniewicz, Andy 24
10. Day, Mark 20
11. Higgins, Charles 20
12. Larsson, Gustav 20
13. Studer, Thomas 20
14. Gundrum, Eric 15
15. Hart, Alan 14
16. O'Connor, Turlough 14
17. Picao, Miguel Cruz 14
18. Saxton, Tom 12
19. Cutts, Kevin 11
20. 8-way tie 10
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
4th place 4 points
5th place 2 points
finding bug 2 points
suggesting Challenge 2 points
Here is Jeff's winning solution:
MyPente.c
Copyright © 1997 Jeff Mallett
//
// Do a depth=1 search to sort moves. Then do a higher
// depth alpha-beta search to select the best move.
//
// Plays for score rather than to win. For example,
// doesn't try to win by getting 5 captures since
// there is no score incentive for this. It could be
// retuned to play for a win instead.
#define SEARCH_DEPTH 4
_FRIEND = 0x0001,
_ENEMY = 0x0002,
_EMPTY = 0x0004,
_WALL = 0x0008
#define BORDER 1
#define BORDERS 2
#define INFINITY 32600
#define NA 0
#define MAX_CELLS (31 + BORDERS) * (31 + BORDERS)
#define ESTIMATE_PLUS 1
#define WIN 2000
#define CAPTURE_SCORE 240
#define VULNERABLE 150
static short CHAIN_SCORE2[3][3] = { //[color][open]
{ NA, NA, NA },
{ -1, -9, -2 }, // FRIEND
{ 1, 9, 2 } // ENEMY
};
static short CHAIN_SCORE3[3][3] = { //[color][open]
{ NA, NA, NA },
{ 3, 16, 40 }, // FRIEND
{ -2,-10,-30 } // ENEMY
};
static short CHAIN_SCORE4[3][3] = { //[color][open]
{ NA, NA, NA },
{ 230, 240, 250 }, // FRIEND
{ -150,-155,-160 } // ENEMY
};
static short CHAIN_SCORE5[3] = { //[color]
NA, WIN, -WIN
};
// 1 2 3 4
static short BLOCK_SCORE[5] = { NA, 0, 14, 14, 22};
static short THREATS[] = {
NA, NA,
25, // 2: tria
30, // 3: half-open four
350, // 4: double trias
370, // 5: tria + half-open four
450, // 6: tessera or 2 half-open fours
500, 500, 500, 500, 500, 500, 500, 500, 500, 500
static short gPreScore[MAX_CELLS], gEstimates[MAX_CELLS];
static short *gEstimatesStart, *gEstimatesEnd;
static short gBoard[MAX_CELLS], *gBoardStart, *gBoardEnd;
static short *gFirstStone, *gLastStone;
static short *gKillers[SEARCH_DEPTH], gPreviousThreats;
static short gDirections[8], *gDirectionsEnd;
static short gMoveNum, gScore, gStartDepth;
static short gBoardHalfSize, gSideLength, gBoardMax;
static short gCumCapturesFriend, gCumCapturesEnemy;
static short gAdjustment, gSE;
#define ADJUST(a) ( (a) + gAdjustment )
#define TRANSLATE(x, y)
(gSideLength * ADJUST(y) + ADJUST(x))
#define GET_INDEX(p) ((p) - gBoard)
#define GET_X(i) ( ((i) % gSideLength) - gAdjustment )
#define GET_Y(i) ( ((i) / gSideLength) - gAdjustment )
#define UPDATE_ENDPOINTS(pSq, a, b)
if (pSq < a) a = pSq;
if (pSq > b) b = pSq
#define OPPONENT(side) (3 - (side))
#define OCCUPIED(x) ((x) & (_FRIEND | _ENEMY))
#define EMPTY(x) ((x) == _EMPTY)
// gChanges -- Array of unsigned longs containing data to
// undo moves
// list of:
// terminated by a OL