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