May 1999 Programmer's Challenge
Piper
Mail solutions to:
progchallenge@mactech.com
Due Date: 11:59pm ET, Friday, 7 May 1999
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)
extern "C" {
#endif
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.
Test code for this Challenge is available.
You can get a head start on the Challenge by reading the
Programmer's Challenge mailing list. It will be posted to the list on
or before the 12th of the preceding month. To join, send an email to
listserv@listmail.xplain.com
with the subject "subscribe challenge-A". You can also join the
discussion list by sending a message with the subject "subscribe
challenge-D".
|