Jan 00 Challenge
Volume Number: 16
Issue Number: 1
Column Tag: Programmer's Challenge
Programmer's Challenge
by Bob Boonstra, Westford, MA
Peg Triangle
Welcome to the New Year! If you're not one of those people who quibble about whether
the new century starts in 2000 or 2001, welcome also to a new century and a new
millennium! As I write this, I can't be certain whether the doomsday predictions will
turn out to have had any validity, but I'm betting that as you read this, the lights will
be on, the telephones will work, the ATMs might be occasionally short of cash, the
grocery stores will be replenishing their canned goods, and the pundits will be
questioning what the fuss was all about. (At least this is my prediction for the
so-called First World - I'm not close enough to the situation in the rest of the world to
be as confident.) Of course, as someone whose Real Job included making certain that
this transition to January was as boring as any other, I know that there was a lot of
hard work invested in ensuring that life went on in the IT world.
But I'm betting that most of you are ready and able to take on this month's
Programmer's Challenge. Especially since most of you are presumably Mac users, who
didn't (or don't) have to go through the complicated process of remediating their
Monopoly-OS machine so that it would continue to function. We're going to make the
Challenge a little simpler this month, in hopes of encouraging some new participants
to take a shot at making the Top Five.
A while back my daughter presented me with a puzzle she had made in wood-shop.
(Yes, my town has progressed to the point where the girls take wood-shop and
metallurgy classes and the boys take cooking and sewing.) The puzzle is a triangular
block of wood with holes drilled into a triangular pattern: 1 hole in the first row, 2
holes in the second, etc. A peg occupies each of the holes, except one. The puzzle is
solved by a sequence of jump moves, where a peg jumps over an adjacent peg into an
open hole in the same direction, after which the jumped peg is removed from the
board. The object of the game is to remove all of the pegs from the board, except one.
Our Challenge will be a slight generalization of this puzzle. The initial board position
will always contain at least one vacant hole, but perhaps more than one. The object
will be to minimize the number of pegs remaining on the board at the end of the game,
but because of the initial configuration it might not be possible to reduce the number
of pegs remaining to one.
The prototype for the code you should write is:
#if defined(__cplusplus)
typedef struct TrianglePegPosition {
short row; /* 0..numberOfRows */
short col; /* -row, -row+2, ..., +row */
TrianglePegPosition from;
TrianglePegPosition to;
// must satisfy
// ( (to.row == from.row) && (to.col == from.col +- 4) &&
// ((from.row +- 1, from.col +-2) occupied) ||
// (to.row == from.row +- 2) && (to.col == from.col +- 2) &&
// ((from.row +- 1, from.col +-1) occupied) )
short /* number of moves */ SolvePegTriangle (
short triangleSize, /* number of rows in triangle to solve */
short numInitialPegs, /* number of pegs in starting puzzle
position */
TrianglePegPosition initialPegPositions[],
/* peg locations in starting puzzle position */
PegJump pegJumps[]
/* return peg moves that solve the puzzle here, in sequence
*/
);
#if defined(__cplusplus)
}
#endif
Your SolvePegTriangle routine is provided with the initial puzzle conditions and must
store the moves required to solve the puzzle in pegJumps, returning from
SolvePegTriangle the number of moves in pegJumps. As initial conditions,
SolvePegTriangle is given the dimension of the puzzle (triangleSize), the number of
pegs in the initial puzzle state (numInitialPegs), and the position of those initial pegs.
The winner will be the solution that solves a sequence of puzzles at the lowest cost.
Each millisecond of execution time used to solve the puzzles will incur a cost of 1
point. Each peg left on the board beyond the first will incur a cost of 1000 points
(whether or not it is possible to remove all but one peg from the board).
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
this month. Java entries must be accompanied by a test driver that uses the interface
provided in the problem statement.
Remember that you can get a head start on the Programmer's Challenge by subscribing
to the Challenge mailing list. See www.mactech.com/progchallenge/ for details.
Three Months Ago Winner
The October SuperDuperGhost Challenge attracted entries from four of the top six
contestants in the Programmer's Challenge points standing, and the top two in the
points standing finished one and two. Congratulations to Ernst Munter (Kanata,
Ontario) and Tom Saxton for finishing first and second, respectively, in the Ghost
Challenge.
The SuperDuperGhost Challenge required contestants to compete in a tournament,
where the object was to win a generalized game of Ghost. The concept of Ghost is simple
- players spell a word, taking turns adding letters, trying to avoid being the one to add
the last letter to a word in the dictionary. SuperDuperGhost complicated the original
game by allowing the addition of letters to the end of the string, to the beginning of the
string, to the beginning or the end, or finally at any place in the growing string,
depending on the mode of the game. Scoring was based on winning games, with a penalty
based on execution time, and an additional penalty for forming a word without
declaring yourself the loser.
Each of the four entries in the Challenge competed against every other entry, with each
player having a chance to play first against each other. With four entries in this
Challenge, that meant that there were 12 matches in each round, of which each entry
competed in 6. I conducted 10 rounds of competition, times four game modes
(addToEndOnly, addToBeginningOnly, addToBeginningOrEnd, addAnywhere), for a total
of 480 matches, with each player competing in 60 of each type.
Playing first had a significant advantage. Ernst's winning entry was successful in
every single match where it made the first move, regardless of whether the game mode
allowed additions to the beginning, end, beginning or end, or arbitrary location within
the growing word string. Tom's second place entry did almost as well, winning 117 of
the 120 matches where it played first. The third-place entry of Sebastian Maurer won
all of the entries where it played first for the game modes in which it chose to
compete; however, Sebastian only had time to complete code for two of the modes of the
game (addToEndOnly and addToBeginningOnly). The table below lists the number of
wins achieved by each entry in each of the four modes of the game.
Wins
addEnd Wins
addBeginning Wins
addEither Wins
addAnywhere
Ernst Munter 38 40 ˙50 49
Tom Saxton 39 40 ˙49 45
Sebastian Maurer 39 ˙40 0 0
JG Heithcock 4 0 ˙21 26
In the addToEndOnly and addToBeginningOnly modes, Ernst employs a recursive
solution to find a letter that does not complete a word, but which forces an opponent to
complete a word. If a win cannot be guaranteed, he selects a letter that admits solutions
where his opponent must complete a word. Depending on the dictionary, this strategy
always succeeds when Ernst moves first and sometimes succeeds otherwise. In the
other two game modes, the code attempts to force the opponent to complete a word, but
otherwise tries to guarantee that the opponent is forced to make a word shorter than
the shortest word Ernst can be forced to make.
The table below lists, for each of the solutions submitted, the total score achieved, the
execution time in milliseconds, the total number of wins achieved, the number of wins
when playing first, and the size and language code parameters. 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 (msec) Total Wins Wins play first
Code Size Data Size Lang
Ernst Munter (527) 17700 979 177 120 10412
2019 C++
Tom Saxton (128) 17250 2575 173 117 6132 637 C
Sebastian Maurer (70) 7900 1157 79 60 4448
187 C
JG Heithcock (39) 5000 1543 51 28 2856 97 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 237
2. Saxton, Tom 126
3. Maurer, Sebastian 77
4. Boring, Randy 66
5. Rieken, Willeke 51
6. Heithcock, JG 43
7. Shearer, Rob 34
8. Brown, Pat 20
9. Hostetter, Mat 20
10. Mallett, Jeff 20
11. Jones, Dennis 12
12. Hart, Alan 11