When I was a kid, I had a little toy with 15 number tiles in a 4x4 frame
arranged so that I could slide the numbers around and put them in order.
If memory serves (and it frequently doesn't), the puzzle was attributed
to Sam Lloyd and was called Lloyd's Fifteen puzzle. Hence, we have the
seeds for the next Programmer Of The Month (POTM):
* * * L L O Y D ' S D I L E M M A * * *
ABCDE Imagine 24 tiles, with the upper case letters A through X.
FGHIJ These tiles are in a 5 by 5 frame such that they cannot
KLMNO slide outside the boundary of the frame. The empty spot
PQRST in the square is marked with a "+" for our convenience.
UVWX+ The figure at the left represents perfection. Your goal
will be to achieve perfection when starting with chaos.
======================= THE DETAILS - SINCE YOU ASKED ========================
I. THE SQUARE AND TILES
The square is a five by five array consisting of 25 "spots".
There are 24 tiles labelled with upper case letters (A-X inclusive).
There will always (duh) be a single empty spot in the square which
is denoted with a "+" (plus sign) in the opening square.
The starting arrangement of the tiles within the square will be provided
in a file whose pathname is given by ARG1 (see I/O below)
II. THE MOVES
At your disposal are five moves, each of which describes the movement
of a tile into the empty spot. There are the obvious four: LEFT,
RIGHT, UP, and DOWN plus a new wrinkle: TRANSPORT (which moves the
center tile to the empty spot).
d=down For example, move the T into the empty spot above.
u=up This is an illegal move in the setup above since there
is no letter which can move "up" into the empty spot.
r=right This would move the X into the empty spot.
l=left Again, this is not legal in the above setup - by the way,
that's an "ELL" and not a "ONE".
t=transport This move takes whatever square is currently in
the center spot (e.g. the M above) and transports
it to whatever spot is empty. This move wasn't
part of the original puzzle, but what the heck!
(ALSO: this guarantees that ANY starting arrangement
can be made into perfection ... without the TRANSPORT
move this is NOT the case - I remember this because
some joker switched two adjacent tiles on my original
puzzle and it made me crazy ... live and learn!)
Note that each move results in only a single square being moved.
Also note that each move results in the previously empty square
being filled. Unlike the physical puzzle, entire rows
or columns of tiles may not be moved at once - each tile
must be moved individually.
If you attempt to make an illegal move, your score will be zero.
A transport move when the center square is empty is illegal (and silly!).
III. THE TASK and THE SCORING
Write a program that reads a file with a jumbled square in it
and print out a series of moves that will cause it to become
perfection when the moves are applied in order.
ONE JUMBLED SQUARE WILL BE PRESENTED FOR THE FINAL TEST:
a) Winner is the program that comes closest to perfection (most
tiles in their finished spots) within 10 minutes .
Perfection is the square at the beginning of this mail.
If (as expected) there are several who actually achieve
this perfection, the first tiebreaker is applied ....
b) Given a tie on (a), then the minimum number of moves will win.
If some entries have the same number of moves, then ....
c) The solution with the fewest transport (t) moves will win.
If some have the same number of transport moves, then ....
ALL PROGRAMS THAT REACH THIS STAGE ON THE SINGLE FINAL PROBLEM
WILL ENTER THE GRAND FINALE (if necessary).
10 squares will be presented to any entries that remain ...
a) most perfect squares achieved in 10 min per square - if tied then
b) fewest total moves on ALL squares which achieved perfection
c) fewest total transports on ALL squares which achieved perfection
d) fastest program - as measured by (hopefully it never
gets to this point!!!)
IV. INPUT/OUTPUT
ARG1 is the pathname of the input file containing a jumbled square.
I guarantee that this input file will be readable and will:
* be 30 characters long (as shown by ls -l)
* have five lines, each of which contains five characters
and a newline - with no embedded white space
* have one and only one each of the characters (A-X and +)
for a total of 25 non-white-space characters.
(UPPER case will be used in the input file)
You may use other arguments for debugging, but your program must
run with only a single argument. Your program should ignore stdin.
Your program output should consist of a string of characters chosen
from the lower case set of (durlt) describing down, up, right, left,
and transport respectively. (LEFT IS REPRESENTED BY THE LETTER "l")
This string should completely describe the ordered set of moves to
make to the jumbled input square. Do NOT output any white space.
DO output a newline ("\n") at the end of the string.
For example, if your program prints out dddrrdt it is describing a
sequence of three down moves, followed by two right moves, followed
by a down move and a transport. This would result in the following
if we started with the perfect square:
ABCDE ABCDE ABCDE ABCDE ABCDE ABCDE AB+DE ABMDE
FGHIJ FGHIJ FGHIJ FGHI+ FGH+I FG+HI FGCHI FGCHI
KLMNO d KLMNO d KLMN+ d KLMNJ r KLMNJ r KLMNJ d KLMNJ t KL+NJ
PQRST PQRS+ PQRSO PQRSO PQRSO PQRSO PQRSO PQRSO
UVWX+ UVWXT UVWXT UVWXT UVWXT UVWXT UVWXT UVWXT
(note: your program should NOT print out any intermedate or final
squares ... only the sequence of moves it derives.)
V. 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 version 2.6.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.
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!!!!
II. The system testing ....
a) ship 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 no more than two a week 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 them once a night but perhaps not!)
d) please make sure your program works with the system test square.
e) your program must perform the task specified within a reasonable
time (varies with problem - but ten minutes is the norm)
(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).
III. SENDING ME YOUR ENTRY - PLEASE USE EMAIL!!!
Please email (not uuto) your source code to me at:
enter@potm.att.com (preferred)
enter@potm.ffast.att.com
attmail!hicinbothem (will forward correctly but
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) */
/* compilation 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 within a day or two.)
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
attmail!hicinbothem .... hopefully all my mail-path bugs are worked out!
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!!!
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.att.com)
=Fred