PROBLEM NAME

A I M L E S S

Navigate a multi-story building: come in the front door, wander aimlessly around visiting as much of the building as possible, and exit where you came in. Of course - you don't want to visit anyplace twice. Longest trip found in the time limit wins! Most ups and downs breaks any ties!

Welcome to the SUMMER 1996 POTM ... deadline midnight on 9/1/96 !!!
(Please do not be afraid of all these details ... the intent of most POTMs
  is straightforward, but I've found that I need to be very explicit to try
  and close any "loopholes" for all you "requirements lawyers" out there.)

I.   WHAT DOES YOUR PROGRAM HAVE TO DO?

	Your program must read in the maps of the "floors" of a multi
	story building.  Each floor will be divided into "squares".
	The floors will each indicate (using "#") which squares MAY NOT
	be visited, and will indicate (using spaces " ") which squares 
	MAY be visited.  The single "entry" and "exit" square is marked
	with the letter "E" and will always be on the first floor.  Your
	path must not step on any of the building squares more than once.

	Beginning at the "E" square, your program must print out a
	string of moves ... each move may be either north, south, east,
	west, up, or down (n,s,e,w,u,d respectively) ... that starts at
	the "E" square and eventually ends at the "E" square.

	The moves are subject to the definitions below.  your path must
	NOT touch any square more than once (other than the "E" square 
	at the beginning and the end).

II.  HOW ABOUT A SIMPLE EXAMPLE

	The sample below illustrates the input file for a simple 4 story
	building - with each floor having 5 rows and 11 columns.  The
	sample below (TO THE LEFT OF THE DIVIDING BAR) illustrates the
	input file ... everything to the RIGHT of the bar is explanatory
	material only.

	The first line of the input file contains four fields:
		1) the number 1 (indicating this is the first floor)
		2) the number of "rows" on each floor (5)
		3) the number of "columns" on each floor (11)
		4) the number of floors contained in the building (4)
			(each floor is the same size and shape)

1 5 11 4	|	FLOOR  ROWS  COLUMNS HEIGHT	(on first line only)
###########	|	###########	The "E" shows the entry/exit square.
   #####  #	|	1  #####  #	The "1's" show the possible first
E       ###	|	E1 ########	squares of the trip (they also may
         ##	|	1        ##	be the next to last squares of the
###########	|	###########	trip) which starts and ends on "E".
2		|		FLOOR (each new floor is preceded with a number)
###########	|	###########
## #      #	|	## #      #	Note that the markings on the right
# #       #	|	# #    d  #	side are for illustration only ....
## #      #	|	## #      #
###########	|	###########
3		|		FLOOR 3 follows:
###########	|	###########	Starting at the location marked with
# # #     #	|	# # #  n  #	"O" ... the squares marked with the
#  #      #	|	#  #  wOe #	"d,n,s,e,w, and u" show the six
#  #      #	|	#  #   s  #	possible squares resulting from these
###########	|	###########	moves ... none were blocked by "#".
4		|		FLOOR 4 follows:
###########	|	###########
#  ###    #	|	#  ###    #	Note:  "u" means moving to a higher
#   #     #	|	#   #  u  #	floor ... later in the file.  The
#  ###    #	|	#  ###    #	floor numbers are given before each map.
###########	|	###########

III. TELL ME MORE ABOUT MOVES AND THE FLOOR MAPS

	1) Your program output must be a string of lower case letters
		denoting the path that begins at the entry square and
		finally ends back on that square.  Each possible move
		is defined by a letter as follows (see example above):

		   

		n = north moves to the next lower row
		s = south moves to the next higher row
		e = east moves to the next higher column
		w = west moves to the next lower column
		d = down moves to the same row and column one floor down
		u = up moves to the same row and column one floor up

		After your final move, output a newline.  Your program
		output is one long line of moves.

	2) You may only move to squares which are blank spaces (" ") and
		to which you have not moved before.  You may NOT move to
		squares marked with a "#" and your path must NOT retrace
		any of the squares it already covered.  The exception to
		this last rule is the "E" square which MUST be both the
		starting and ending square.

	3) THE ENTRY/EXIT SQUARE:  will be marked with an "E" on the first
		floor map.  The "E" will always be in column one and the
		squares immediately "north" and "south" of "E" will always
		be valid moves.  The "E" will NOT be in the corner of the
		first floor.  Except for the "E" and the squares immediately
		to the north and south of it, all other squares in column
		one on floor one will be marked with "#".

	4) Each floor will contain exactly the same number of rows and
		columns (as defined by the first line of the input file).
		The first and last rows will always contain only "#"
		markings.  Except for the three squares described in
		rule 3) above, the first and last columns will always contain
		only "#" markings.  Each floor is fully contained except
		for the three squares in rule 3).  There are no "windows"
		in this building.

		THERE WILL BE BETWEEN 5 AND 20 ROWS TO EACH FLOOR.
		THERE WILL BE BETWEEN 10 AND 80 COLUMNS TO EACH FLOOR.
		THERE WILL BE BETWEEN 2 AND 10 FLOORS IN EACH BUILDING.

		These building dimensions will be defined on line one
		of the input file.  Thus, there may be as many as 1,600
		squares on each floor (counting the boundaries) and as
		many as 16,000 in the entire building.

	5) Aside from the boundaries, each floor may contain any number of
		prohibited squares marked with "#".  Any floor may contain
		zero "#"s other than the boundary, or may be completely
		filled with "#"s.  The latter situation would obviously
		block movement past this floor.

	6) There is no movement allowed below the first floor or above
		the top floor ... you cannot move "d" from the first floor
		or "u" from the top floor.  No basement, and no roof!

IV.  THE SCORING - HOW TO WIN!

    The input to your program will be a single argument containing the
    path name of the input file.  Your program should read this file 
    to derive all information on the size and number of floors, as well
    as the maps of each floor.  See V. below for the input file formats.

    The output of your program will be be a string of lower case letters
    (nsewud) describing the moves you will make to traverse the building
    and return to the "E" square.  Your output concludes with a newline.

    First Score:  The winner will be the program which outputs the longest
    string of valid moves ... where a valid move is described above.  long
    aimless walks around the building visiting alot of squares are GOOD!

    Second Score:  In the event that more than one program has the most
    number of moves, the winner will be the path that contains the most
    ups and downs.  (Since the number of ups = the number of downs in
    any valid path, this tiebreaker will be the number of "u"s in
    the valid path.)  Lots of ups and downs is GOOD!

    Final Tiebreaker will be the execution time as measured by
    	 timex time taken on the final test.  Fast is good.
	Long is bad.  More than 10 minutes is disqualified!

	THE FINALS WILL CONSIST OF THREE BUILDING DEFINITIONS.  THE
	SCORES ON ALL THREE BUILDINGS WILL BE ADDED TO DETERMINE
	THE FINAL PLACEMENTS.  THE BUILDING DEFINITIONS MAY BE
	RANDOM OR DIABOLICAL AT THE WHIM OF THE POTM-MASTER.
	Tiebreakers are only applied if the sum of the moves over
	the three runs is identical.

V.  INPUT/OUTPUT

	1) The output must be ONLY the string describing the moves.  The
		output must appear on standard output.

	2) NO OUTPUT to stderr is permitted.

	3) All input is derived from the file whose pathname is contained
		in the single argument to the executable program:
		e.g.:  myprogram filename

	4) The format of the input file will be as follows:
		a) line 1 contains four non-zero integers:
		   the number 1 (indicating this is the first floor)
		   the number of "rows" on each floor    ( 5 <= R <= 20)
		   the number of "columns" on each floor (10 <= C <= 80)
		   the number of floors in the building  ( 2 <= F <= 10)
		b) lines 2 through R+1 (R=the number of rows) contain the
		   map of the first (ground) floor.  Each of these lines
		   will contain exactly C characters followed by a newline.
		   (C=number of columns)  Each of these C characters will
		   be either a "#", a " " (space), or an "E".
		c) the remainder of the file will contain R+1 lines for
		   each of the remaining floors .... the first line will
		   contain the floor number.  The next R lines will contain
		   exactly C characters (either "#" or " ") followed by
		   a newline.
	    The sample above (in II) provides an example of an input file for
	    a four story building ... ignore everything to the right of the
	    map shown to the left of the bar in the example above.

VI.  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/g++ version 2.7.2
	PERL version 5.002
	Java version 1.0
	Scheme48 - a Lex variant

    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.

         also  perl, version 5.000
	 also  java, version 1.0 of the Java Developer Toolkit from SUN
		(as downloaded to a SPARC workstation)

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

    g) Maximum malloc'able space is a bit over 50 Meg ....

    h) sizeof(short)=2; sizeof(int)=4; sizeof(long)=4; sizeof(char)=1

    i)	 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 10 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 yours and mine.
       All execution time measurements used for tiebreakers (if any)
       will be measured using  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@potm.ffast.att.com		(preferred)
         hicinbothem@att.com		 (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)		*/
    /*  compile 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 in a day or so)

    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 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@potm.ffast.att.com)
=Fred












Make your own free website on Tripod.com