P E G G E D .... the first 1997 POTM
|
I'm sure most of you have seen puzzles made of wood or plastic that
have a bunch of pegs in holes. Usually you are required to remove
pegs by "jumping" them with other pegs until there is only one peg
left - usually in the middle. Every couple of years I re-discover
one of these puzzles and I can never remember how to solve it. So
I decided to make a POTM out of it.
PEGGED: The Details
Welcome to the First 1997 POTM ... deadline midnight on 4/1/97 !!!
(Please do not be afraid of all these details ... the intent of most POTMs
is straightforward, but I've found that I need to be very explicit to try
and close any "loopholes" for all you "requirements lawyers" out there.)
I. WHAT DOES YOUR PROGRAM HAVE TO DO?
Your program must read in a file that describes a playing board
with a bunch of holes. Some of the holes will have pegs in them
and some will be empty. The holes will be marked with "O" and
the holes with pegs in them will be marked with "X". Your
program must read this input file and plan a series of "moves"
that will leave only a single peg on the board. Each "move"
may be one of the following:
a) any peg may move horizontally or vertically to
an adjacent empty hole. This type of move
will be called a "walk" (no diagonals).
b) any peg may jump horizontally or vertically over
another peg which is immediately next to it.
In this case, the peg which is "jumped over"
is removed from the board. This type of move
is called a "jump".
Your program will output a series of walks and/or jumps which
will leave only a single peg on the board. Obviously, if you
started with N pegs there will be (N-1) "jumps" in your
solution. There may be no "walks" at all or there may be many
of them. Your score will be the total number of moves you
need - the fewer the better!
II. HOW ABOUT A SIMPLE EXAMPLE
Let's say that the input file looks __OO_
like the five line, five column file __OO_
given on the right. Note that there OOXOO
are a total of 15 holes in the board OOOOX
(the other ten positions marked with ____X
the "_" are not usable). Three of
the holes have pegs in them and are marked with an "X".
The rows are lettered alphabetically (in this case A through E)
while the columns are numbered numerically beginning with 1.
Let's say your program makes three moves as follows:
E5-C5 C3-C4 C5-C3
__OO_ __OO_ __OO_ __OO_
__OO_ __OO_ __OO_ __OO_
OOXOO OOXOX OOOXX OOXOO
OOOOX OOOOO OOOOO OOOOO
____X ____O ____O ____O
Your score is "3" since it took you three moves (jump,
walk, jump) to get to a single peg. Coincidentally, the
last peg ended up in the dead center (C3) of the board - this
is good because it means your "tiebreaker" score is zero.
(See the scoring section for details on the tiebreakers!)
III. TELL ME MORE ABOUT BOARDS (INPUT) and THE MOVES (OUTPUT)
1. All boards will contain 25 or fewer rows - these rows
should be labelled with upper case letters when
describing moves beginning with A. There will be
an odd number of rows in each input file.
2. All boards will contain 49 or fewer columns - these columns
should be labelled with numbers beginning with 1.
There will be an odd number of columns in each input file.
3. There will be no white space in the input file. Each board
position will be denoted with one of three ASCII characters:
a) "_" indicates that this position does NOT contain a
hole and hence may not be used for any purpose
b) "O" (upper case letter O - NOT zero) indicates that
this position starts with an unoccupied hole.
Pegs may be moved into and out of this position.
c) "X" indicates that this position is a hole which is
currently occupied by a peg. Pegs may be moved
into and out of this position.
4. In the input file, each row will be contained on a single line
of text with a single character for each column. No
mysteries here - exactly as you would expect of a sane person.
5. Your program will output one line of text for each move. Each
line of text must contain TWO board positions separated by
a "space" character. The first board position must be a
position which currently contains a peg. The second board
position must currently contain an un-occupied hole. The
two positions together must constitute a legal move as
described below. A board position is described by an upper
case letter denoting the row and a number denoting the column
which are NOT separated by white space. Some valid output:
A1 A3 (A2 must have a peg)
B17 D17 (C17 must have a peg)
R48 R47
L11 L9 (L10 must have a peg)
6. There are two types of valid moves:
a) A "walk" takes any peg, and moves it one hole up, down,
left, or right to a previously unoccupied hole.
No diagonal walks are allowed.
b) A "jump" is possible for a peg when there is another
peg to the left or right of it, or above or below it.
To "jump" a peg move TWO squares up, down, left, or
right - you must jump over an OCCUPIED hole and
into an UNOCCUPIED one. After the "jump", the peg
that was jumped over is removed from the board.
c) You may not jump over a square marked with anything
but an "X" ... no jumping over "_" or "O" spots.
d) with the exception of restricting moves to horizontal and
vertical, the "walks" and "jumps" are exactly what
you think they are ... this is not rocket science.
e) most puzzles of this type do not allow "walks" and all
moves must be "jumps". By allowing both I can
guarantee that a solution exists for almost any
board I can put together.
IV. THE SCORING - HOW TO WIN!
First Score: The winner will be the program which requires the
fewest number of moves to eliminate (by jumping) all pegs but one.
Note that if we start with N pegs, all programs will need to
have (N-1) "jumps" in them, so the smallest number of "moves"
will occur when there are the smallest number of "walks". For a board
with N pegs, the best possible score is (N-1) although that may
not be possible for all presented problems.
NOTE: if your program runs for more than 10 minutes on
any board, it will receive a score of ZERO for that board.
Similarly, any illegal moves or core dumps will result in a
score of ZERO.
Second Score: In the event that more than one program achieves the
lowest "first score", the initial tiebreaker will be determined
by the location of the final peg on the board. All playing boards
will contain an odd number of rows and columns - thus allowing a
"center" hole to be defined without ambiguity. This tiebreaker
will be the number of walks that would be required to move the
last peg to this center hole. NOTE: You should NOT actually
include these moves at the end of your solution since doing so
would increase your first score.
Final Tiebreaker will be the execution time as measured by
timex time taken on the final test. Fast is good.
Long is bad. More than 10 minutes per board is disqualified!
THE FINALS WILL CONSIST OF three separate boards. In order to
determine a winner - the first scores on all three boards will
be added. The lowest total will win. If there is a tie, only
the programs that tie will have their second scores added together.
Of THESE programs, the lowest second score will win. If ties
remain, the for all three final runs will be added
and the lowest total will win. It is unlikely to come to this.
V. INPUT/OUTPUT
1) The output must be ONLY the lines describing the moves. One
move per line. The output must appear on standard output.
2) NO OUTPUT to stderr is permitted.
3) All input is derived from the file whose pathname is contained
in the single argument to the executable program:
e.g.: myprogram filename
4) The format of the input file is described in II and III above.
VI. THE SYSTEM TEST PROBLEM ... when you submit, your program will need
to solve the following problem. Your results will be posted along
with everyone elses (not the move sequence, just the scores). PLEASE
make sure your program can handle this problem before sending it!
______OOO______ A1 through A15 on this row.
_____OOOOO_____ B1 through B15 on this row ... etc.
____XOXXXOX____
___OOOXXXOOO___ Some valid first moves:
___OXXXXXXXO___ F10 F8 (removing peg on F9)
___OXXXOXXXO___ H8 F8 (removing peg on G8)
___OXXXXXXXO___ C5 C6 (no pegs removed)
___OOOXXXOOO___ F5 F4 (no pegs removed)
____XOXXXOX____
_____OOOOO_____ Note that this problem is similar to some you may
______OOO______ have seen being sold, except that four extra pegs
have been added and there are several extra holes.
The center square is F8.
VI. READ THE Frequently Asked Questions (FAQ) list distributed every
week ... it often contains corrections to this problem statement!
=============================================================================
The following items are standard stuff for ALL the POTMs ....
(but they occasionally will change ... so READ 'EM!)
=============================================================================
I. About your programming:
a) I compile on one machine (usually) and execute on
another as follows:
compilation machine: SunOS 5.3 Generic_101318-59 sun4m sparc
execution machine : SunOS 5.3 Generic sun4c sparc
b) The compilers I have available are (at least):
SPARCompiler C++ 4.0
SPARCompiler C ANSI C compiler
SVID compliant under SunOS 5.x
gcc/g++ version 2.7.2
PERL version 5.002
Java version 1.0
Scheme48 - a Lex variant
All compilation will be done WITHOUT ANY OPTIMIZATION, and the
standard math library will be loaded (even if not used). While
this might not reflect the real world, it is at least consistent.
No makefiles are permitted, if there are special instructions
please so indicate in your program header comments.
Plus: ... whatever else I can support on the compilation
machine ... just ask and I'll try to find it!!!
I have the ability to compile on several different
boxes, so don't hesitate to ask!
>>> IMPORTANT: submit early so we can resolve any
>>> portability problems!!!
NOTE: assembly code submissions are NOT acceptable. I must be
the one to compile your code so I can check for cheating!
c) if you wish to submit a shell program, Bourne, Korn, and csh
are available ... along with any bin or /usr/bin tools that
are available as generic Unix tools - my judgement!!!
(again - submit early in case there are version differences)
d) Temporary files may be created in /tmp, but MUST be removed
when you are done ... creation of files anywhere else is
strictly prohibited.
e) Maximum size of the source code is roughly 25K characters -
different rules may apply for specific POTMS, and
comments don't count against you.
f) Maximum size of executable is 1 Megabyte ... please!!!!
g) Maximum malloc'able space is a bit over 50 Meg ....
h) sizeof(short)=2; sizeof(int)=4; sizeof(long)=4; sizeof(char)=1
i) a = 0x80000000 = -2147483648
a - 1 = 2147483647
a + 1 = -2147483647
{a} is true. {a == 0} is false.
II. The system testing ....
a) mail me an entry as soon as possible - you can always submit
another entry if you improve your solution .. but try and
keep it down to one a week once the porting issues are
resolved .... please!
b) one entry per person (or team) please. I associate each entry
name with an email address and a person for communication
purposes. Communication is fine - and encouraged - but
everyone's code should be their own unless there is a
stated collaboration and a single team entry. Honor system!
c) on receipt of your entry, I'll run a system test to make sure
your program works ... you'll receive the results and
a weekly standing of how you fared against other entries.
(I usually will get to new mail once a night but perhaps not!)
d) please make sure your program works on the system test problem.
e) your program must perform the task specified within 10 minutes
sys+user time as measured by timex on MY execution system.
Your time will be provided along with your system test run
so you can see the differences in speed between yours and mine.
All execution time measurements used for tiebreakers (if any)
will be measured using time via timex (similar to
time command). NOTE: A code fragment to measure elapsed time
is available from the POTM-master for the asking.
III. SENDING ME YOUR ENTRY - PLEASE USE EMAIL!!!
Please email (not uuto, no attachments) your source code to me at:
enter@potm.ffast.att.com (preferred)
hicinbothem@att.com (use only as a last resort!)
IMPORTANT: Please use the following (or equivalent) lines at the
front of the program you mail to me (this will help immeasurably!):
/* POTM ENTRY: entryname (something clever please!) */
/* Your Name: First Last */
/* Your email: log@machine.att.com (or whatever) */
/* compile instructions (if other than "make entryname") */
NOTE: If you submit a shell program, please include these lines
with a leading "#" and indicate which shell to run it under!
IMPORTANT: ENTER EARLY - you will receive weekly standings and
you will resolve any portability issues early. You may improve
your entry at any time by simply sending me another entry - so it
pays to enter earlier! (I process most everything in a day or so)
IMPORTANT: If you don't hear from me within a few days - it may
mean that the mail got screwed up .... please follow up with an
inquiry to hicinbothem@att.com ....
Thanks! If you have any questions, mail 'em to me - if I answer them
I'll include them in the Frequently Asked Questions (FAQ) list I
circulate with the weekly standings!!! Don't call me ... please!
WATCH THE FAQ - ESPECIALLY IN THE FIRST FEW WEEKS AS ALL THE STUPID
ERRORS I MAKE IN THE PROBLEM STATEMENT TURN UP!!!!
Looking forward to your entry! (remember: enter@potm.ffast.att.com)
=Fred
Here is a copy of the FAQ at the contest conclusion:
This is a list of Frequently Asked Questions (the FAQ list). New questions
are added to the top and dated .... the goal is to make the same information
available to all participants. The FAQ supplements and overrides the long
form of the rules where there is a conflict!
7) 02/17: Ummmm ... what were those system test boards again????
There were two boards, reproduced below for your testing pleasure.
The first was pretty easy - the second stumped several entries!
______OOO______
_____OOOOO_____
____XOXXXOX____
___OOOXXXOOO___
___OXXXXXXXO___
___OXXXOXXXO___
___OXXXXXXXO___
___OOOXXXOOO___
____XOXXXOX____
_____OOOOO_____
______OOO______
And the second one:
XXXXOOXXOOXXOXX
O_OOXOXXXOXOO_O
O_XXXOXXXOXXX_O
__XOX_____XXX_O
__XOXXXOXXXXX__
__XOXXXXXOOXX__
XXXOOOXXXOXXX__
XOOXXXXXOOXXX_X
_____OOOOOXXXXX
6) 01/03: Can you give me a hint? About how many pegs in the finals???
I haven't thought about the finals yet ... fewer pegs than holes,
and less than or equal to 25*49 holes ... does that help????
And whatever I give you must run in less than 10 minutes!
(Timing code available on request if you need it!)
5) 12/23: Just some clarifications about the input file:
*) it will always be rectangular
*) your program does not need to check for boards which do
not conform to the requirements - all boards WILL
*) The first character on the first line is position A1 ...
the first character on the second line is B1 ... etc.
(row A is line 1 of the input file)
*) There will be at least three rows and three columns.
4) 12/23: If low scores win, and you give scores of ZERO for core dumps ...
Hmmm ... seems like I need to close this loophole or you smart
folks will figure out how to beat this POTM easily. So: all
misbehaviors will be awarded a gazillion points rather than ZERO.
3) 12/23: Will the center of the board always be a hole?
Yes - but it may be filled at the start
2) 12/23: Will there ever be holes not reachable from the center hole?
Or any "unsolvable" boards which are impossible to reduce to
one peg? Or any "islands" of holes not connected to all others?
Or maze-like boards with convoluted paths?
No .... you'll always be able to "walk" from the center to
any hole on the board - and I guarantee that all problems will
be reducable to a single peg using "jumps" and "walks". The
shortest walk from any hole to the center MAY involve more than
one turn, but my intent is NOT to build mazes. And that's about
all I'm going to say about THAT!
1) 12/22: The second tiebreaker may be ambiguous for some boards ... help!!
I defined the tiebreaker as the number of "walks" it
would take to get to the center ... but if there is an area of
the board which could not be walked through, defining it this way
is misleading. The intent is that the tiebreaker is the sum of
the horizontal distance and the vertical distance between the
last peg you leave and the center peg on the board - regardless
of whether this path could actually be "walked".