Apr 00 Challenge
Volume Number: 16
Issue Number: 4
Column Tag: Programmer's Challenge
Programmer's Challenge
by Bob Boonstra, Westford, MA
Text Compression
This month, we've got some very important messages to send. But we're not living in a
world of free bandwidth. In fact, bandwidth in our Challenge world is very expensive,
so expensive that we're asking you to compress our messages and save us a few bytes.
The prototype for the code you should write is:
void * /* yourStorage */ InitCompression(void);
long /* compressedLength */ CompressText(
char *inputText, /* text to be compressed */
long numInputChars, /* length of inputText in bytes */
char *compressedText, /* return compressedText here */
const void *yourStorage /* storage returned by InitCompression */
);
long /* expandedLength */ ExpandText(
char *compressedText, /* encoded text to be expanded */
long compressedLength, /* length of encoded text in bytes */
char *expandedText, /* return expanded text here */
const void *yourStorage /* storage returned by InitCompression */
);
void TermCompression(
void *yourStorage /* storage returned by InitCompression */
);
For this Challenge, you need to provide the four routines indicated above. Your
InitCompression and TermCompression routines will be called only once each, at the
beginning of the test and at the end of the test, respectively. InitCompression should
allocate and return a block of yourStorage where you initialize any information needed
by your compression and expansion routines. That storage will be passed back to you
unchanged each time you are asked to compress or decompress text. TermCompression
will be called at the end of the test and should deallocate the block of yourStorage to
avoid a memory leak.
In between the calls to InitCompression and TermCompression, the test code will make
multiple calls to CompressText and ExpandText with different inputText values.
CompressText should process the inputText, populate the compressedText, and return
the number of bytes in the result. ExpandText does the opposite, processing the
compressedText, converting it to expandedText, and returning the number of bytes of
the original text. Multiple CompressText and ExpandText calls will occur with varying
inputText and compressedText, in any order, with the obvious constraint that text
must be encoded before it can be decoded.
The inputText may contain any character between 0x00 and 0x7F, inclusive. As a
practical matter, the inputText will be drawn from paragraphs of English-language
text, computer programs in C, C++, and Pascal, and html pages.
All text-specific information needed to decode the compressedText must be stored in
the compressedText itself. Any text-independent decoding information may be stored in
yourStorage or in static storage within your program. No text-specific encoding
information may be stored in yourStorage or in static variables.
The winner will be the solution that correctly compresses the inputText into the least
costly compressedText, where cost is a function of length and execution time.
Specifically, each inputText will have a cost equal to theCompressedLength of the
corresponding compressedText, plus a penalty of 10% for each 100 milliseconds
required to do the encoding and decoding.
This will be a native PowerPC Challenge, using the CodeWarrior Pro 5 environment.
Solutions may be coded in C, C++, or Pascal. Solutions in Java will also be accepted,
but Java entries must be accompanied by a test driver that uses the interface provided
in the problem statement.
Three Months Ago Winner
Congratulations to Sebastian Maurer for winning the January, 2000, Triangle Peg
Challenge. The Peg Challenge required entries to solve variously sized games of peg
solitaire, a game where pegs are arranged in holes on a triangle board. The objective of
the game is to repeatedly jump one peg over an adjacent one, removing the jumped peg
each time, with the intent of removing as many pegs as possible. In our Challenge,
scoring counted 1000 penalty points for each peg left on the board, plus one penalty
point for each millisecond of execution time. Sebastian did not submit the fastest entry
- in fact, he ranked third in speed - but it played the Peg game significantly better
than the other solutions, resulting in a better overall score.
I evaluated the Pegs entries using 14 test cases, ranging from 5 pegs to 100 pegs on a
side. Nine of the test cases were missing only one peg, one of the large puzzles was
missing 50 pegs, with the remainder missing a small number of pegs. Sebastian's
entry left fewer pegs on the board than the second place solution in 12 of 14 test cases,
and fewer than the third place solution in 10 of 14 cases. Sebastian's entry won in all
of the test cases involving larger puzzles.
Sebastian's code is rather sparsely commented. The work is done in his Search routine,
which iteratively tries valid moves, backtracks when it cannot find a valid move, and
saves the best solution found so far. In looking at the code for the top entries, it wasn't
obvious why Sebastian's solution did so much better than the others. The entries did
use different logic to prune the search and trade execution time against search depth;
perhaps those differences explain the performance variation.
The table below lists, for each of the solutions submitted, the overall score, the
execution time in microseconds, and the total number of pegs left on the board for all
of our test cases. It also indicates the code size, data size, and programming language
used by each solution. Two entries did not complete all of the test cases and are listed
last. As usual, the number in parentheses after the entrant's name is the total number
of Challenge points earned in all Challenges prior to this one.
Name Score Time (µsecs) Pegs Left Code Size Data Size
Lang
Sebastian Maurer (77) 2022464 46464 1976 4852
162 C
Andrew Downs (2) 3623988 10988 3613 1872 20 C
Willeke Rieken (61) 3727672 14672 3713 3020 56
Randy Boring (112) 11211715 476714 10735 7308 132096
M. L. N/A N/A 2648 218 C
J. C. N/A N/A 10828 1021 C++
Top Contestants
Listed here are the Top Contestants for the Programmer's Challenge, including
everyone who has accumulated 10 or more 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.
Rank Name Points
1. Munter, Ernst 227
2. Saxton, Tom 139
3. Maurer, Sebastian 87
4. Rieken, Willeke 48
5. Boring, Randy 43
6. Heithcock, JG 43
7. Shearer, Rob 43
8. Taylor, Jonathan 24
9. Brown, Pat 20
10. Downs, Andrew 12
11. Jones, Dennis 12
12. Hart, Alan 11
13. Duga, Brady 10
14. Hewett, Kevin 10
15. Murphy, ACC 10
16. Selengut, Jared 10
17. Strout, Joe 10
18. Varilly, Patrick 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 Sebastian's winning Triangle Peg solution:
Pegs.c
Copyright © 2000 Sebastian Maurer
#include "Pegs.h
#include "Memory.h
#include "Timer.h
const int kNumTries = 1000;
const UInt32 kStopTime = 500000;
// in microseconds
const int kNumDirections = 6;
enum {kIllegal = 0, kFull, kEmpty};
char** gGrid;
PegJump *gCurrentJumps;
PegJump *gBestJumps;
int gBestScore;
UnsignedWide gLastImprovement;
unsigned short *gDirection;
short gDeltaRow[kNumDirections];
short gDeltaCol[kNumDirections];
static UInt32 WideDiff(UnsignedWide m1, UnsignedWide m2)
UnsignedWide m;
m.lo = m2.lo - m1.lo;
m.hi = m2.hi - m1.hi;
if (m1.lo > m2.lo)
m.hi -= 1;
return m.lo;
}
static void PrintBoard(int triangleSize) {
for(int r = 0; r < triangleSize; r++) {
for(int c = - triangleSize; c <= triangleSize; c++)
case kIllegal: printf(" "); break;
case kFull: printf("X"); break;
case kEmpty: printf("."); break;
default: printf("?");
}
}
printf("\n");
}
printf("\n");
}
AllocateGrid
//////
// Memory allocation for the 2D grid
static char **AllocateGrid(
int xMin, int xMax,
int yMin, int yMax)
int nx = xMax - xMin + 1;
int ny = yMax - yMin + 1;
char **array;
Ptr p;
int rowSize;
array = (char **) NewPtr((Size)(nx * sizeof(char*)));
if (array == 0)
return 0;
array -= xMin;
p = NewPtr((Size)(nx * ny * sizeof(char)));