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
Make your own free website on Tripod.com