P E G G E D .... the first 1997 POTM |
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 minuteson 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
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".