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 email@example.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: firstname.lastname@example.org (preferred) email@example.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: firstname.lastname@example.org (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: email@example.com) =Fred