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