C H O M P !
====================
This summer, we're eating cookies. Eat a lot of cookies and DON'T eat
the last poison cookie and YOU could win the next Programmer Of The Month.
You write a program to play a game X O O O O O O O
called "chomp" and play against all O O O O O O O O
the other folks who send in programs. O O O O * * * *
O O O O * * * *
Head-to-head, winner-take-all. O O O O * * * *
Programs alternately eat a bunch of cookies by choosing a row and column
and "eating" everything below and to the right of it. The example above
shows a 5x8 starting grid after one chomp at row 3, column 5 that ate 12
cookies. The poison cookie is always in the upper left hand corner. When
it's your turn, take a chomp and avoid being the one who is forced to eat
the poison cookie. THIS POTM is not original, some research may pay off!
======================= THE DETAILS - SINCE YOU ASKED ========================
DEADLINE is Sunday September 3rd, 1995 at 11:59 PM EST.
I. THE COOKIE GRID will be presented on standard input ... you will take
a chomp, modify the grid, and write the resulting grid to standard
output. The grid will consist of N rows and M columns, where N
is given by ARG1 and M is given by ARG2. The grid itself will
consist of an array of characters. There are three legal values:
'X' is the poison cookie - it will always be in row 1 column 1
'*' are empty positions - these cookies have already been eaten
'O' (letter O) are good cookies - you can chomp at any of these
positions and remove THAT cookie and everything below and
to the right of that cookie before writing out the grid.
The grid size is given by the two arguments to the program: rows
and columns. There will be between 2 and 50 rows and between
2 and 50 columns. 2<=N<=50 and 2<=M<=50 where N and M are rows
and columns. Thus, the smallest grid will be 2x2 and the largest
will be 50x50. The grid need not be square - but it MAY be.
II. THE CHOMP is your move. Your program must choose one of the cookies
in the input grid (either an 'O' or 'X' position) and change this
position and all positions below and to the right of your chosen
position to '*' signifying that these cookies have been eaten.
For example, if the 4x7 input square is:
XOOOOOO if you chomp at row 2, XOOOOOO
OOOO*** column 3 ... then you OO*****
OOOO*** must output: OO*****
OO***** OO*****
XOOOOOO if you chomp at row 1, XOOOOO*
OOOO*** column 7 ... then you OOOO***
OOOO*** must output: OOOO***
OO***** OO*****
XOOOOOO if you chomp at row 3, XOOOOOO
OOOO*** column 2 ... then you OOOO***
OOOO*** must output: O******
OO***** O******
XOOOOOO if you chomp at row 1, *******
OOOO*** column 1 ... then you *******
OOOO*** must output: *******
OO***** *******
Of course, in this last case you have lost!
Note that your program does NOT print out the "position" of the
cookie you choose - it must print out the resulting grid!
Note also that if your program is presented with ONLY the
poison cookie - you MUST eat it and output the all '*' grid.
X****** You are FORCED to eat *******
******* the cookie at row 1, *******
******* column 1 and you MUST *******
******* output the grid: *******
Although the examples are shown on a 4x7 grid, remember that
the grid may grow to be as large as 50x50. The grid size will
NOT change over the course of a game until one of the two
programs wins. The final grid will be fairly large.
Starting grids will always be filled with uneaten cookies, and
only the cookie in row 1, column 1 will be poison.
III. THE TASK and THE SCORING - HOW TO WIN!
The task is simple: don't eat the poison cookie. If you can
make your opponent eat the posion cookie - then you WIN! If
you are forced to eat the poison cookie - you lose.
If you WIN, you get a score equal to the number of cookies
you ate along the way. If you lose, you get a score of zero.
During the finals, your entry will play one match against every
other entry. A match consists of two games on an identical size
grid - each player gets to go first. So, if I get 30 entries,
YOUR program will play 29 matches, or 58 games.
The program with the most WINS after all matches are complete
is the grand winner. If two (or more) programs have the same
number of WINS, then the highest TOTAL SCORE over all matches
will win. If two (or more) programs are still tied, then the
program making the FEWEST TOTAL CHOMPS over all matches will
win. If there are STILL ties I'll run some sort of playoff
between the remaining programs using a variety of input grids.
Hopefully, it will not come to this!!!
The size of the final grid will be determined in August, but
it won't be square! The system test grid will be of manageable
size and system tests will be played against a random-move
opponent to determine whether the program conforms to the rules.
IV. INPUT/OUTPUT
A "grid" is defined as N rows of M characters, where each line is
terminated with a newline. Your output should look
something like this for a three row, four column grid:
printf("%c%c%c%c\n", .....) row one
printf("%c%c%c%c\n", .....) row two
printf("%c%c%c%c\n", .....) row three
no white space, newline on each line.
A grid will be presented on standard input ... piped to your program.
Your program must output a grid on standard output.
Your program should accept two arguments: the number of rows
followed by the number of columns. I will never run
your program with input files with an incorrect number
of rows or columns.
For example, if the file TESTFILE contains : XOOO
OOOO
OOOO
and your program is called "a.out", then the following pipeline
should work and print out the resulting grid after three moves:
cat TESTFILE | a.out 3 4 | a.out 3 4 | a.out 3 4
PLEASE make sure your program can run against itself in this way!!!
V. 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!)
=============================================================================
==> Quick summary of changes for CHOMP: 25K max source size; no more than
==> 10% of the source used for data initialization; no more than 30 seconds
==> per move averaged over an entire large-size game; make sure the header
==> is in your source; send it to enter@potm.ffast.att.com
=============================================================================
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 version 2.6.2
g++ version 2.6.2
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 should be sent, if there are special instructions
please so indicate in your program header comments.
Plus whatever other languages 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! (e.g. perl, sh, awk, whatever)
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 ONLY in /tmp. Creation of files
anywhere else will cause disqualification. All files that
are created MUST be removed on completion of your move. Failure
to remove any created files will cause disqualification.
You may NOT attempt to to record the moves of the current or
previous games for evaluation of later moves. It's probably
safest simply NOT to use temporary files.
==> e) Maximum size of the source code is roughly 25K characters -
==> comments don't count against you. The intent of this rule is
==> to prohibit entries with large tables in them. BUT, I've found
==> it necessary to add the following prohibition: no more than 10%
==> of your source code may be data initialization. Please try and
==> adhere to the intent of this rule. (By the way, code generators
==> are not allowed to be used to subvert this rule ...)
f) Maximum size of executable is 1 Megabyte ... please!!!!
II. The system testing ....
a) ship 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 no more than two a week 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 listing with the current status of the entries.
(I usually will get to them once a night but perhaps not!)
d) please make sure your program works before you ship it??
==> e) your program must perform the task specified within a reasonable
==> time (for CHOMP, your program should average no more than
==> 30 seconds per move over the course of a game of any size grid).
(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). Warnings will be issued, and disqualifications
==> will (in general) not be made because of taking too much time
==> except in circumstances where the guidelines are clearly violated.
III. SENDING ME YOUR ENTRY - PLEASE USE EMAIL!!!
Please email (not uuto) your source code to me at:
enter@potm.ffast.att.com (preferred)
fah@ffast.ffast.att.com
attmail!hicinbothem (will forward correctly but
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) */
/* compilation 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 within a day or two.)
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
attmail!hicinbothem .... hopefully all my mail-path bugs are worked out!
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!!!
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