These are the long rules for the latest POTM.  I have tried to
be as clear as possible but if there are any questions please
ask them as soon as possible so I can correct errors in the
weekly FAQ mailings.  My goal is to eliminate loopholes - if
you have a question about wording, I probably meant the statement
to have the simplest possible interpretation.

           ******  S U I T C A S E    ******
    (deadline is 11:59 PM EST Sunday October 29,2000)

My summer of playing Diablo II is almost done - and aside from
all the slashing and hacking, I had to learn how to efficiently
stuff swords and armor into my pack.  The pack is a 10 by 4
grid, and the items come in various smaller sizes.  Often you must
rearrange the items in order to fit a large item into the pack.
So there it is.  The POTM will present you with a partially filled
pack (suitcase) of arbitrary size, and a new item to put into it.
You will need to take things out and repack them in order to
make enough room for the new item.  Least number of moves wins!

==================  T H E   L O N G   R U L E S  =================

I.  YOUR PROGRAM AND YOUR TASK IN SUMMARY

  You will be presented with a rectangular 2-dimensional "suitcase" of
  fixed size.  The suitcase will have several items in it, each of
  which will be rectangular.  You will also be given a rectangular 
  piece that is outside of the suitcase.  Your task will be to place
  the new object into the suitcase along with the objects that were
  in there at the beginning.  Each "move" consists of picking up an
  object and placing it in a vacant spot within the suitcase.  The
  final move will place the outside object into the suitcase.  Your
  objective is to accomplish the task in the smallest number of moves.

  Your program will read a file containing the description of the
  suitcase, the objects in it, and the object outside the suitcase.
  Your program will print the moves necessary to place the new object
  in the suitcase (if possible) according to the requirements.

II.  SOME SAMPLES

  In the examples that follow, an input file is presented (with some
  comments added) and then the program output for a sample solution
  is given (also annotated).

  AAAB_CC__D XX    Here's a 10x4 suitcase with 7 empty spots (_).
  AAAB_CCE_D XX    The task is to fit a 2x2 piece into the suitcase.
  AAA_FF_EGG
  HHHHHHHHHI    Looks like an easy one ... two moves should do it!
  
  E 1-5   (move the E piece into the fifth column in the 1st/2nd row)
		(it could have gone other places as well)
  X 1-8    (insert the X piece into the board in the now-open spot in
          the 8th column of the first row)
  
  
  AABBCC_I XXX    An 8x3 board with a 1x3 piece to fit in.  There are
  EEFGGHHI    three empty spots, but the are not next to one another.
  J_FKKDD_
  
  J 3-8    (move the J piece to the lower right)
  C 3-1    (move the C piece to the lower left - freeing 3 open in a row)
  X 1-5    (move the X piece into the freed-up spot!)
  
  
  AAABBBCCC___ XXX    A 12x4 board with a 3x3 piece to fit.
  AAABBBCCCDDD XXX
  EEEFFF___GGG XXX
  ___FFFHHHGGG
  
  H 4-1    (this is one solution - there IS a three-move solution)
  G 3-7
  D 1-10
  X 2-10
  
  
  PPPPBBBBCCCCDDDDEEEE XXX    The board will have at most
  PPPPBBBBCCCCDDDDEEEE XXX    30 columns (numbered 1-30 left-to-right) and
  PPPPBBBBCCCCDDDDEEEE XXX    15 rows (numbered 1-15 top-to-bottom)
  PPPPBBBBCCCCDDDDEEEE XXX
  ___GGG_________JJJ__        There will be at most 20 pieces (A-T) plus
  _K_GGG_F_H_____JJJ_I        the outside piece (always labeled X)
  ___GGG_________JJJ__
  LLLLMMMMNNNNOOOOAAAA        There "may" not be a solution, even 
  LLLLMMMMNNNNOOOOAAAA        though there are enough empty spots!
  LLLLMMMMNNNNOOOOAAAA        (I don't think this one can be solved!)
  LLLLMMMMNNNNOOOOAAAA        You CANNOT rotate any pieces!
  
  NO SOLUTION    (there WILL be at least one no-solution in the finals!)


III.  SUITCASES AND OBJECTS

  A.  A suitcase will be a rectangle consisting of between 3 and 15 rows
      and between 3 and 30 columns ... thus there will be at least 9
      "spaces" and at most 450 "spaces".  
  B.  Each "space" will be defined by an ordered pair defined by the
      row number (from 1 to 15) and the column number (from 1 to 30).
      The upper left "space" is 1-1; the lower right "space" in the
      largest possible suitcase is 15-30;  the upper right "space" in
      the largest suitcase is 1-30 (row 1, column 30).  A hyphen (dash)
      is used to separate the row and column values.
  C.  Each unoccupied "space" in the suitcase will be marked with
      an underbar in the input file.

  D.  An object will be a rectangle consisting of between 1 and 15 rows
      and between 1 and 30 columns ... thus the smallest object is 1
      space big and the largest is the size of the suitcase in any
      given problem.  An object will not be larger than the suitcase.
  E.  An object will be represented with an upper case letter.  There
      will be at most 20 objects in the suitcase to begin the problem,
      beginning with object A, then B, and so forth until all objects
      are represented.  No letters will be skipped.  At most, the letters
      A through T will be used to represent these 20 objects.
  F.  The position of an object inside the suitcase is defined by the 
      "space" occupied by the upper left-hand corner.
  G.  The object that is initially outside the suitcase is always
      marked with the letter X and follows he same rules as other objects
      except that it has no starting position within the suitcase.

  H.  An object may be placed in a position within the suitcase if and
      only if ALL spaces the object will occupy are currently empty.
      (This is slightly different than how Diablo II works.)
  I.  The object may not have any parts that fall outside the suitcase.
  J.  objects may NOT be rotated or "turned over" - the orientation of
      all objects (and the suitcase) will remain as presented in the
      original problem.

IV.  THE INPUT FILE FOR YOUR PROGRAM

  A.  Well - the input file will look like the examples above ... your
      program must take a single argument containing the name of the
      file which will contain the problem definition.
  B.  There will be as many lines in the file as there are rows
      in the suitcase.  There will be only one problem per file
      and only one file per program execution.
  C.  The only whitespace in the file will separate the suitcase
      definition from the "outside X-marked" object.  The outside
      object's upper left corner will appear on line ONE of the
      file following ROW 1 of the suitcase and a single space.
  D.  The suitcase and all objects are as defined above - only upper
      case letters A-T will be used to represent objects inside the
      suitcase, the character "_" (underbar) will represent vacant
      spaces in the suitcase, and "X" will represent the outside object.
  E.  Objects will be assigned letters without skipping letters, but
      there will be no particular way in which the objects are
      lettered within the suitcase.  (i.e. ... if there is no object
      labelled "M", then there will be no objects N-T either.)
      (Object A may be at the lower right, upper left, or wherever!)
    
V.  YOUR PROGRAM OUTPUT

  A.  Each line of your output represents one "move" - the placement of
      an object into an available set of unoccupied spaces in the suitcase.
  B.  A "move" consists of a letter (defining the object to be placed) and
      a row-column ordered pair (indicating the row and column of the 
      empty spot in the suitcase where the upper left corner of the 
      object will be placed).
  C.  The letter representing the object to be moved is the first 
      character on the line, folowed by a space, followed by the ROW,
      followed by a hyphen (-), followed by the COLUMN
  D.  The final output line will move the object "X" into the suitcase.
      Moves prior to the final move will move the objects that start
      out in the suitcase to different positions in the suitcase.
  E.  In the event that you find that it is impossible to place the
      object "X" in the suitcase, your program should output a single
      line that contains the text: "NO SOLUTION".

VI.  SCORING AND WINNING
  
  A.  Your score for a given problem is the number of moves it takes
      you to place the X object into the suitcase (along with all the
      other objects of course!).  Small numbers of moves is good - the
      fewer moves you use, the better your score.
  B.  The finals will consist of five suitcases - each of which your
      program must solve independently.  Your score on the finals will be
      the sum of the moves on all the problems.
  C.  A correct indication of "NO SOLUTION" will score one point.  An
      incorrect indication of "NO SOLUTION" will score 999 points.
  D.  In the event of ties, the entries that tie will solve an
      additinal set of problems chosen from problems submitted by 
      the participants.
  E.  If entries remain tied, the FASTEST entry will win as measured
      by the accumulated  time taken over all problems.

=============================================================================
    The following items are standard stuff for ALL the POTMs ....
    (but they occasionally will change ... so READ 'EM!)
=============================================================================
I.  About your programming:

    a) Since 9/98 the POTM compiles and executes on and Ultra-2:

        potm potm 5.5.1 Generic_103640-17 sun4u sparc SUNW,Ultra-2
        The Ultra-2 I'm on has 128Mb physical
        memory and 350Mb virtual memory.  It runs Solaris 2.5.1.
	cpu0: SUNW,UltraSPARC (upaid 0 impl 0x10 ver 0x40 clock 200 MHz)

        I must insist that your entry be contained in
        a SINGLE ASCII file, mailed in plaintext from a mailer that
        does not split long lines or insert strange characters.  
        Please help keep my life simple!!!

    b) The compilers I have available are (at least):

        Sun WorkShop Compiler C 4.2         (ANSI C Compiler SVID compliant)
        Sun WorkShop Compiler C++ 4.2 
        GNU compilers gcc/g++ version 2.8.1

*** C/C++ Note:  please do not use platform dependent include files
***   (like conion.h for example) since they will cause my compilation
***   to fail.  If YOU need them, consider using ifdefs so that only
***   YOUR compilation will see them ... thanks!

        PERL version 5.004
	Python 1.5.1
        Java, version 1.1.6 of the Java Developer Toolkit from SUN
                (as downloaded to a SPARC workstation)

        FORTRAN compilers from SUN, sorry - no PASCAL support!
        FORTRAN 90: WorkShop Compilers 4.2 10/22/96 FORTRAN 90 1.2
        FORTRAN 77: WorkShop Compilers 4.2 30 Oct 1996 FORTRAN 77 4.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 are permitted, if there are special instructions
    please so indicate in your program header comments.

***      IMPORTANT:  submit early so we can resolve any
***      portability problems!!!  (Particularly if you 
***      are working in a PC environment.

       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!!!
         Also nawk, awk, dc, or whatever.
         (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) sizeof(short)=2; sizeof(int)=4; sizeof(long)=4; sizeof(char)=1

    h)       a    = 0x80000000  = -2147483648
         a - 1                  =  2147483647
         a + 1                  = -2147483647
           {a} is true.  
           {a == 0} is false.

    i) RAND_MAX = 2^15 - 1 (32767) when using the rand() function.

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!
         Use the POTM bulletin board at:
         http://www.sitepowerup.com/mb/view.asp?BoardID=100152

    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 the
       specified time limit (usually ten 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 your machine 
       and mine.  All execution time measurements used for 
       tiebreakers (if any) will be measured using (sys+user) 
       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 @ att.com                       (preferred)
         hicinbothem @ att.com                 (use only as a last resort!)

WARNING!!!  Please be sure your mailer does NOT truncate long lines
    or make any substitutions for characters.  These kinds of problems
    will prevent the program from compiling when I receive it!

    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:  These comments should be referenced in whatever method
    is appropriate for your programming language of choice.

    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 week 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 @ att.com)
=Fred












Make your own free website on Tripod.com