May 99 Challenge
Volume Number: 15
Issue Number: 5
Column Tag: Programmer's Challenge
by Bob Boonstra, Westford, MA
Piper
Every once in a while, good fortune not only comes your way, but actually reaches out
of your computer monitor, and grabs you by the throat. I felt a little like that while
reading a recent issue of TidBITS. In it was a column by Rick Holzgrafe reflecting on
the increasing speed of computers, in which Rick described a program he wrote for a
PDP-11/60 to solve a word puzzle. The idea behind the puzzle was to take a phrase and
map it onto a rectangular grid, with the objective being to map the phrase into a
rectangle of the smallest possible area. The word puzzle looked like a good idea for a
Challenge, and Rick and TidBITS agreed to let me use it.
In more detail, the puzzle works like this. To start, you are given a null-terminated
string consisting of printable characters. You process the characters in order,
ignoring any non-alphabetic characters and ignoring case. The first alphabetic
character can be mapped to any square in the grid. The next letter can be mapped to any
adjacent square, where adjacent is any of the eight neighboring squares in a
horizontal, vertical, or diagonal direction. You may reuse a square if it is adjacent and
already has the letter you are mapping. If the same letter occurs twice in a row in the
input string, the letters must still be mapped to adjacent (but distinct) squares.
The prototype for the code you should write is:
#if defined(__cplusplus)
typedef struct GridPoint {
long x;
long y;
} GridPoint;
void Piper (
char *s,
GridPoint pt[]
);
#if defined(__cplusplus)
}
#endif
For example, your Piper routine might be provided with the string:
How much wood would a woodchuck chuck if a woodchuck
could chuck wood?
You might place the letters of that string into a 4x14 rectangle like:
ULD ADLU
HDOAIUCOHWUHOD
UCOWFKHDOMCWOW
K WO
Or, you might compact them into an 4x4 rectangle:
HWMU
OOCH
UDWK
LAFI
You must return the GridPoint coordinates of where each character is mapped, with
pt[i] containing the coordinates of input character s[i]. The origin of your coordinate
system should be the cell where the first character is placed. The winner will be the
solution that stores the input string in a rectangle of minimal area. Note that you are
minimizing rectangle area, not the number of occupied squares. A time penalty of 1%
for each second of execution time will be added
This will be a native PowerPC Challenge, using the latest CodeWarrior environment.
Solutions may be coded in C, C++, or Pascal.
Three Months Ago Winner
The February Challenge invited readers to write a player for the game of Chinese
Checkers. Played on a hexagonal board with six appended triangles, Chinese Checkers
pits between 2 and 6 players against one another, with the objective being to move
one's pieces from the home triangle to the opposite triangle. In the traditional game,
the home triangles are usually 3 or 4 positions on a side; the Challenge extended the
game to triangles of up to 64 positions. Pieces can either be moved to an immediately
adjacent position or jumped over an adjacent piece. A single piece is permitted to make
a sequence of jumps in a single move.
As simple as the game sounds, readers found it to be very difficult, so difficult that no
solutions were submitted for the Chinese Checkers Challenge. Which left Yours Truly
in something of a difficult spot. I could stop the column at this point, which wouldn't be
very interesting for readers, not to mention not very satisfying for the magazine. Or I
could write a solution for the Challenge myself, something I haven't done since I
retired from Competition four plus years ago. Somewhat against my better judgement,
I selected the latter option.
The first thing I noticed in solving the Challenge was that the board coordinate system
specified in the problem wasn't very useful in generating a solution. I needed a
coordinate system that could be easily rotated in 60-degree increments, enabling my
solution to play any of the six possible player positions. After some thought, I came up
with a more symmetric coordinate system, called CanonPosition in the code, along with
conversion routines ConvertPositionToCanonPosition and
ConvertCanonPositionToPosition. The commentary in the code illustrates the
coordinate system for a board of size 4. Then I needed a way to evaluate board positions.
I decided on a simple metric that summed the distances of all pieces from the apex of
their goal triangle. That metric could be improved upon by taking possible jump moves
into account. The solution starts by computing all possible moves for our player. It
then tries each of those moves, and then recursively calls MakeNextMove to process
the next player. It computes and tries all moves for that player, and recurses for the
next player. Recursion terminates when kMaxPlys turns have been taken for all
players. Positions are evaluated using a min-max technique, where each player selects
the position that maximizes his position relative to the best position of the other
players.
The code could be improved in many ways. Instead of trying all possible positions, it
could prune some obviously bad moves in the backward direction. This is complicated
by the fact that some good jump multi-moves can include individual jumps that appear
to be moving backward. The code might also be improved by evaluating moves by
progressive deepening, rather than the depth-first search currently used, and by
ordering move evaluation based on the scores at the prior depth. This technique is used
in chess programs to prune the move tree to a manageable size. These and other
optimizations are left to the reader. :-)
Remember, you can't win if you don't play. To ensure that you have as much time as
possible to solve the Challenge, subscribe to the Programmer's Challenge mailing list.
To subscribe, see the Challenge web page at
. The Challenge is sent to the list
around the 12th of the month before the solutions are due, often in advance of when the
physical magazine is delivered.
Here is our sample Chinese Checkers solution:
Chinese Checkers.c
Copyright © 1999 J. Robert Boonstra
/*
* Example solution for the February 1999 Programmer's Challenge
*
* This solution is provided because no solutions were submitted
* for the ChineseCheckers Challenge. This solution leaves a
* great deal to be desired: it is not optimized, it does not
* prune prospective moves efficiently, and it does not employ
* any of the classic alpha-beta techniques for efficiently
* selecting a move.
*/
#include
#include
#include
#include "ChineseCheckers.h
/* Position coordinates specified in problem (size==4)
0: 0
1: 0 1
2: -1 0 1
3: -1 0 1 2
4: -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6
5: -5 -4 -3 -2 -1 0 1 2 3 4 5 6
6: -5 -4 -3 -2 -1 0 1 2 3 4 5
7: -4 -3 -2 -1 0 1 2 3 4 5
8: -4 -3 -2 -1 0 1 2 3 4
9: -4 -3 -2 -1 0 1 2 3 4 5
10: -5 -4 -3 -2 -1 0 1 2 3 4 5
11: -5 -4 -3 -2 -1 0 1 2 3 4 5 6
12: -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6
13: -1 0 1 2
14: -1 0 1
15: 0 1
16: 0
*/
#define kMaxPlys 1
#define kEmpty -1
/* CanonPosition uses units with (0,0) at the middle of the board */
typedef struct CanonPosition {
long row;
long col;
} CanonPosition;
/* Canonical position coordinates (size==4)
-8: 0
-7: -1 1
-6: -2 0 2
-5: -3 -1 1 3
-4: -12 -10 -8 -6 -4 -2 0 2 4 6 8 10 12
-3: -11 -9 -7 -5 -3 -1 1 3 5 7 9 11
-2: -10 -8 -6 -4 -2 0 2 4 6 8 10
-1: -9 -7 -5 -3 -1 1 3 5 7 9
0: -8 -6 -4 -2 0 2 4 6 8
1: -9 -7 -5 -3 -1 1 3 5 7 9
2: -10 -8 -6 -4 -2 0 2 4 6 8 10
3: -11 -9 -7 -5 -3 -1 1 3 5 7 9 11
4: -12 -10 -8 -6 -4 -2 0 2 4 6 8 10 12
5: -3 -1 1 3
6: -2 0 2
7: -1 1
8: 0
*/
/* PlayerPos is used to store the location of each of a players pieces
*/
typedef struct PlayerPos {
CanonPosition pos;
typedef char *CanonBoard;
static long myNumPlayers,myNumPieces,myIndex,myGameSize,
myPlayerPosition[6],myMinDist;
static PlayerPos *myPositions;
/* global board */
static CanonBoard myBoard;
/* moveIncrement is added to a CanonPosition to find the adjacent
square in the
* six possible directions 0..6, with 0==horizontal right, 1==down
right, ...
* 5==up right
*/
static CanonPosition moveIncrement[6] =
{ { 0, 2}, { 1, 1}, { 1,-1}, { 0,-2}, {-1,-1}, {-1, 1} };
/* macros to access the board */