Entry Summaries

The attached mail is the collection of write-ups I received. As usual they are mostly unedited (only personal POTM-master insults were removed). Write-ups are provided in order of finish (more or less).


======================================= Spelunker =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Spelunker       23084 3645 1771 5768/942  8320/1316 8996/1387 =Andre Wilhelmus
=================
Spelunker was submitted by =Andre Wilhelmus at awilhelm@hvsca01.nl.lucent.com
=================
HOW DID Spelunker approach the task?  Special tricks?

  It reads the building.  Every room (node) has an array of pointers for the
  available directions (edges).  Every direction (edge) has pointers 
  to the next and the previous room (nodes).  This is done to get 
  rid of those 3D array indices.
  
  Attempts alternate between ns and sn as initial path.
  
  For every room in the path, it looks for an adjacent room which is not
  in the path.  The next room in the path should have unused directions
  because the path extension must end in that room.  This strategy prevents
  removing a part of the existing path and wasting time to check if the new
  extension path is longer than the path to be removed.
  The adjacent room which is not in the path is put in a list and a width
  first search, I think (I should really add more comments to my program,)
  is used to find its way back to the path.
  The search prefers directions to rooms with the least number of free
  directions with the least number of free directions.
  Directions with an equal score are chosen randomly to allow multiple
  attempts.
  
  When no more extensions can be added, the above procedure is repeated
  again using the current path but now the end of the extension path
  is allowed to be anywhere in the current path.  The new extension
  path should be longer than the path to be removed.
  
DID Spelunker iterate in any way?  How did it know it was done?

  It tries multiple attempts until time runs out.  The path with the
  highest number of rooms and the highest number of ups is kept
  (the number of ups is ignored during path search.)
  
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

  A good evaluation function is very important as well as finding out why
  the largest building could not even be completed within 10 minutes (an
  earlier Spelunker version.)
  For debugging, the path is checked against the building to see if the
  path is correct.  This did not help me when the largest building was up
  because the input was not fully checked and whole outer walls
  disappeared because of a bug.
  
WHAT DO YOU DO FOR A LIVING?
  Writing/maintaining C++/C/Fortran programs.
FOR FUN?
  Learning to write Hiragana.
  Playing Day of the Tentacle / Maniac Mansion on my Mac.
INNERMOST SECRET?
  Bishoujo Senshi... ^_^
POTM IDEAS?
  Nope.
  
=================================================================

======================================= stalker =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
stalker         22862 4612 1398 5732/911  8212/1547 8918/2154 Mihai Badoiu
=================
stalker was submitted by Mihai Badoiu at mihaib@lbi.sfos.ro
=================

HOW DID stalker approach the task?  Special tricks?

  Stalker is using some backtracking techniques combined with some heuristics. 

  Stalker is trying to maximize a cycle "E->A->B->E" by finding another 
  path from A to B (A->B) bigger than the current one using only building 
  squares that have not been used.
  Example:
  
  ###########
     #####  #
  E       ###
           ##
  ###########
  
  The initial cycle is "NS", "SN" or "EW".:
  Initial cycle (NS):
  ###########
  1  #####  #
  2       ###
           ##
  ###########
  
  After first maximize(NESW):
  ###########
  12 #####  #
  43      ###
           ##
  ###########
   
  After the second maximize(NESSWN):
  ###########
  12 #####  #
  63      ###
  54       ##
  ###########
  
  A possible maximize:
  ###########
  123#####  #
  8 4     ###
  765      ##
  ###########
  
  ... and so on.

  The A->B path is founded using some backtracking techniques. To find 
  a better path I used some heuristics: the backtrack function is 
  trying first the neighbor squares that have 1 neighbor then 2 
  neighbors, 3,4 and at last 5 neighbors. When a square is selected 
  in the path it became inactive, so we have to decrease the number 
  of neighbors of its neighbors.
  Stalker maximize the cycle while there are A->B paths.

DID stalker iterate in any way?  How did it know it was done?

  Stalker is a nice program. I hope not to run out of time!

WHAT DO YOU DO FOR A LIVING? 

  I am currently a student at Computer Science High School of Bucharest. 
  I am also working as a programmer at a small software firm in Bucharest 
  named "CERTEH S.R.L."

FOR FUN?

  I like sports very much. In my free time I play basket-ball, soccer and 
  volley-ball. I like reading and watching SF movies. STARTREK is one of 
  my favorite movies because of its modern equipment and treating future 
  problems. I like listening to rock and classic music as well. 

INNERMOST SECRET?

  "For tomorrow may rain, so I'll follow the sun."

=================================================================

======================================= mowing3D =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
mowing3D        22564 2410 1408 5636/696  8018/965  8910/749  Bob Hall
=================
mowing3D was submitted by Bob Hall at hall@research.att.com
=================
HOW DID mowing3D approach the task?  Special tricks?

  Mowing3D uses depth-first search (DFS) as its fundamental primitive operation.
  It starts out by finding any cycle (using DFS) starting/ending at E.  It then
  walks along the current cycle a step at a time.  At each step S it uses DFS to
  try to find a "side trip" that re-enters the path somewhere (call it F) such
  that if we replace the segment from S to F along the cycle with the side
  trip from S to F we get a longer cycle.  It then just keeps on trying this,
  always lengthening the cycle, until it can't find any way to lengthen it.
  
  Now, there is the question of in what order does the DFS search examine
  neighbors of a node.  That is, does it look up/down/east/west/north/south
  first, what next, etc.  Mowing3D simply tries the procedure described in
  paragraph 1 above 720 (=6!) times, once per each choice of fixed preference
  order.  That is, the first time it might try prefering neighbors in the
  order "UNEWSD" and then rotate through all 720 permutations of those six
  letters.  Of course, I have to have code to stop myself after 10 minutes if
  necessary, possibly before having examined all the permutations.  Therefore,
  I examine the orders in a "fair" way (with respect to the 3-space symmetries)
  so that I'm not biased into only examing a few general directions.
  
DID mowing3D iterate in any way?  How did it know it was done?
  
  As described above, it iterated two ways: first in going through the 720
  permutations of "UNEWSD" and within each of those, it iteratively improved
  the path by looking for extending side trips.  It knew it was done by
  either getting through all 720 permutations or by 10 minutes being up.
  
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
  
  WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?
  * Research in agents, artificial intelligence, and software engineering.
  * Fun? what's that?
  * POTM idea: how about competitive "Connect Four" playing programs?
    (Connect Four is a tic-tac-toe-like game played on a 6x7 grid. Each
     move consists of dropping your token in at the top of a column.  It
     ends up placed at the lowest unoccupied row.  The first player to get
     four in a row wins.  Their are many variations: varying the dimensions of
     the grid or the number in-a-row required to win; also, allowing the forming
     or a 2x2 box or 3x1 L to win as well, etc.)
  
  
=================================================================

======================================= sundew =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
sundew          22246 4194 1477 5600/584  7886/952  8760/2658 =Fred Hicinbothem
=================
sundew was submitted by =Fred Hicinbothem at fah@potm.ffast.att.com
=================
HOW DID sundew approach the task?  Special tricks?

  SUNDEW (South/Up/North/Down/East/West) starts at the main entrance and
  goes about the building making moves in priority order based on a
  priority array containing the six possible moves in some specific order.
  If it can make move ONE, it does - if not, then it proceeds to make move
  TWO, etc.  If it cannot make ANY move, it backs up and doesn't tread on
  that particular "dead end" again.  Eventually, it will either find the
  way back to the enter square or (in a case which is not allowed) mark
  everything as a dead end.  THEN ... walk the path and look for an
  adjacent pair of squares that can be added to the path somewhere in the
  middle ... and keep adding pairs until there are no more to add.

DID sundew iterate in any way?  How did it know it was done?

  The difficulty was in choosing the CORRECT sex-tuple of priorities since
  some worked better than others in different buildings.  So, since I had
  the time I tried all six factorial of them and kept track of which one
  scored best!  I checked the time just in case and tried to order the
  sex-tuples to try the "most beneficial" first.

ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

  Submit early to get the porting compilation bugs resolved ...

WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?

  Systems Engineer (whatever that is) for AT&T ... this is my fun ...
  I need a life ... stay tuned!

=================================================================

======================================= Ripple =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Ripple          22016 3694 1788 5464/940  7768/1257 8784/1497 Emerald Chung
=================
Ripple was submitted by Emerald Chung at emerald@research.att.com
=================

HOW DID Ripple approach the task?  Special tricks?

  Ripple creates an undirected graph out of the building.
  The vertices represent spaces in the building. 
  An edge connects two vertices if the spaces are next to each other.
  As its name, Ripple starts from a small cycle (for instance, sn)
  then gradually expands the cycle. 
  The cycle is traversed by pair in a depth-first order.  Each time,
  a vertex and its next vertex in the cycle are examined. 
  The shortest path (not going through any vertex already in the cycle)
  between these two vertices, if exists, is inserted into the cycle. 
  
DID Ripple iterate in any way?  How did it know it was done?
  
  Since each vertex may have more than one neighbors,
  their order in the data structure can be permuted to
  generate different results.  Ripple iterates on neighbor permutations. 
  
WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?
  
  I am working at Bell Labs, distributed software research department.
  I am also a mother of two boys, 6 and 3.
=================================================================

======================================= Harley_Hamilton =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Harley_Hamilton 21948 5871 1568 5330/1158 7772/1777 8846/2936 =Chad Hurwitz
=================
Harley_Hamilton was submitted by =Chad Hurwitz at churritz@cts.com
=================
HOW DID Harley_Hamilton approach the task?  Special tricks?
  
  It computes a 1-tree of all the verticies, and then adjusted the other than
  2-degree nodes accordingly to jimmy them into being 2-degree nodes.  (note:
  if all verticies are of two degree in a 1-tree you have a hamiltonian cycle,
  and a not so bad score.)  There were also weights put on flat edges so
  they would be less likely (than vertical edges) to be chosen in the 1-tree.
  
  After the 1-tree was adjusted or trained a good amount, I tried to open
  up the small cycle in the 1-tree to become larger by finding edges that
  connected between 1-tree branches.
  
DID Harley_Hamilton iterate in any way?  How did it know it was done?
  
  yes, if it could, it trained the one-tree and then tried to find a tour,
  if it could do this more than once with some randomity and additional
  training within the time limit, it did.
  
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
  
  why would people not wash?  it's really simple you just get in the shower (or
  bath if your prefer) and turn on the water.  be sure to get behind both ears,
  if your ankles can go that far.  actually i shouldn't talk...  just don't
  procrastinate, it's the root of all evil, see what it's doing to me?
  
WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?
  
  stuff, more stuff, some stuff again, the POTM master should import this
  info from previous answers.
  
  
=================================================================

======================================= I_want_a_guide =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
I_want_a_guide  21468 3392 1665 5144/900  7972/1216 8352/1276 Kurt VandenBranden
=================
I_want_a_guide  by Kurt VandenBranden at kvd2@bipsy.se.bel.alcatel.be
=================
HOW DID I_want_a_guide approach the task?  Special tricks?

 step 1. find any path through the building
   Starting from the start-position, I just go from position to position,
   until I am back at the start. 
   If the path is too short when I get back to the start, or when there is 
   no path back to the start, I use backtracking to try it some other way.
   How to decide what will be the next step:
     Every position in the building has a number assigned to it. This number
     is the number of free positions reachable from this position.
     I always go to the adjacent position with the lowest number assigned
     to it. This way, I always take the position first that is the more
     difficult to reach.
   
 step 2. try to make the path as long as possible
   This step is not easy to explain.  example:
     If the path I already found contains a 'north', I try
     to replace this with:
               east - north - west
	    or west - north - east
	    or up - north - down
	    or down - north - up
     if the corresponding positions are still free.
   You have to try to understand this graphically, it's like trying to
   put a bump on the existing path.
   This procedure is tried until the path has reached maximum length,
   and then you have the finished path.

DID I_want_a_guide iterate in any way?  How did it know it was done?

  Yes, I just keep searching for new solutions until I'm almost out
  of time.

ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

  I'm impressed with the speed of PERL.
  I thought I wouldn't have a chance against all the C- and C++ programs,
  but I think I did reasonably well.

WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?

  work: I'm a software-ingineer at a big telecommunications firm
  fun: running Linux on my PC at home, juggling, reading SF
  thanks Fred, for organising the POTM, I loved competing in it.

=================================================================

======================================= Get_Back =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Get_Back        21302 5672  595 5116/1235 7642/1791 8544/2646 Tim Ruhl
=================
Get_Back was submitted by Tim Ruhl at tim@cs.vu.nl
=================
HOW DID Get_Back approach the task?  Special tricks?

  I first generate a distance table that shows the shortest distance 
  from a point to the exit. This table is used for a heuristic to find 
  an initial path. Every step tries to go to the point that has the
  longest minimal path back. After each step a check is made whether 
  it is still possible to get back to the exit. This gives an initial 
  legal path.
  
DID Get_Back iterate in any way?  How did it know it was done?

  After the initial path is found, a check is made whether the path has
  somewhere a point as neighbor that is not reached in the current best path.
  If so, this unreached point is made part of the path that reached it
  and the same search strategy as described above is applied. Search stops
  when no improvements can be found by going to an unreached point from
  the current best path. An alarm signal is used to stay within the time limit.
  
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

  After every step a check is made whether the exit can still be reached 
  (that's why it is called get back). This search uses a heuristic based
  on the distance table and a heap to sort all possible moves.
  
WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?

  I'm a PhD student at the Vrije Universiteit Amsterdam. I'm working on
  parallel programming (the Orca parallel programming language, the Panda 
  portability platform).
  
=================================================================

======================================= Willie_Wundes =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Willie_Wundes   21290 4123 1374 5196/703  7594/1196 8500/2224 Dave Peterson
=================
Willie_Wundes was submitted by Dave Peterson at dpeterso@isd.net
=================
HOW DID Willie_Wundes approach the task?

  Brute force with simple bad route elimination.

Special tricks?

  Got better results with room/wall weights.
 
DID Willie_Wundes iterate in any way?

  Tried all six opening/ending rooms and all 720 direction orderings.

How did it know it was done?

  Either all possible methods tried, or timed out.

ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

  I came up with the name Willie_Wundes from "Death of a Salesman".
  Wundes is a dialect variation on wonders, using the six directions.
  (This contest is a Hamilton Path.  The Traveling Salesman Problem
  is a subset of the Hamilton Path Problem.)
 
WHAT DO YOU DO FOR A LIVING?

  Programmer level V for Applied Systems, Inc.

FOR FUN?

  Surf the Internet!

INNERMOST SECRET?

  More time to work on the latest POTM.

=================================================================

======================================= antFarm =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
antFarm         21170 4478 1802 5162/1099 7756/1492 8252/1887 Glenn Bradford
=================
antFarm was submitted by Glenn Bradford at gmb@sarts.att.com
=================
HOW DID antFarm approach the task?  Special tricks?

  From the entrance, antFarm generally goes east and then slices up and down
  thru the building as it works its way back west and out the exit.
  
  At any given room, an evaluation function decides which direction to move
  next. The function scores higher for the directions taken which are more
  constraining (have neighboring rooms which are unenterable or have been already
  entered). This strategy helps avoid creating pockets of unvisited rooms.
  In the event of ties, east moves are favored followed by up and down moves.
  
  On floors which have at least 30% fewer empty rooms than the average empty
  rooms per floor, scores for going up and down are boosted.
  Conversely, on floors which have at least 30% more empty rooms than the
  average empty rooms per floor, scores for going east, west, north, and
  south are boosted.
  
  A chunk of time during antFarm's run is devoted to a more "aggressive go east"
  strategy. In it, the evaluation score for moving east is artificially boosted,
  while the score for moving west is artificially diminished.
  
  antFarm keeps track of how many times an attempt is made to visit a room, and
  if these attempts cross a threshold, it considers the room unenterable. 
  This is a method to shortcircuit the search in parts of a building where 
  you might be trapped. These counts are initialized when a path has 
  been backed up to a fairly short length (see below).
  
DID antFarm iterate in any way?  How did it know it was done?
  
  Depth first search, but if a better soln is not found within a time limit,
  the recursion "backs out" to a shorter part of the path and then restarts the
  search from there, hoping to find a more fruitful soln. A switch to the
  "aggressive go east" stragegy occurs after the "back out".
  
  Usually knew it was done by hitting the 600 second time limit.
  
WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?

  I do software development in Network Systems at Lucent Technologies.

=================================================================

======================================= son_of_Sot =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
son_of_Sot      20734 5962 1770 4980/1051 7630/2052 8124/2859 Bob Ashenfelter
=================
son_of_Sot was submitted by Bob Ashenfelter at ash@att.com
=================

HOW DID son_of_Sot approach the task?  Special tricks?
  
  There are four solver routines and one improver routine.  The solvers are
  called "deterministic", "random", "semi-deterministic", and "semi-random".
  Each starts at the entrance and repeatedly picks one of the available moves
  until it gets back to the entrance.  Whenever they get into a dead end (no
  available moves), they call routine "unmove()" which backs out one move and
  leaves the vacated space marked so it won't be visited again.
  
  The "deterministic" solver always picks the UP move if it is available,
  then DOWN, EAST, NORTH, SOUTH, and WEST in that order.  The "random" solver
  of course picks randomly from the available moves.  The other two solvers
  are in between, favoring UPs and DOWNs with some degree of randomness.
  
  The improver routine takes a pre-existing solution and goes through all the
  moves looking for situations where there are two unvisited spaces adjacent
  to the path that it can add to the solution.
  
DID son_of_Sot iterate in any way?  How did it know it was done?
  
  Yes.  The "deterministic" solver is called only once because it always gets
  the same solution.  But the other solvers generate different solutions each
  time they are called and so they are run over and over, hoping that they
  will stumble on ever-better solutions.  Only the best solution is saved.
  
  There are two ways that it knew it was done.  One was a time limit, set at
  590 seconds.  The other was if it had found a best-possible solution.  When
  the building was first read in, the maximum number of moves was computed by
  counting the empty spaces (plus "E") and rounding down to an even number.
  The maximum number of UP moves was computed by counting the number of empty
  spaces with an empty space one floor below and dividing by 2.  Whenever a
  solution with these maximums is found, the program takes an early exit.  I
  didn't really expect this to get used, but it turns out that the "determin-
  istic" solver gets an optimum solution for the large empty building that
  was used as a system test.  (Actually, the version Fred had at the time
  didn't have this feature--it had a very short time limit instead.)
  
  Once the time limit expires, the improver routine is called to try and
  improve the previously-best solution.  Since one pass of the improver may
  open up new opportunities for improvement, the improver is run over and
  over until there is no more improvement.  Then it prints out the solution.
  
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
  
  When this problem first came out, I thought there might be a way that it
  would be similar to the previous POTM, KNIGHTCRAWLER.  Hence the name
  "son_of_Sot", after the name of my previous entry, "Sir_Sot".  In the end,
  I never did find much of a connection, although the overall structure of
  the two programs is similar.
  
  I must confess to not having tried hard enough on this problem.  When it
  first came out, I worked on it some for a couple of weeks, then did nothing
  for two months.  Then I submitted an old program as a new entry because it
  aced the empty building.  Another month passed.  Finally, at 6 p.m. on the
  very last day, I started work on the improver routine.  This improved my
  final standing from moderately poor to moderately good, but I didn't really
  consider my final entry to be competitive.  Here are several of ideas I
  thought about, but didn't implement.
  
  Originally, I thought it would be very important to detect and block off
  all "dead ends", otherwise a lot of time would be wasted generating moves
  that would eventually have to be removed.  I never did come up with an
  algorithm for determining which spaces were "dead" and in the end I convin-
  ced myself that it really wasn't all that important.
  
  My improver is good at picking up pairs of empty spaces, but it can never
  do anything with isolated empty spaces.  I needed a routine to migrate such
  orphans together so the improver could take them.
  
  The high-level control of this program needs improvement, but I didn't take
  the time to do anything about it.  Probably I could have moved up a couple
  of notches in the standings if I had applied the tools I developed more
  intelligently.
  
  Finally, I will leave you with the design of a building so fiendishly
  devious that I didn't mention it to Fred lest he should use it since my
  program is not designed to cope with it.  Consider a large building that
  is divided into a large number (several hundred) small closed rooms.  Now
  make exactly two openings in the walls (or floors) of each room such that
  they are all strung together like beads on a necklace.  It would be fairly
  easy to generate a decent solution to this configuration.  Do so, and save
  it.  Finally, add no more than one additional opening to each room so that
  additional pairs of rooms are connected, creating short circuits in the
  string of rooms.  Consider your choices as you enter each room.  There are
  only two ways out since you have already used up the third getting in.  If
  you choose the wrong exit you will have cut off access to all the short-
  circuited rooms.  Sure, you can enter them, but sooner or later you will
  run into a dead end and have to back out.  With hundreds of binary choices
  to make, the chance of finding the one true path is astronomically small.
  And yet you already have found and stored a good solution, you just can't
  find it once all those extra options are available!
  
  One more thing...  Son_of_Sot found the most UP moves.  I want my YO-YO.

>>> POTM-MASTER NOTE:  BOB HAS BEEN AWARDED THE YO-YO ... MY ERROR!!!
  
  WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?
  
  Circuit design.
  
  Bicycling, sailing, grow orchids, travel.
  
  No way...
  
  Nothing new, but I would like to say that I enjoyed the fact that this
  problem was not too similar to the previous ones.  There have been too
  many POTMs which involved a two-dimensional square array of some kind.
  This one was three-dimensional.  Perhaps we can look forward to N
  dimensions!
  
=================================================================

======================================= Witless =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Witless         20716 3900 1154 5408/700  7152/1449 8156/1751 Alex Popiel
=================
Witless was submitted by Alex Popiel at popiel@nag.cs.colorado.edu
=================
HOW DID Witless approach the task?  Special tricks?

  Immediately after reading the board, Witless did some annoyingly
  complex graph theory (identification of bi-connected components)
  to simplify the playing field, and calculate gross maxima for
  the maximum number of steps/ups possible.  This simplified board
  and corresponding statistics were then saved.
  
  Witless then chose a direction order bias and made a simple 2-step
  path (either north or south of the entrance, depending on edge
  proximity).
  
  Next, Witless did a "ballooning" of the path: if there were two
  open spaces next to an existing edge of the path, the edge was
  replaced with three edges going through the two (now filled)
  spaces.  The order of filling was controlled by the direction
  order bias, above.
  
  Once no more ballooning could be done, Witless scanned the path
  for surrounding open spaces.  When an open space was detected,
  A depth-first search was done to find a path through that space,
  reconnecting with the existing path at some later point.  If
  such a path was found, then another round of ballooning was done,
  and the result checked against the original (before the search);
  if it was better, it was kept, otherwise the original was restored.
  This was repeated until no more improvement could be made this way.
  
  Witless then compared the path with the best path to date,
  possibly replacing the best path.  The direction order bias was
  then changed, and the board restored to the simplified state
  immediately after load; a 2 step path was generated, and the
  entire process repeated.
  
  Witless terminated when either it ran out of time (never happened
  during tests) or it finished all of the preprogrammed direction
  order biases.
  
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
  
  Several tricks I found (and find) useful:
  
  1) Avoid dynamic memory allocation as much as possible; for
     well-defined probems with maximum size, it is rarely necessary.
     Statically (or, occasionally, automatically) allocate for maximal
     size, and use as much as you need.
  
  2) Lay out your data structures for simplest use.  In the case of
     Witless, this included representing the board (partly) as an
     array of characters, with I used directly as the read buffer
     when loading the problem.  No character translations were done
     on the input, and the numbers included in the problem file
     were never parsed.
  
  3) Put borders around your data spaces, so you don't have to
     special case edge effects.  I added a 0th and an (n+1)th floor
     to the building, filled with impassible terrain.  (The impassible
     terrain happened to be nulls in the character array, so I didn't
     have to initialize it, either.)
  
  4) Make array dimensions powers of two whenever possible, even if
     this causes overallocation of memory; the speed increase from
     the simplified indexing is noticable.
  
  5) If working in a multidimensional space where directions are
     barely distinguishable, don't use a multidimensional representation.
     Instead, flatten it to one dimension, with the various directions
     transformed into different size offsets.  By referring to these
     offsets in a variable, you can make the same code work for all
     the directions, instead of just one.
  
  6) Don't grow overly attached to complex algorithms; they rarely
     work better (or even as well) as the simple ones.  (I ended up
     abandoning all work I had done after the first week of this
     contest.)  Of course, the truly simple (brute-force) solutions
     rarely work, either...
  
  7) If you think it will work, test it.  If you don't think it will
     work, test it.  If you don't think, test it.  It's amazing what
     the tests show.
  
  8) Profilers are your friends.
  
=================================================================

======================================= janitor =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
janitor         20482 3653 1843 4920/397  7386/790  8176/2466 Greg Youngdahl
=================
janitor was submitted by Greg Youngdahl at youngdahl@lucent.com
=================

HOW DID janitor approach the task?  Special tricks?

  Basically it used a bruit force approach.  One thing I did (and
  I'm sure it wasn't unique) was to add a basement, attic, and west wall of
  all '#' characters to the building so I wouldn't have to be checking all
  the time to see if I was at a boundary, I could just look for '#'s and
  let them block my path as they would anywhere.
  
DID janitor iterate in any way?  How did it know it was done?
  
  From any particular square janitor had a sequence of moves that
  it would try to make.  If a move succeeded it would try moving on from the
  new square trying moves in the same sequence.  Once it got blocked (no
  more possible moves from a given square) it would back up to the previous
  square and try the next move in the sequence for that square.
  
  I ended up using 28 different sequences of moves from any given
  location in order.  These were almost arbitrarily chosen.  I found that any
  particular sequence would generate some result (if it found a path at all)
  fairly quickly and then as it continued searching it might find a better
  result that was only a few steps better even though it searched for a long
  time (I think basically a given approach would end up blocking off a section
  of the building and would have taken a long time to get back to that area
  of the building and move into it).  I was better off to start over with
  a new move sequence after a short time of searching.  I decided to consume
  20 seconds on a given sequence and then give up on that and try another
  sequence.  Is that iteration?  Running for 20 seconds on each of 28 move
  sequences should have run for 9 minutes and 20 seconds, leaving me with
  40 seconds to spare (or I could have done a couple more sequences).  On my
  system at work (a Sparc5) I found I could check on the time every 64000
  steps and come in within about 5 seconds of that time limit.  However on
  the runs for the contest (on Fred's system) apparently the processor is
  significantly slower, and each of my runs exceeded the 10 minute limitation
  by a few seconds (I though when I got the results of my runs in the mail
  that I was going to be disqualified, but apparently I didn't violate that
  requirement enough for disqualification).
  
  For any substantial building it knew it was done when it ran out of
  time.  In theory (given enough time with a given move sequence) it would have 
  tried every possible move from every possible square and found the ultimate
  path through the building.  But of course 10 minutes was nowhere near enough
  time to do that for any but the most trivial buildings.  Given enought time
  (or a simple enough building) it would have realized that it had backed up
  to the starting square again and known it was done.
  
  
  ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
  
  Well, my office mate suggested that the people who found 0 paths for
  any of the buildings ought to be fired ;-)   Here is a program for them...
  
  main()
  {
  	printf( "ns\n" );
  }
  
  
  I'm also wondering why the VERBOSITY AWARD went to Ripple.c at only
  49710 bytes.  Janitor.CC was was 66155 bytes.
  
*** POTM-MASTER NOTE:  Don't be so proud!!!!
  
  WHAT DO YOU DO FOR:
      A LIVING?  software engineer.
      FOR FUN?   guitar player.
      INNERMOST SECRET?  uh... no comment.
      POTM IDEAS?  wait for Fred to send out contest announcements.
  
=================================================================

======================================= Round+Round =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Round+Round     20422 4415 1650 5290/1029 6908/1345 8224/2041 Daniel vanderZee
=================
Round+Round was submitted by Daniel vanderZee at zee@info.nl
=================
HOW DID Round+Round approach the task?  Special tricks?

  The program starts by generating one or more random points in the
  building and attempts to find a path through it. Once it finds a path it
  randomly deletes sections of the path, inserts new points into the path
  and attempts to find a path through these points. If a path through
  these points is found it tries to "sidestep" and "step back" wherever
  possible, i.e. path sections like ?w? are replaced by ?nws?.
  
  Round+round is just a basic genetic algorithm. It starts out with a set
  of paths, keeps only the best paths, mutilates 'm and starts over. 
  
=================================================================

======================================= rookie =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
rookie          19596 5447 1642 4156/1198 7314/1812 8126/2437 Paul Nelson

	Sorry ... no description available for rookie

=================================================================

======================================= blind =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
blind           18572 3529  915 2490/442  8008/1365 8074/1722 Carlos Valenzuela
=================
blind was submitted by Carlos Valenzuela at carlos@basic.attis.com.mx
=================
HOW DID blind approach the task?  Special tricks?> 

  It is based on two complementary methods:

  1) List all the possible next movement  sorted (ascendant) by number
     of neighbors
     then choose just the first 3
     Group this moves 8 by 8 
     Generate all possible ways of 8 movements
       Sort them avoiding isolate squares, choose just the first 2 

  2) Once that a path exist, find all couples of adjacent squares that 
     can be added to the path 

DID blind iterate in any way?  How did it know it was done?

    Once that the limit time is reached or when the building is full or 
    almost full (one square free)

WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?

  28 years, single (not for long time) Bachelors degree on Physicist 
  UNAM Mexico; I work as programmer on EPIA, here we make Software for 
  Banks in Mexico I love Science F. Movies, and walk on the wood

About POTM contest

  I Found very stimulant to see the tables of results from several
  different test-problems

  What about let the participant run his own test on the POTM-machine,
  that way the portability problems and others related could be fixed
  and worked out more easily

  Fred, thanks for your assistance and friendly help. I really enjoy this
  contest.  Please feel free to change the style or the grammar of 
  this message.  (Please do).

=================================================================

======================================= Minos =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Minos           18242 3718 1758 3130/709  7068/1278 8044/1731 Didier Barzin

	Sorry ... no description available for Minos

=================================================================

======================================= strider =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
strider         15766 5823    0 2844/1105 5974/1944 6948/2774 George VanAusdall
=================
strider was submitted by George Van Ausdall at gva@bob.lc.lucent.com
=================
WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?

  Answering the personal questions first, I'm a programmer working for
  Lucent Technologies.  Previously, I worked for Western Electric, AT&T
  Technologies, AT&T Network Systems, AT&T Corporate Headquarters, and
  Bell Labs, even though I only changed my work location one time and
  changed departments only twice!  I enjoy bowling, playing bridge, and
  solving programming problems.
  Now, on to the interesting subject:

HOW DID strider approach the task?  Special tricks?

  Strider (named after the character in J.R.R. Tolkien's Lord of the Rings)
  was written in just a few hours over the course of the last two days of
  the contest, so it's not very sophisticated.  In fact, this description
  is longer than the source code!
  
  The representation of the building in strider is the obvious one: a
  three-dimensional array.  There's also a one-dimensional array for
  storing the sequence of moves.  The maximum size of the building
  specified in the problem description makes this practical.  There's no
  dynamic memory allocation in strider.
  
  The only analysis of the building that it does is these two simple things:
  1. It determines the true number of columns in the building.  I.e., it
     checks how many columns on the right are completely filled with #s
     (the rightmost one should always be so).  A better test would be how
     many columns are inaccessible; but that's a lot harder!
  2. It counts how many of the three locations directly east of the E and
     directly east of the two spaces above and below the E have #s.  If two
     or more of these locations have #s, the only possible solutions are
     the two trivial solutions "ns" and "sn".
  
  If analysis #2 does not show that a trivial solution is necessary,
  strider starts by moving north if the location directly east of the
  space above the E contains a space.  It then moves east.  Then, it
  enters a loop that tries to move up as far as it can, tries to move down
  as far as it can, and then picks a horizontal direction to move one
  step.  If it can't move in any horizontal direction, it backs up one
  move and tries again.  If it succeeded in moving up or down before
  unsuccessfully looking for a horizontal direction, it will back up (or
  down) one floor.  Whenever strider backs up, it marks the location that
  it backed up from, so it will never try to move there again.  (This is
  to guarantee that strider will terminate.)  The main loop exits when no
  horizontal move is possible and it's not possible to back up anymore (in
  which case it outputs the trivial solution "ns") or when it moves back
  into column 0.  In the latter case, it then moves north or south one
  step, if necessary, to get to the E.
  
  The code for the horizontal moves tries to move in the general directions
  indicated by the following diagrams (please excuse the crude ASCII art --
  I'm not an artist), which show strider's movements in two empty one-floor
  buildings; one with an even number of columns, and one with an odd number
  of columns (hence analysis #1 above).  The idea is to go north and then
  go east across the north side of the building.  Then, it goes alternately
  south and north along the columns, gradually heading back to the west.
  By wandering the building from east to west, the area around the E is
  left unvisited until the end, maximizing strider's ability to make its
  way back to the E without having to back up a lot.
  
  	  ---->---->-----+		    ---->---->---->---+
  	  E              |		    E                 |
  	  -<-+   +-<-+   v		    -<-+   +-<-+  +-<-+
  	     |   |   |   |		       |   |   |  |
  	     ^   |   ^   |		       ^   |   ^  +->-+
  	     |   v   |   v		       |   v   |      |
  	     |   |   |   |		       |   |   |  +-<-+
  	     ^   |   ^   |		       ^   |   ^  |
  	     |   v   |   v		       |   v   |  +->-+
  	     |   |   |   |		       |   |   |      |
  	     +-<-+   +-<-+		       +-<-+   +--<---+
  
  This simple strategy works well in empty buildings of any size, but it
  tends to leave large areas unvisited in complex buildings.  If I'd
  allowed three days to write strider instead of just two, I'd have added
  one more thing:  After completing the path, look for unvisited locations
  that are adjacent to visited locations and start a new path through the
  unvisited locations.  If the new path intersects the old path such that
  the new path is longer than the bypassed part of the old path, splice in
  the new path.  (If the new path comes back to the old path in more than
  one place, it should pick the place that's closest to where it started
  the new path.)  This can be repeated until there are no more unvisited
  locations adjacent to visited locations.
  
  Finally, strider outputs its sequence of moves.
  
=================================================================

======================================= boom =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
boom            15724 5783    2 3000/1157 6062/1997 6662/2629 R.Ang I.Soehardjo

	Sorry ... no description available for boom

=================================================================

======================================= Protein =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Protein         15254 2605 1710 6/0       7180/1379 8068/1226 Kroum Savadjiev
=================
Protein was submitted by Kroum Savadjiev at kroum@consulan.com
=================
  First, i would like to congratulate all my competitors - participants of
  the POTM for the work done to solving the problem, and, of course, the 
  POTM Master for the overall organisation, which was very good!
  
HOW DID Protein approach the task?  Special tricks?
  
  I changed my strategy at almost every new version of Protein. First, my 
  approach was to take a valid path ( "sn" is always a valid path ), and then
  to "swell" him to the maximum level. For exemple, "sn" can be "swelled" to
  "senw", if possible. Unfortunately, this version was not very good, because 
  at the end there was too many unused places. Also, this version did not pass
  the second system test - the big empty building, it was very slow. I managed 
  to accelerate the program, but the speed was still insufficient. Then i added
  a preliminary function before the swelling, which was very fast, but not very
  efficient in terms of "filling" the building. This function's output was a 
  relatively long path for almost no time, and it was used like "seed" to the
  subsequent swelling. The big empty building was filled entirely, but in the
  others buildings there still was too many empty places... My last version 
  uses 3 stages: first, a very quick filling of the building, then a "swelling"
  of this preliminary path, and, at the end, a "slow" function which tries 
  to fill all the remaining places using an exhaustive iteration for all the
  time remaining (the first 2 stages usually took 3-4 seconds), in hope that the
  building will be filled in the most efficient way. I think that Protein
  behaves not very bad... I have some ideas to improve it, but unfortunately 
  i won't have the time until the end of this POTM.
  
DID Protein iterate in any way?  How did it know it was done?
  
  After the first two stages, Protein tries to iterate through all possible 
  remaining moves, in order to fill all the empty rooms. This is, of course,
  impossible on a "real-life" building, but , fortunately, in the first 2 stages
  almost 90% of the work was done in a very short time. Nevertheless, i still
  cannot pass through all remaining moves, but for 570 seconds the path is 
  lengthen with some moves. I know that the exhaustive search cannot be the so-
  lution, unfortunately, when i realised that the first 2 stages was not enough
  for a good result, there was not much time left to imagine a better solution.
  
  My second stage, the "swelling", also uses iteration, in a sense. 1st it was 
  a recursive function, but for performance reasons, i changed the recursivity 
  with an ordinary loop. But i think the question is not about this
  kind of iteration.
  
  At the end, the third stage does not know that the task is done, because the
  task is almost never done 100%. It just uses all the remaining time...
  
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
  
  I have just a comment: the POTM-Master was absolutely right saying that
  entering soon is paying. This, among other things, gives the opportunity to
  compare our program with the competitors, and to take measures to improve
  the necessary.
  
WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?
  
  I live and work in Montreal, a beautyfull city. I work as a programmer, and
  programming is also my "hobby".
  
  At the end, i would like to wish everybody (and myself) better results at 
  the next POTM!
  
  
=================================================================

======================================= sagan =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
sagan           15022 2520   24 6/0       6898/1070 8118/1450 Douglas Zongker
=================
sagan was submitted by Douglas Zongker at zongker@cps.msu.edu
=================
HOW DID sagan approach the task?  Special tricks?

  sagan first determines which squares on the map will never be part of
  any legal path and fills them in with walls (eliminating blind alleys,
  etc.).  It then represents the remaining rooms as nodes of a graph,
  with edges connecting adjacent rooms.  The graph is collapsed to
  remove all nodes of degree 2 (so that, for instance, a long hallway
  will be represented as just one edge in the graph).
  
  To generate a path, it starts with a trivial seed path "ns" or "sn",
  or "ud" or "ew" if those are legal, and tries, by exhaustive search,
  to replace every subpath with a longer subpath connecting the same
  rooms.  It tries once for each seed path, and then outputs the longest
  path generated.
  
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
  
  This is my first POTM -- I could use some myself...
  
WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?
  
  I'm starting as a CS grad student at the University of Washington.
  
=================================================================

======================================= Wandering_Plane =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Wandering_Plane 14950 2420    0 6/0       6880/1088 8064/1332 Raj Singh

	Sorry ... no description available for Wandering_Plane

=================================================================

======================================= Save_The_Worm =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Save_The_Worm   14908 3822   34 6/0       6830/1447 8072/2375 Vance Heron
=================
Save_The_Worm was submitted by Vance Heron at vance.heron@jpl.nasa.gov
=================
HOW DID Save_The_Worm approach the task?  Special tricks?

  Started with the simplest "legal path" - either ns or sn, then
  extended it by two moves each time e.g. nusd or nesw.  I repeatedly run 
  through the entire path checking for available 2 move extensions.
  
  Tricks:  
     Created a "bottom" and "top" floor all #, simplifying checking
     for legal moves.
  
     Built the output string 2 characters at a time - and saved the
     "best" output string for a single print.
   
DID Save_The_Worm iterate in any way?  How did it know it was done?
  
  I found I could do an entire "run" very fast and ended up doing several
  runs, trying different starting moves and orders of extensions.  After 
  N tries (currently N=12) I print the best result.
   
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

  Tried an approach similar to the 8 queens problem, where I made
  moves until I either got to the end, or got stuck.  Then I backed up 
  and tried different choice from a given position.  Took way to long, and 
  ended up repeating backtracks - I still think this approach has potential.
  
  I'm not very happy with my current approach, but couldn't come up with
  a better one with the limited time I had.  An approach I haven't quite
  worked out would be to determine all possible vertical moves, then find ways 
  to connect them at the various levels ?!?.  
  
  Lost a lot of sleep trying to think of a better approach ;-/
  
WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?

  Living - System Engineer, designing and testing systems to capture 
  process and distribute SAR data obtained from earth-observing satellites.

  Fun - Play with my 2 young children, and sing in a barbershop quartet.
  I also enjoy hiking, camping, cooking and reading.  Recently added POTM :)

  Innermost Secret - you've got to be kidding. I will say that "save the 
  worm" is a joke refering to the previous JPL/NASA logo, which used a 
  worm like font, recently replaced with the old NASA logo used during 
  the 60s, commonly called "the meatball".
  
  POTM Ideas - I like the idea of a program that "plays" against another (I 
  believe you've done that at least once before).  
  Given a sequence of numbers, guess the next one (e.g. 1 11 21 1211 111221 ..)
  Mastermind type games (guess a sequence of digits, given hints at each move)
  
=================================================================

======================================= Plima =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Plima           14868 2401    0 6/0       6904/1215 7958/1186 Zeljko Zahtila
=================
Plima was submitted by Zeljko Zahtila at zzahtila@vitgdts1.telecom.com.au
=================
HOW DID Plima approach the task?  Special tricks?

  The idea behind Plima (high tide) is simple: start from the shortest path 
  (e.g. ns) and try to expend one path segment at a time, i.e. s would be 
  replaced by wse, and the path would become nwse; then w would be replaced 
  by nws, and the path would now be nnwsse.
  This strategy works well when there are no forbidden rooms. I spent a 
  lot of time developing an algorithm to go around forbidden rooms that 
  worked very well in 2 dimensions but didn't find a way (and time) 
  to port it to 3 dimensions.
  
DID Plima iterate in any way?  How did it know it was done?

  Plima keeps expending a segment until possible, than it moves to the next 
  segment.  The algorithm is so simple (and quick) that it didn't have 
  to check for time limits.
  
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
  
  If I had to do it again I would apply knowledge about graphs that I 
  subsequently acquired from Sedgewick: Algorithms in C++.  Reading 
  of this book was inspired by this problem.
  
WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?
  
  For living: computer consultant.
  For fun: bringing up two sons (Tony 3.5, Mate 1.5). Not much time left for 
  anything else.  Time spent on POTM was stolen from my sleep.
  Secrets: let them keep this status.
  POTM ideas: None at the moment, if something comes to mind I will let you 
  know. Keep the good work going.
   
=================================================================

======================================= zigzag =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
zigzag          14718 2143    0 6/0       6776/989  7936/1154 Mark Kuczynski

	Sorry ... no description available for zigzag

=================================================================

======================================= proto1 =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
proto1          14478 2399 1796 6/0       6584/1119 7888/1280 P.Frants S.Pieterse
=================
proto1 was submitted by P.Frants and S.Pieterse at pfrants@cs.vu.nl
=================
HOW DID proto1 approach the task?  Special tricks?

  Unfortunately we could not spend as much time as we wanted on this POTM, but
  here we go. The only thing we did was to create the shortest path first and
  then we improved that path by adding two steps anywhere possible until the
  path did not improve anymore.
  
DID proto1 iterate in any way?  How did it know it was done?

  The above algorithm was repeated until time was up.
  
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

  We have implemented functions for identifying so-called 'rooms' and our
  plan was to connect as many of these as possible before applying the
  improvement algorithm above. That Damn Time...
  
WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?

  Studying and having fun. Athletics, rc-flying, potm etc. None at the moment,
  but when we think of one we'll mail Fred.
  Thank you once again Fred, and all the other competitors!
  
=================================================================

======================================= Where_to? =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Where_to?       13224 1440 1280 5504/634  7718/806  2/0       Markus Sabadello

	Sorry ... no description available for Where_to?

=================================================================

======================================= pastaiga =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
pastaiga        12866 2335  260 5304/1081 7562/1254 0/0       K.Boitmanis A.Zogla
=================
pastaiga was submitted by K.Boitmanis and A.Zogla at
		acad.latnet.lv!ugale@kcig2.att.att.com
=================
HOW DID pastaiga approach the task?  Special tricks?

  Reading data and initializing: walls and other #'s was stored as some big
  numbers(20000), reminder of building's main array - 0s;
  initial path was marked as (-1;-2) (entry as -1); iterating started at -1
  with numbering of elements of array 1,2,... which means distance from path
  (if element's number is 5, distance to path is 5 steps). If any number meets
  path (negative numbers), length of possible addition to existing path is
  evaluated and if this is more than distance from current start position of
  numbering to meeting position, path is prolonged by renumerating
  (negatives). No searching for path elements through big array, there is
  temporary array for storing of path elements and searching is performed only
  in surrounding elements of path in building (n,s,e,w,u,d). After renumbering
  of path elements numbering of array continues with last used path element
  for previous numbering. After reaching entry element, all goes round again
  until no additions had made during one cycle.

  Built in time control. If time is under halfway (300 secs), attempt to find
  better solution is performed (another initial path (-1;-2)). Temporary array
  for storing path (chars).

ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

  Just remember, correct solution for any task is short and simple.
  Pastaiga means walking. Main trick.  ;-)

WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?

  For POTM as it is any idea, where problem has no one and only correct
  solution, is OK, like recognition of something from images(text,
  fingerprints, etc.), packing and unpacking, etc.

=================================================================

======================================= Red29erDevils =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Red29erDevils    8714 3434 1969 2798/1078 0/0       5916/2356 Nils Magnus
=================
Red29erDevils was submitted by Nils Magnus at shocc@unix-ag.uni-kl.de
=================
HOW DID Red29erDevils approach the task?  Special tricks?

         We first look for an arbitrary path through the store and
         afterwards we try to enhance this path.
  
  ** Find a path:
  To find any path, we develop a depth-first-search from two starting
  points. Branches are cut if we touch the other tree or if we have no
  other way left to go. We select from the resulting intersection points
  the one imposing the longest path.
  
  ** Enhance a path:
  Given a path, we try to find from each path element to find a path to
  another possible path element. If we find such a new path and it is
  longer than the old connection, they're swapped.
  
DID Red29erDevils iterate in any way?  How did it know it was done?
  
  We iterated over our path. One can think of running with an air-empty
  bicyle-tyre trough the building from entry to exit and pumping air
  into it afterwards. Shouldn't we be able to pump any more air into the
  tyre (the path), we're finished.
  
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
  
  A great one. I'm still not sure if this problem is really
  NP-complete. I assume it is, but allowing only little differences
  compared to the optimal solution this problem should be solvable in
  rather short time. But reality is different... :-\ I learned C++ is
  nice to code (for some respect), but rather clumsy in execution.
  
WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?
  
  Distracting the focus from the dark side of life, e. g. physics exams
  and similar stuff. I guess I should become programming contestant
  pro. Thinking about solutions we discussed cellular (sp?) automats
  (e. g. life) acting as independent solvers of bigger problems... Just
  an idea...
  
  ///Nils, who was supported by Peter and Tun
  
=================================================================

======================================= DownAndOut =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
DownAndOut       8394  849  742 464/92    0/0       7930/757  Jim Eadie
=================
DownAndOut was submitted by Jim Eadie at jim_eadie@cc.chiron.com 
=================
  It was apparent from the start that a recursive approach was needed in 
  order to search for a MAXIMUM path as opposed to just a path. 
  However that would have needed a pretty large stack. So an iterative 
  approach ( tail - recursion) was used and the first path found was used. 
  
  Another restriction, the 25K source code limit, also influenced my 
  approach. I could not develop much code to evaluate and prune any paths 
  found.
  
  I pretty much experimented with searching in the directions n,e,s,w,u,d and 
  permutations of that set. Some arrangements were quickly discarded as they 
  invariable generated short paths. 
  
  Before the actual search begins I scanned the maze to identify those 
  squares which could not possibly be in the path as they only have on entry 
  point. I figured this would help in reducing the backtracking effort out of 
  dead ends.
  
  I identified the task as being over by just testing the resulting move 
  against the known entry square.
  
  It very quickly became apparent that many squares were being left 
  un-wandered and also that they could have been included in the path. I 
  spent a fair bit of time looking for a way to incorporate these squares 
  AFTER a path had been found. I developed a "splice" function. It looked for 
  at least 2 adjacent empty squares ( ie nn, ss, uu, etc) which might be 
  reached from a nearby by pair of squares on the path. I then looked to see 
  if a deviation could be made from the found path to incorporate these empty 
  squares. For example on a path of ...nn..., next to 2 empty squares on the 
  east side, one could turn this into ...enwn... This splice was repeated 
  until no further possibilities existed.
       
  The final approach to the problem came when the empty maze became the test 
  system. Unfortunately all the above did not help in solving the problem in 
  the allowed time limit!!! In a fit of lazyness I just modified the program 
  to only scan the lowest floor, and then let the slice fill in the rest.

=================================================================

======================================= Marketroid =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Marketroid       8068 1290  895 6/0       0/0       8062/1290 Steven Burnap
=================
Marketroid was submitted by Steven Burnap at sburnap@wsgc.com
=================
HOW DID Marketroid approach the task?  Special tricks?

  Not as well as I'd have liked :-)
  
  Basically there are two phases.  First, it examines the input and 
  replaces any unreachable spaces with a '#'.  Unreachable spaces are those 
  either surrounded by '#'s or adjacent to only one '#' (dead ends).  It makes
  multiple passes until no more such spaces are found.  Then it does a more 
  in-depth analysis to find large areas with only one entrance.  All spaces 
  in these are also filled with '#'s.  This makes the second phase easier 
  as the program doesn't have to worry about dead ends.
  
  In the second phase, it creates a minimum path ("ns" or "sn") and then 
  tries to expand on that path until either it cannot or it runs out of 
  time.  The first part of this is to search the path for two adjacent 
  used spaces that are next to two adjacent unused spaces.  This is then 
  expanded from a two-square path to a four square path.   It stops this 
  when it can no longer find any such spaces.  At this point Marketroid 
  usually has a pretty good path and has used less then five seconds of 
  time.  It then starts scanning for subpaths that seem to be adjacent to 
  many unused spaces.  It then clips the subpath out and tries to find and 
  better path (recursively).  It does this until it runs out of time.

DID Marketroid iterate in any way?  How did it know it was done?

  Yes.  All of the steps are short and guarantee a valid path that is at 
  least no worse then when the step started.  It is then done when it runs 
  out of time.  (To be on the safe side, it starts cleaning up and printing 
  output when there are 30 seconds left.

ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

  This solution seems to work pretty well for getting a decent path 
  quickly, but for getting the best solution I think a whole other approach 
  is needed.  The second part of the expansion phase would only add ten or 
  so spaces to the path on buildings the size of the test building.

WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?

  I'm a computer programmer working on OS/2, AIX and Z80 Point of Sale 
  software (mostly in C, some in C++) for Williams-Sonoma.

=================================================================

======================================= Run_A_Muck =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Run_A_Muck       5268  574 1953 5268/574  0/0       0/0       Jim Wright
=================
Run_A_Muck was submitted by Jim Wright atjwright@seattleu.edu
=================
HOW DID Run_A_Muck approach the task?  Special tricks?

  Run a muck started out as a Brute Force Algorithm.  It did not 
  score very high on the first test, so I decided to find a better algorithm.
  I looked at what most people used for the TSP, and that was Linear 
  Algebra.  I found that the simplex method gave me the Maximum moves 
  through the building, but it also gave me too many small paths and 
  loops to contend with.  So I looked at the Stepping Stone Algorithm 
  from Operations Research.  This is the algorithm that worked the best, 
  however it took too long to solve the bigger buildings.  I then took 
  the Brute force algorithm and graphed it on to the Stepping Stone,  
  if the building is big then Run A Muck will use brute force, 
  smaller buildings use the Stepping Stone.
  
  Both of these algorithms take too long so they find as many paths it 
  can in Ten minutes and then prints the largest one.  The stepping 
  Stone may not hit the most ups it can, but the Brute force algorithm 
  tries going up first then down second ensuring that the first long 
  path it finds has the most ups.
  
WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?

  By the way, I'm Jim Wright, I work for the Boeing Company, as well as 
  getting my Masters in Software Engineering.
  
  My idea for a POTM is to build a Adventure Game Solver.  This would 
  require building an Adventure Game in C and then having an interface 
  where you send a string of commands into the C game and then receives
  a string of what the game did back to the entry.  It will do this 
  until a 'You have solved this game' message appears.

=================================================================

======================================= YAIA =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
YAIA             5266  998 1312 5262/998  2/0       2/0       Emery Lapinski
=================
YAIA was submitted by Emery Lapinski at ewl@panix.com
=================
HOW DID YAIA approach the task?  Special tricks?

  I never felt like I got a very good mental handle on how to deal with
  this problem.  (I still can't think of a way to brute force a solution.)
  After a few false starts and frequent redesigns I
  came up with what seemed to give me a fairly decent path through the
  buildings I tested without being too easily fooled.  From a given location
  YAIA moves to an available location that:  a) is furthest away from the
  exit and b) still allows YAIA to reach the exit.  Based on rather specious 
  heuristics it is easily fooled so I find paths for each possible move off 
  the entrance space, time permitting.
  
  I planned on taking the initial guess and tweaking it to find better paths.
  I never thought of a good way to do it.  (Like I said, I could never get a 
  good mental model of what I wanted YAIA to do.)
  
DID YAIA iterate in any way?  How did it know it was done?
  
  No real iteration.  Each step taken was followed by a series of calculations,
  but steps were never untaken.  YAIA knew it was done when it had found
  a path for each possible move off the entrance space.
  
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
  
  YAIA does not stand for "Yet Another" anything, but instead is an abbreviation
  for an old joke about a sign hanging above a urinal in a mens' room.  Are
  you sure you want to hear it?  OK.  It's not funny.  "Our aim is to 
  keep this bathroom clean.  Your aim is appreciated."  It seemed appropriate.
  
WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?
  
  I earn money as a computer programmer designing GUIs and implementing
  them in Java (until quite recently it was Galaxy/C++).  For fun I like
  to go to the gym, go SCUBA diving, play with my computer and revising
  my WWW pages.  My secrets are hidden away even from myself.
  
=================================================================

======================================= SeeMyThumb =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
SeeMyThumb       4820 1161   44 4816/1161 2/0       2/0       Brace Stout

	Sorry ... no description available for SeeMyThumb

=================================================================

======================================= CheeseHead =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
CheeseHead       3856  886 1777 1694/386  2162/500  0/0       Mike Buchmann
=================
CheeseHead was submitted by Mike Buchmann at mikeb@cray.com
=================
HOW DID CheeseHead approach the task?  Special tricks?

  For each move I computed the number of steps each block was away from
  the exit position.  To do this, I simply looked at each adjacent block
  and added one to the lowest value, starting with the exit block having
  a value of one.  Since we are really only interested in the blocks
  adjacent to the current location, I have added a check so once these
  blocks have been assigned a value to continue.  The move is then to the
  square furthest away from the exit (highest value), unless time is running
  out (< 1 min) then the program heads for the exit.  I also ran the program
  (time permitting) through three times for the three possible first moves.

ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

  The secret is to find your moves quickly, I have yet to perfect this.
  Just a little note, you can get a lot more moves out in ten minutes when
  you run your code on a Cray super-computer!  If you would like to order
  one, just send me a note ($30 million should get you a really nice one).

WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?

  I am a computer programmer for Cray Research (now an SGI company) working
  in the design automation department.  My work has mainly been with printed
  circuit board design.

  I would like to thank Fred for organizing and running this event.  It really
  has been fun to work on and to compete.  One small suggestion I have is to
  place the supporting programs (timing code, maze generation...) on the
  POTM web site.

  I will be posting my entry on the internet after September 1st at
  http://home.cray.com/~mikeb/potm (I am assuming that mine will not be the
  winning entry).  I would like to see others solutions.  If you would like
  to share your solution with me, send it to mikeb@cray.com.


=================================================================

======================================= LostSoul =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
LostSoul          372   64 1785 6/0       110/11    256/53    Byon Garrabrant
=================
LostSoul was submitted by Byon Garrabrant at byon@netcom.com 
=================
HOW DID LostSoul approach the task?  Special tricks?

  The plan was to start with an empty path, choose a random direction 
  and two random points in the path, and add the direction at the first 
  point and the opposite direction at the other point and test for 
  success.  If it fails, try another random set, else make that the new 
  path and start over.  Sometimes it tries several additions before 
  checking for a valid add.
  
DID LostSoul iterate in any way?  How did it know it was done?
    
  It just kept adding steps until it could add no more (many attempts 
  without growth), then it compared that path to the best, saved it if 
  better and started over with an empty path.
  
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
  
  It was a lot of fun to write, but the timing was tricky to solve on 
  the test platform since I used a different platform
  
WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?
  
  Computer Game Programmer for Virgin Interactive for money and fun.
  Amatuer Radio (KD6BCH) just for fun.
  Keep up the good work on the PTOM!

=================================================================

======================================= ROGUE =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
ROGUE              82    6  469 6/0       0/0       76/6      Michael Strauch

	Sorry ... no description available for ROGUE

=================================================================

======================================= XaaShuffle =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
XaaShuffle         28    0  603 18/0      4/0       6/0       Mark Huizer
=================
XaaShuffle was submitted by Mark Huizer at xaa@stack.urc.tue.nl
=================

  Hey... forget it :-) I couldn't find the time to do anything on it :-(

=================================================================

======================================= Maze_Master =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Maze_Master         6    0    0 2/0       2/0       2/0       Ertugrul Tabak

	Sorry ... no description available for Maze_Master

=================================================================

======================================= RoamAndRamble =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
RoamAndRamble       6    0    0 2/0       2/0       2/0       Russ Cox
=================
RoamAndRamble was submitted by Russ Cox at rsc@research.att.com
=================
HOW DID RoamAndRamble approach the task?  Special tricks?

  Basically, it used recursive descent to try all paths, with some
  optimizations.  It checked every few steps to see what was isolated
  and what was not.  If it counted and found that there were not
  enough unisolated squares to find a better path than before,
  it bailed out.  That was about it.  It opted for up and down
  before any other moves so that I had the tiebreaker thing all
  set.  Early on, I was 11th but second in up/downs.  Unfortunately,
  recursion wasted a lot of stack space and the program dumped core
  on Fred's machine.  So I wrote a printf statement and mailed it
  in, and never bothered to fix it.  So that's the secret to my
  speed (and low score).
  
DID RoamAndRamble iterate in any way?  How did it know it was done?

  The operating system told it so.  It sent SIGsomething and dumped 
  core.  Actually, the current version is just a printf, so there
  was no loop.  In the real program (which runs only on real 
  machines :) it recurses until it notices that time ran out.
  
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

  Not really.  Don't use recursion.  Write your own stack.
  Spend more time on it than I did.
  
WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?

  I don't do anything for a living, really.  I go to school at
  Delbarton School (high school senior) in Morristown.  For
  fun I do crazy things like this programming contest.  I don't
  have any ideas for POTM or an innermost secret.
  
=================================================================

======================================= Swifter_Drifter =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Swifter_Drifter     6    0    0 2/0       2/0       2/0       Scott Everett

	Sorry ... no description available for Swifter_Drifter

=================================================================

======================================= CARAMBA =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
CARAMBA             6    0  666 6/0       0/0       0/0       Ralph Meira

=================
CARAMBA was submitted by Ralph Meira at ralph.meira@sophia.attgis.com
=================
HOW DID CARAMBA approach the task?  Special tricks?

  Iteration based on a algorithm that usually works well for the
  "chess knight's walk" problem. I just introduced an extra function 
  that wouldn't allow a move into a position that could not be traced 
  back towards the entrance.

DID CARAMBA iterate in any way?  How did it know it was done?

   My biggest problem ! Because I iterated, every time the program arrived at
   a better solution I would store and continue. Close to the time_limit 
   I would break-off to the end and print out the best solution.

ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

   Don't underestimate large empty buildings !

WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?

      ;-)



=================================================================

======================================= vasco_da_nada =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
vasco_da_nada       6    0 1365 2/0       2/0       2/0       Salman Nawaz
=================
vasco_da_nada was submitted by Salman Nawaz at sal@coltrane.cb.lucent.com
=================
HOW DID vasco_da_nada approach the task?  Special tricks?

  No special tricks, in my opinion.  I guessed from the beginning that it
  would not be possible to try all possible paths in ten minutes.  I took a
  pseudo-random approach where I start at the entrance, find all initial
  moves, and then for each possible initial move, make moves according to
  a heuristic of "udnesw"; i.e., ups are most preferred, followed by downs,
  followed by norths, etc.  I make legal moves using the heuristic until
  either I find myself back at the entrance or I hit a dead end.  If I find
  myself back at the entrance, I stop and start over with the next initial valid
  move.  If I hit a dead end, I take moves back until I'm no longer at a dead
  end or I find that I can't get any solution with the current path.
  
  The final version is as just described, but attempts the initial valid move
  paths for a total of three different heuristics ("deunsw", "udnesw", and
  "nduesw").
  
DID vasco_da_nada iterate in any way?  How did it know it was done?
  
  Iteration was simply as described above.  Again, vasco_da_nada knew it was
  done only by happenstance:  either it just found itself back at the entrance
  and knew it had to stop, or it found itself at a dead end and found that it
  would have to take back all of its moves to avoid the dead end (a zero-length
  "solution"), and would just give up and go to the next attempt.  The total
  number of "attempts" in this sense is the number of heuristics (three) times
  the number of initial legal moves (two or three, depending on the input).
  
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
  
  It was a wonderful exercise.  I've been coding in C regularly for about ten
  years, and I still found myself needing to revisit my "C Traps and Pitfalls"
  book.
  
  I initially was dynamically allocating all large data structures with
  malloc().  Changing to static allocation more than halved execution time in
  most cases I tested.
  
  Unfortunately, it didn't magically cause vasco_da_nada to find the optimum
  solution.
  
  I was amazed that in one case, for a simple three-story building with five 
  rows and ten columns, one initial path took 65 moves to find a solution, 
  another path took about 150,000 moves to find a solution, and the third 
  path ran for an entire weekend and I had to kill it.  
  Just goes to show you how many possible combinations there are when 
  you try to iterate in a solution space of, oh, somewhere around seven 
  to the eightieth power? (and that's for the smallest possible building...)
  
  WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?
  
  For a living:
    I work in (Lucent Technologies!) Bell Laboratories' BCS (Business
    Communications Systems) business unit, and particularly in Multimedia
    Messaging and Response (voice mail and voice response systems, for example)
    as a software/systems-engineer/next-to-last-line-of-technical-support
    person.  We affectionately call it Current Engineering for Intuity AUDIX.
  For fun:
    Budding guitar player with a little previous piano instruction, very very
    amateur poet/songwriter/singer.  It's okay, at least I can amuse myself.
    I also enjoy playing pool and engaging in heated conversations about
    history, politics and society (often at the same time!).
    Also, weeding my yard (freaky, huh?).
  Innermost secret:
    Reduced my TV consumption to less than five hours a week in 1982.  Reduced
    it further to approximately zero in June of this year.  Shhh, don't tell
    anybody; they'll find out how much of a freak I really am.  And no, I
    didn't toss it off a building or smash it with a sledgehammer; it's in a
    dark corner of my basement attached to a VCR so I can rent a movie one of
    these days.
  
=================================================================

======================================= Crazy_Scheme =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Crazy_Scheme        6    0 2004 6/0       0/0       0/0       Mike Mossey
=================
Crazy_Scheme was submitted by Mike Mossey at dgr.jpl.nasa.gov!mossey@att.com
=================
HOW DID Crazy_Scheme approach the task?  Special tricks?
  
  I call it "inflating."  It starts with the path 'ns', a known complete
  path (let's call a complete path, starting and ending at the door, a
  "loop").  Then it looks for two consecutive squares on the path A and
  B that have empty space next to them.  It tries to make a new path
  segment that starts at A and ends at B.  If it finds one, then it has
  extended the loop...the new loop is guaranteed to be a loop and
  guaranteed to contain all the original squares on the loop and all the
  new squares.
  
DID Crazy_Scheme iterate in any way?  How did it know it was done?  
  
  It tried to apply the inflating process over and over until it
  couldn't find a place to apply it.
  
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
  
  One of the nice things about Scheme (a Lisp variant) is the garbage
  collection.  This let me construct functions that had no side effects
  and still operate efficiently.  Let me explain:
  
  All my functions that operate on the structures that represent the
  building, the path, etc. have no side effects.  Eg, the function that
  inflates the path takes a building/path structure as an argument and
  returns an entirely new building/path structure (well effectively
  new...more in a bit).  The old building/path structure still exists in
  case I need it for backtracking or something like that, and in general
  the lack of side effects makes the expressions I use simpler and more
  easily understood.
  
  "But darn these buildings take a lot of memory, and the new path might
  only represent a small change.  You mean you copy the entire building
  into the new structure even when most of it is the same?  Isn't that
  inefficient?"
  
  Actually I don't have to copy much at all.  Scheme (and Lisp) data
  structures are often trees with pointers linking the parent nodes to
  child nodes.  I can copy the parts of the tree that I don't need to
  change by copying the pointers of high-level nodes, and not many are
  required to get most of the tree.  So the old data and new data ~share
  structure~.
  
  "But when you go to free data, you can't free any parts shared with
  other data structures.  Isn't that a great deal of complexity?"
  
  I never explicitly free data...the garbage collector does it for me,
  and does an efficient job of it too.  It knows when parts of the tree
  have been forgotten about, and quietly frees them so that they may
  become reincarnated as new useful data, begin the Great Cycle again,
  and move a step closer to nirvana.
  
WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?
  
  For a living I program computers at Nasa's Jet Propulsion Laboratory.
  For fun I compose music following the tradition of what is commonly
  called "classical music."  My innermost secret is the weight of my
  liver in grams accurate to 4 places---and I'm not talking.  As far as
  POTM ideas, the ones I've seem so far are pretty darn good.
  
=================================================================

======================================= AmazingStories =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
AmazingStories      4    0  671 0/0       2/0       2/0       Ruud deJong

	Sorry ... no description available for AmazingStories

=================================================================

======================================= WalkAbout =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
WalkAbout           4    0  932 0/0       2/0       2/0       Charles Roberson

	Sorry ... no description available for WalkAbout

=================================================================

======================================= CrazyWalk =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
CrazyWalk           0    0    0 0/0       0/0       0/0       Wim Decroix

	Sorry ... no description available for CrazyWalk

=================================================================

======================================= Ramblin_Man =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Ramblin_Man         0    0    0 0/0       0/0       0/0       Vince Wolodkin

	Sorry ... no description available for Ramblin_Man

=================================================================

======================================= TheExtraStep =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
TheExtraStep        0    0    0 0/0       0/0       0/0       Jeffrey Pogodzinski

	Sorry ... no description available for TheExtraStep

=================================================================

======================================= Wanderer =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Wanderer            0    0    0 0/0       0/0       0/0       John Hitchcock

	Sorry ... no description available for Wanderer

=================================================================

======================================= dalmation =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
dalmation           0    0    0 0/0       0/0       0/0       Ken Weinert

	Sorry ... no description available for dalmation

=================================================================

======================================= delver =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
delver              0    0    0 0/0       0/0       0/0       David Wells

	Sorry ... no description available for delver

=================================================================

======================================= ImLost =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
ImLost              0    0  774 0/0       0/0       0/0       Michael Goldshteyn

	Sorry ... no description available for ImLost

=================================================================

======================================= legume =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
legume              0    0 1324 0/0       0/0       0/0       Mark Schnitzius

	Sorry ... no description available for legume

=================================================================

======================================= LuckyBlindDrunk =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
LuckyBlindDrunk     0    0 1980 0/0       0/0       0/0       Ray Cole

	Sorry ... no description available for LuckyBlindDrunk

=================================================================

======================================= Mr_Magoo =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
Mr_Magoo            0    0 1987 0/0       0/0       0/0       Justin Legakis

	Sorry ... no description available for Mr_Magoo

=================================================================

======================================= pathbreaker =============

=================================================================
    ENTRY       MOVES  UPS SECS amaze.me  multiplic potm.bldg    AUTHOR
pathbreaker         0    0 1992 0/0       0/0       0/0       John Williams
=================
pathbreaker was submitted by John Williams at jwill@chromatic.com
=================
HOW DID pathbreaker approach the task?  Special tricks?

  Pathbreaker attempted to pull the problem apart by finding the
  critical ( shortest ) path and selectively breaking one of the
  links. This relied on local information, so globally it was not
  optimized. I followed up by taking the remaining cubes and attempting
  to splice them into the existing path.
  
DID pathbreaker iterate in any way?  How did it know it was done?
  
  The first pass was where the problem was broken down and commitments
  made. The iterative passes are where remaining cubes were spliced in
  if possible.
  
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
  
  Basically I ran out of time for pathbreaker development. The first
  pass is the really important one, and I tried a few tweaks to
  optimize the selection of a path to break. More analysis here would
  probably yield better results.
  
WHAT DO YOU DO FOR A LIVING?  FOR FUN?  INNERMOST SECRET? POTM IDEAS?
  
  I'm a verification engineer and mostly hack perl and verilog. I wish
  I had time to have fun!
  
=================================================================