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