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".












Make your own free website on Tripod.com