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.

        ******      Q U I L T S       ******
     (deadline is midnight Sunday Dec. 13, 1998)

While going through my late grandmother's trunk, I found several hundred small squares (about 6 inches by 6 inches) of material. She had apparently been planning to sew them together to make a quilt. Each square had a distinct color on each of its 4 sides. Obviously, she had intended to arrange the squares so that the sides next to one another were of the same color.

I sat down to try and arrange the small squares into as large a quilt as possible ... but it was TOO HARD for me so I've decided to appeal to the POTM community for some help. I'll give your program a description of the squares, and your program will arrange them into as large a quilt as possible!


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

I.  YOUR PROGRAM AND YOUR TASK IN SUMMARY

     A.  Your program will read an input file which contains
          one line for each small square you have to work with.
          The path of the input file will be the single
          argument to your program.

     B.  Each line of the input file will have a Number which 
          uniquely identifies the square, and the list of the 
          four colors which are on the edges of the square.

     C.  After reading the input file, your program will arrange
          the squares into a grid following the rules given
          below.  The most important rule is that two squares
          may be adjacent ONLY if their adjacent sides are the
          same color.  Your program then outputs the arrangement
          of the squares by printing out their unique numbers.

     D.  The POTM-Master (that's me!) will check your output to 
          insure it conforms to the rules and score your results.  

II.  SCORING AND WINNING

     A.  The goal is to construct as large a quilt as possible
          that is "square-like" itself.  Thus, a quilt that
          is square should score higher than one that is long
          and thin - even if the same number of squares are
          used in the construction.  The "score" for a quilt
          will be defined as the AREA divided by the PERIMETER
          of the quilt your program constructs.

          Thus, a quilt that is 10 x 6 squares will score:
               (10*6)/(10+10+6+6) = 1.875

          A quilt that is 12 x 5 squares will score:
               (12*5)/(12+12+5+5) = 1.7647

          Note that both quilts in this example use 60 squares.
          The first one scores higher since it is "squarer".

        THUS:  SCORE = AREA / PERIMETER of the constructed quilt.

          The highest score achieved on the finals will win.

     B.  If two or more entries have the same score, the following
          tiebreaker will be applied.

          TIEBREAKER = smallest number of different colors on 
                    the edge of the fully constructed quilt

          The final quilt will have an exposed "edge" around
          the perimeter of the quilt.  I will count the number
          of different colors on the edges of the squares
          which are exposed to the outside (do not abut any
          other squares).  The SMALLEST number of different
          colors will serve to break the tie - a low number
          of different colors on the edge is GOOD.  If the
          entire edge was one color, then the TIEBREAKER score
          would be 1 ... the best possible.

     C.  If two of more entries have the same tiebreaker, the tie
          will be resolved in favor of the FASTEST program
          to achieve the result.  I do NOT expect this criteria
          to be applied and hope to resolve a winner with the
          two criteria above.  The timing measurement is taken 
          using timex  time on the final run.

     D.  The final run will present a collection of 1000 or fewer
          squares to your program.  There will be only a single
          final problem (in some past POTMs there have been
          multiple problems in the final run).  The POTM-master
          will judge the result and determine the winner using
          the above rules.  My decisions are final.  The POTM-
          master will define the final problem according to
          whatever criteria I feel like applying at the time
          (the squares may be random, or they may not, I just
          haven't decided yet!).

     E.  As the contest progresses, the entries received to date
          will execute a "SYSTEM TEST" to insure proper behavior
          of the problem.  Weekly results of these runs will
          be posted, but they will not factor into the
          determination of the eventual POTM winner.  Actual
          resulting quilts will not be posted, but scores will be.

III.  THE SQUARES AND THEIR COLORS

     A.  Each square will have one input line and will be identified
          with a unique reference number.

          i)   There will be at most 1000 squares for each problem.
          ii)  The unique identifiers will be the numbers 1 through
               N where N is the number of squares.  N will also
               be the number of lines in the input file.
               N <= 1000.
          iii) The input file will be sorted by unique number.

     B.  Each square will have four sides which will each be marked
          as having a specific color.  
          
          i)   There will be at most 26 colors used in each problem.  
          ii)  The colors will be denoted by the letters A through
               Z in upper case letters in the input file.
          iii) The input file will indicate the colors of the four
               sides by providing four upper case letters in
               the following order:  NORTH EAST SOUTH WEST
               (that is - in "clockwise" order) separated by
               a single space.
          iv)  For example, an input line for square number 17 might be:

               17 A B C D

              which describes a square looking something like:

              _AAAA_          The north side is color "A"
              D    B          The  east side is color "B"
              D    B          The south side is color "C"
              D    B          The  west side is color "D"
              D    B
              _CCCC_     

      (note that the corners are not marked in this representation)

     C.  Each square may be rotated clockwise 90, 180, or 270 degrees, 
          but it may NOT be turned over.  Thus, square number 17 above
          may be used in any of the following four representations:

                 N E S W     The directions of the sides
                =========
                 A B C D          (this is 17,0 - no rotation)
                 D A B C          (this is 17,90)
                 C D A B          (this is 17,180)
                 B C D A          (this is 17,270)

          but this is NOT equivalent to the square A D C B which
          you would get if you "turned over" the quilt square.
          To emphasize:

   >>>     ROTATING A SQUARE IS OK, TURNING OVER A SQUARE IS FORBIDDEN. <<<

         Regardless of which input line I provide for square 17,
         you may use any of the four legal orientations in your 
         solution.  You may NOT use any of the "turned over" 
         orientations unless they are represented by a different
         input line.  Also ... once you use square 17 in ANY
         orientation, you may NOT use it again in another orientation.

     D.  The input file may contain several lines with equivalent
          or identical squares ... or it may not!

     E.  An individual square may have four different colors on
          the four sides, or it may repeat colors in any way
          on any side.  Thus, a square may have sides with 4,
          3, or 2 different colors, or it may have all four
          sides with the same color.


IV.  THE RULES FOR ATTACHING SQUARES

     A.  Each square in the input file may be used only once.
     B.  You do not have to use ALL of the squares - use as many
          or as few as you like.
     C.  You may rotate a square to use it, but you may NOT turn
          it over (see II.C above).
     D.  You may use each square only ONCE.
     
IV.  FORMAT OF YOUR OUTPUT

     A.  THIS IS IMPORTANT ... PLEASE PAY CLOSE ATTENTION TO THE
          FORM OF YOUR OUTPUT SINCE THE SCORING PROGRAMS WILL
          GIVE YOU A SCORE OF ZERO IF YOUR SOLUTION CANNOT BE
          FIGURED OUT ...

     B.  Your final quilt will consist of a collection of squares.
          Each square will have a unique number (1-1000), a
          particular rotation (0,90,180,or 270 degrees), and a
          particular location in the final quilt.

          Each square will be defined by its number followed by 
          a comma and then its clockwise rotation.  For example:

          735,0     is square number 735 in its original orientation
          32,270     is square 32 rotated by 270 degrees (see III.C)
          1000,90     is square 1000 rotated by 90 degrees

          Note that only rotations of 0,90,180, and 270 are acceptable.

          Note that even if a square is NOT rotated, the ",0"
          must still appear afer the unique number of the square.

     C.  The quilt is constructed from squares by printing each row
          of the quilt on a single line of output as a collection
          of squares.  Perhaps an example is best:

          735,0  32,270 99,90          (line one of output)
          100,90 14,180 22,0           (line two of output)

          shows a quilt with 6 squares in it arranged in 2 rows
          (or lines) and 3 columns.  Each square in the quilt
          is denoted with its unique number and the number of
          degrees the original definition is rotated (see III.C).

          The POSITION of a square will be defined by the row (line)
          and column in your output.  Thus, square 735 in the
          above example is at the NORTHWEST corner of the quilt
          and sqare 99 (rotated by 90 degrees clockwise) is at the 
          NORTHEAST corner of the quilt.
          Similarly, square 100 rotated by 90 degrees is in the SOUTHWEST 
          and square 22 is in the SOUTHEAST corner.

     D.  If your rows extend beyond 80 characters, this is fine.  ONLY
         break a line (with CR/NL) when you intend to mean that the
         row of your quilt is complete.  You may use tabs or blanks
         between your squares if you wish but there must be some kind
         of white space (at least one tab or space) between squares.
         There should be NO space on either side of the comma used in
         each square definition.

V.  FORMAT OF THE INPUT FILE and AN OUTPUT FILE - A SAMPLE
        This is a sample file with 25 quilt squares ... I have no
        idea what the largest possible quilt might be ... enjoy!
        (Note - a sample 2x2 solution is shown at the right)

1 R W B G
2 G G G G
3 R W B G
4 A R R B
5 B R G G
6 G B W R
7 G G G G
8 R G R G                 This is a sample 2-line output solution:
9 W W W G
10 W R G B                14,0   18,180
11 B A A A                22,270 25,270
12 B W A B
13 Z A B G
14 B B B B                Graphically ... this would look like:
15 B G B G
16 R G B B                _BBBB_ _GGGG_
17 G B G B                B    B B    G
18 B B G G                B    B B    G
19 F G W R                B    B B    G
20 F F R W                _BBBB_ _BBBB_
21 R G F F                _BBBB_ _BBBB_
22 A B G W                A    G G    G
23 F W B G                A    G G    G
24 B G B B                A    G G    G
25 G B G G                _WWWW_ _GGGG_

=============================================================================
    The following items are standard stuff for ALL the POTMs ....
    (but they occasionally will change ... so READ 'EM!)
    9/98 key changes:  Now an Ultra-2, email entries to enter@att.com
=============================================================================
I.  About your programming:

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

        potm potm 5.5.1 Generic_103640-17 sun4u sparc SUNW,Ultra-2

        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 me keep my life simple!!!

    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

*** 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.002
        Java, version 1.1.6 of the Java Developer Toolkit from SUN
                (as downloaded to a SPARC workstation)
        Scheme48 - a Lex variant
        Python 1.4 (Nov 27 1996) 

        PASCAL - hope to have the SPARC Pascal compiler
        FORTRAN - hope to have the SPARC FORTRAN compiler

    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.

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