|
|
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:
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)
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!
=Fred
|
