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.


	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.

	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

	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.


    Please email (not uuto) your source code to me at:

    	enter@potm.ffast.att.com		(preferred)
    	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!!!


Looking forward to your entry!	(remember:  enter@potm.ffast.att.com)
Make your own free website on Tripod.com