SCENIC TOUR 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).
NOTE: If a program ran longer than 720 seconds it was killed even if
it had not yet generated a solution. Entries had 600 seconds in
which to complete the task ... times for each problem are shown below.
-()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()-
============== 1 ====================== indiana_dijones =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
indiana_dijones 57.0 576/32816 2148.8 151/324473 104.7 355/37159
TIMES: a2b:456 graffiti:566 hand:484 TOTAL:1507_sec
=================
indiana_dijones submitted by Chad Hurwitz at churritz@cts.com
=================
++ Please summarize the algorithm used by indiana_dijones
Most everything is based on dijikstra's algorithm as you probably have guessed.
"Indi" tries to get to the golden statuette at the end of the map, as quickest
as possible, but once he takes it he has only so much time for the boulder to
follow him around, of course indi tries to maximize the time he has to escape
the boulder by making it go up and down mountains in the cave.
Shortest path is found by using the standard algorithm using fitness of
least total cost from start node with a small modification for zero costs
and diagonals. In order to minimize moves following zero cost links,
i multiplied any cost that was nonzero by (MAXLIMIT=255*20-1=5099)/4
and made zero costs 1. Also in order to maximize diagonals (to let the
longest path more easliy navigate around the shortest), i added 2 to
links that were north/south west/east.
After finding a shortest path i determined if it was possible to make a path
back to the start node. If a path was not possible, i would run the shortest
path again with a limit on the moves of the shortest path as LIMIT-SIZE.
This would ensure it would be possible to have a feasible solution of Fred's
devious problem.
For the longest path, i stumbled upon a slight modification to the shortest
path algorithm that would yieled reasonable longest paths with in a limit of
moves/hops. I used the same algorithm to get a longest path, but used a
fitness of greatest cost from node divided by moves to the K power. I would
run this algorithm with different K, varying from 1.1 to 3.8, i would get my
best results with K around 1.5. But most of the outcomes would make a path
with too many moves or too little moves, so from about 60 runs i would take
the path which had the best average cost per move.
From there I would improve upon the path with a simple insertion algorithm.
Between each two nodes in the path, i would look for at most a 4 node
path which could be inserted between the two to make a better path, with
out moving more than the limit of moves. The 4 was chosen because at
255x255 maps, 5 or more would estimate it would run more than 10 minutes
on Fred's machine.
If there was still time left after that, i would re-run the shortest path with
a shorter limit on moves, and then rerun the longest path. Then compare the
solution i got with the previous one and take the better longest/shortest
ratio, that seemed to prove the best step, for the two final problems, which
indiana_dijones found better longests because it reduced the moves the very
shortest path would have required.
++ Do you have any good references to recommend?
I wish, does anyone else have any references to longest path with a
constraint on hops? I did try to look but couldn't find any.
I would like to congratulate Cynthia for entering with a Sed program,
now there's a real programmer. And my personal favorite name,
Climb_Every_Mountain.
++ If I had it to do all over - here's what I would try ....
I started working on a better improver at the last moment, that would take
the longest path, pick a random node A, draw a longest path via the algorithm
above from the node (which could be in the middle), and then follow the
origonal path and determine if there is a better path from the followed node
back to node A, using the new longest path links. This didn't work out well
but i believe would be an option if there were enough time to debug.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
(1) You hiring?
(2) San Diego, California, USA
(3) Programming
(4) BassDrumMusic/3dGames/Programming
(5) Yes
(6) Always end on midnight sunday even if you have to delay the results for a
week and make sure there is a successor potm master, i hear Fred is
letting his cholesteral intake go wild.
=================================================================
============== 2 ====================== DVKha_DHTH_VN =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
DVKha_DHTH_VN 51.5 568/29232 1745.2 151/263529 75.5 349/26365
TIMES: a2b:540 graffiti:540 hand:540 TOTAL:1620_sec
______________________
POTM-MASTER NOTE: The following is extracted from the comments
in this program. If I receive a better description it will be
posted on the main POTM website at https://members.tripod.com/~POTM
______________________
/* VietNamese . */
/* Version 4.0 ! New version ! */
/* Thank you very much ! I am very happy when my program run on */
/* your machine */
/* I was compile it by GCC 2.7.2.1 (on MS-DOS , PC Pentium 166 MMX) */
/* My algorithm : First , I use DIJKSTRA algorithm to find shortest road */
/* from (0,0) to (size-1,size-1) . After that , I use greedy method to */
/* find longest road from (size-1,size-1) to (0,0) */
=================================================================
============== 3 ====================== Walking_with_my_dog =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Walking_with_my_dog 53.1 568/30158 1372.5 151/207247 100.0 349/34893
TIMES: a2b:580 graffiti:606 hand:582 TOTAL:1768_sec
=================
Walking_with_my_dog submitted by Guillermo Sais at gsais@iname.com
=================
++ Please summarize the algorithm used by Walking_with_my_dog
The algorithm is divided into two steps:
1. Finding the shortest path between the source (0,0) and the target
(n,n). This is the easy part of the algorithm, as there are many
straightforward algorithms for doing this, such as Dijstra's algorithm
(while there are better algorithms than Dijstra shortest path algoritm).
2. Finding the longest path between the target (n,n) and the source
(0,0). This is the nice (hard) part of the algorithm, so for now on I'll
only describe this step.
To find the longest path I use a divide-and-conquer approach. First, I
change all the edge's weights (weight=distance between two adjacent nodes)
using the following transformation:
F'(weight) = Treshold - weight; where Treshold = 256.
Then I find the shortest path (using the same algorithm as in step 1)
between the target (n,n) and all other nodes. I also find the shortest path
between the source (0,0) and all other nodes. Now, I've found the shortest
path from the source (0,0) and the shortest path from the target (n,n) for
every node in the grid, and I use this information to calculate a third
point (x,y) that maximizes the distance from the source *plus* the distance
from the target, while minimizing the number of total moves made.
As you can see by now, I've actually divided the original problem into two
smaller problems: finding the longest path between the target (n,n) and the
new point (x,y), and finding the longest path between the new point (x,y)
and the source (0,0). Now I'll repeat the same steps for each of these
sub-problems and I'll get two new points: (x1,y1) and (x2,y2). Next I'll
find which one of this points gives the best path, and then I'll discard the
other point. Now I've three smaller sub-problems, so I'll repeat the same
steps for each one of these... well, I guess you got the idea. But when
should I stop? good question, and a good answer would be to stop when the
number of moves reach the limit, or maybe when the time runs out, whatever
comes first... Then I simply put together all the sub-paths and that's it!
Now I can go walking with my dog... or not?
++ Do you have any good references to recommend?
There's only one better reference than Knuth's "The Art of Computer
Programming; Volume 1: Fundamental Algorithms", and that reference is, of
course, Knuth's "The Art of Computer Programming, Volume 2: Seminumerical
algorithms", (or maybe Knuth's "The Art of Computer Programming, Volume 3:
Sorting and Searching").
Well, you know what I'm talking of, don't you? Despite being almost
*three* decades old, Knuth's work still represent the most complete
reference about algorithms that I've ever seen anywhere, period.
++ If I had it to do all over - here's what I would try ....
I'd certainly try the same algorithm but using a variable treshold value. My
current algorithm uses a fixed treshold value of 256 so that all edges have
positive values. The main problem with the fixed treshold approach is that
the resulting transformation is not "accumulative", that is:
F'(x) + F´(y) <> F´(x + y)
*** NOTE *** the transformation function is: F'(x) = Treshold - x.
Using a treshold value of 0, the transformation is perfectly "accumulative":
F´(x) + F´(y) = F´(x + y)
Following is a description of the variable treshold algorithm:
STEP 1:
TresholdMin = 0
TresholdMax = 255
STEP 2:
Treshold = (TresholdMin + TresholdMax) /2
STEP 3:
Find path using current Treshold.
STEP 4:
if Path.Moves>Limit then
TresholdMin = Treshold
else if Path.MovesSE. Next, we "normalize" it.
(D) Choose the coordinate (x) on the string with the maximum (or minimum,
on the return trip) altitude difference between its own Cummulative
Distance and the Cumulative Distance of one of its neighbouring points
on the string (y). The delta-Step count between (x) and (y) must be
greater than 1. "Snip out" the coordinates on the string that lie
between coordinates (x) and (y); zero the Step Count and Cummulative
distance of the intermediate points and make (y) the next immediate
point on the string after (x). Repeat this until there are no points
on the string which are more than 1 Step adjacent to any other point
on the string.
1 2 3 1 . . 1 . .
. 4 5 . 2 3 . 2 .
. . 6 . . 4 . . 3
String String after String after
as Plotted 1st iteration 2nd iteration
normalization. normalization
(String segment (String segment
1-4 snipped.) 2-4 snipped.)
(E) Reset the Visited Counter for all coordinates on the map. Put the
pointer on the SE point of the map. Repeat Steps (B) and (C)
(as required) until arriving at the NW corner of the map.
Now we have a string from SE->NW. Time to "normalize" it too.
(F) Snip-out some loops in the return string using step (D). Choose loops
that have a large number of steps but a small difference in Cumulative
Distance. Keep snipping until the total number of steps (NW->SE->NW)
is equal to the specified Map Limit. Print the string, exit, and go
to the Mall.
"Timing Code? Timing Code? We don't need no steenking timing code."
++ Do you have any good references to recommend?
Not precisely on the topic, but well worth having a look at:
Kip S. Thorne, (1994). "From Black Holes to Time Warps: Einstein's
Outrageous Legacy". W.W. Norton & Company, Inc. New York, New York.
M. Mitchell Waldrop, (1992). "Complexity: The Emerging Science at the Edge
of Order and Chaos". Touchstone. New York, New York.
++ If I had it to do all over - here's what I would try ....
The *order* of directions tried from a given point can make a large
difference between the optimum string and the plotted string (if there
are multiple steps with the same delta-altitude). So...
A method of keeping track of divergent steps that have the same altitude
difference from a single point would make it possible to back-peddle and
plot multiple strings where the altitude doesn't change (as in the graffiti
map).
The normalization routine could be more intelligent by looking at
neighbouring points 2 away, rather than just 1.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Almost never. Calgary, Canada. Freestyle code cutter and sysadmin.
=================================================================
============== 13 ====================== Plateau_and_Climax =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Plateau_and_Climax 31.4 614/19284 0.0 (ERROR) 45.4 355/16111
TIMES: a2b:171 graffiti:596 hand:75 TOTAL:842_sec
=================
Plateau_and_Climax submitted by Randy Saint at saint@phoenix.net
=================
++ Please summarize the algorithm used by Plateau_and_Climax
I started with a modified A* to find the levelest path. Then reversed the
check to find the bumpiest path. I used the average altitude delta as the
cost function for the reverse path. It seemed to work ok.
++ Do you have any good references to recommend?
I'm still trying to find a good reference on Iterative Deepening A* (IDA*).
++ If I had it to do all over - here's what I would try ....
I had the shortest path done just after the contest started, but couldn't
come up with a logical "best path" method for the bumpiest path. I didn't
work on it in earnest until a week before the deadline. I used average cost
to come up with a path, however the algorithm doesn't use all possible steps
to maximize the total cost.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Lockheed Martin, Houston, TX, Working at NASA JSC.
Fun? Programming contests.
Secret? I'm just a programmer at heart, but at work I've gone into
management to further my career.
Visit my Computer Programming Contests page:
http://www.c-com.net/~saint/contests/
=================================================================
============== 14 ====================== Cool_proga =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Cool_proga 19.7 900/17748 11.9 4573/54211 42.5 417/17721
TIMES: a2b:592 graffiti:592 hand:591 TOTAL:1776_sec
=================
Cool_proga submitted by Pavel Zaletskiy at pavelz@dpt.ustu.ru
=================
++ Please summarize the algorithm used by Cool_proga
1) program searches the short pathes (one of each possible length),
wich most of all match a criteria. The criteria attemts to account
a possible long path length for given short path.
2) after first step, program search long path for each found short path.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I am the student of the fourth grade of Ural State Technical
University (Ekateriburg, Russia) (now I am going to the fifth grade).
I am working simultaniously with studing. I am system engineer.
I liked to participate in the POTM. I did it just for fun.
=================================================================
============== 15 ====================== Hey_take_a_hike =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Hey_take_a_hike 36.8 568/20890 0.0 (ERROR) 33.5 349/11695
TIMES: a2b:598 graffiti:470 hand:598 TOTAL:1667_sec
=================
Hey_take_a_hike submitted by Grant Davis at gwd@lucent.com
=================
++ Please summarize the algorithm used by Hey_take_a_hike
1. Determine THE minimal path from start to turn-around point.
If it's not legal (too long), substitute a suboptimal, but
legal, path.
2. Sort cells according to altitude.
3. Choose a high or low cell that will fit in a path from the
turn-around point to the start. Add cells (alternately) until
an arbitrary search depth is reached.
4. Repeat step 3 with a new starting cell until the time is up.
++ If I had it to do all over - here's what I would try ....
Get it done earlier so I could tinker more ... gee if I'm still
tinkering I guess it wasn't done.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Company - Lucent Technologies
Location - Middletown, NJ (Red Hill)
Job - Whatever
Do for fun - Softball, Hiking (Really!)
Innermost Secret - Is this Jerry Springer? Hey, take a hike!
=================================================================
============== 16 ====================== procrastinator =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
procrastinator 16.9 568/9610 37.1 647/24011 16.0 349/5585
TIMES: a2b:239 graffiti:241 hand:235 TOTAL:715_sec
=================
procrastinator submitted by Ben Nye
=================
++ Please summarize the algorithm used by procrastinator
try a bunch of ways to make short paths, then for each one
try a bunch of ways to make a long path, if there is time left,
run a few passes of iterative refinement over each path.
output the best path produced by any combination.
Try to do the fastest methods first, in case it doesn't have time
to try all of them.
++ If I had it to do all over - here's what I would try ....
start WAY earlier, I didn't get the iterative refinement done in time
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
location: Missoula, MT
Job: programmer
for fun: write suicide chess programs, play chess/suicide chess,
play WarcraftII, hike
=================================================================
============== 17 ====================== PEPPER =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
PEPPER 25.5 746/19046 0.0 (TIME) 39.7 373/14811
TIMES: a2b:8 graffiti:723 hand:6 TOTAL:738_sec
Sorry ... no description available for PEPPER
=================================================================
============== 18 ====================== Sieger =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Sieger 27.0 572/15464 0.0 (TIME) 35.2 355/12499
TIMES: a2b:542 graffiti:731 hand:518 TOTAL:1793_sec
=================
Sieger submitted by Oleg Pavliv at OlegP@lynx.ch
=================
++ Please summarize the algorithm used by Sieger
Shortest path I calculate using Dejkstra (spelling can
be incorrect) algorithm.
Finding longest path.
At first I calculate the average distance.
I use the algorithm with random values.
The larger distance we have, the more probable it will be chosen.
If I see the number of moves will exceed the LIMIT I go
to the (0,0) point with the shortest number of moves.
++ Do you have any good references to recommend?
No. I use only my own ideas.
++ If I had it to do all over - here's what I would try ....
Build the grid with larger cells, I'll unite the cells
using the average values or the average distance. I'll
have the grid with smaller size. Solve the problem on
this average grid. Than I'll find the best path between
the average cells.
The other idea is the same as I implement in my
solution, but to divide the grid on two parts, solve the
problem on each and unite them. This can be done recursively.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Lynx Software Research AG.
Langenthal, Switzerland.
I'm group leader in large project MiracleV. This is
object-oriented system to create business applications.
=================================================================
============== 19 ====================== Alpinoid =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Alpinoid 14.3 1344/19244 0.0 (TIME) 43.4 465/20163
TIMES: a2b:614 graffiti:742 hand:613 TOTAL:1970_sec
=================
Alpinoid submitted by Davor Slamnig at slamnig@fa2.so-net.or.jp
=================
++ Please summarize the algorithm used by Alpinoid
Alpinoid is not-quite-deterministic, with some randomizing and a
lot of hard-coded rules. It loops the methods, searching for the best
low path for 2 minutes and then generates high paths for the rest of the
alotted time.
Basically, there are 6 mechanisms involved:
1. Building the low path
2. Building the high path
3. Optimizing the low path
4. Optimizing the high path
5. Lengthening the high path
6. Shortening the high path
The general looping goes like this:
while(under 2' execution time){
Build low path
Optimize low path
}
The best low path is stored.
while(under 10' execution time){
Build high path
Lengthen/Optimize high path
[Shorten high path]
}
The best high path is appended to the best low path.
Read the rest if you must.
1. Building the low path
The initial low path is built very simply.
If we're starting from 0, 0 then the possible moves are:
right
down
right/down (diagonal)
This guarantees the ending on (size - 1), (size - 1).
The moves are usually made to the square with the smallest altitude
difference.
Some randomizing is done here, so sometimes it jumps to the square
with the next smallest difference.
3. Building the high path
The initial high path is built simply, too.
If we're starting from 0, 0 then the possible moves are:
right
down
right/down
up/right
down/left
This almost guarantees the ending on (size - 1), (size - 1).
We're keeping our fingers crossed that the (final )low path
will not obstruct the end square, since the high path is generated
after the low path is fixed.
The moves are usually made to the square with the highest altitude
difference.
Some randomizing is done here too, so sometimes it jumps to the square
with the next highest difference.
3/4. Path optimization
The paths are traversed from beginning to end, and each consecutive 3-step
segment is compared to a list of 52 possible 3-square spatial relationships,
"patterns". The list also contains alternative patterns (with identical
starting and ending points). The alternative patterns are tested out on the
board. An alternative path segment that yields the best altitude difference
(lowest for the low path or highest for the high path) is used to modify
the original path.
This is looped until no more optimization can be done.
5. Lengthening the high path
If the high path is too short (low path length + high path length <
max path length), it is lengthened.
The path is traversed from beginning to end, checking out possible inserts
(adding a step to the path).
The insert that yields the highest altitude difference is added to
the original path.
This is looped until low path length + high path length
== max path length.
6. Shortening the high path
If the high path is too long (low path length + high path length >
max path length), it is shortened.
The path is traversed from beginning to end, checking out possible deletes
(removing a step without breaking the path).
The deletion that yields the lowest altitude difference is carried out.
This is looped until low path length + high path length
== max path length.
++ If I had it to do all over - here's what I would try ....
I've been thinking about low-pass filtering of the grid to make it simpler,
and then gradually "de-filtering" it, adjusting the path to fit.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I work as a C/C++ programmer for TechnoCraft, a small Japanese company
specializing in automated dictionary software.
I live in Zagreb, Croatia (working on-line).
For fun I bought a small add-on bicycle seat for my 3-year-old son,
and we cycle around as much as the summer heat allows.
=================================================================
============== 20 ====================== chachacha =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
chachacha 10.7 1358/14596 19.3 1523/29469 18.6 497/9225
TIMES: a2b:530 graffiti:534 hand:533 TOTAL:1598_sec
=================
chachacha submitted by Aivars Zogla at fix.lv!uvsk@kcig2.att.att.com
=================
++ Please summarize the algorithm used by chachacha
CHAnceCHAnceCHAnce - in other words - lottery again. So, I leave all for
chance this time and hardly exploit random generator.
1) Shortest path from 0,0 to SIZE-1,SIZE-1 (best from some hundreds);
2) Long path back to 0,0 + extra steps to get LIMIT if possible (about 50
tries on each long path) - until timeout. To make extra step - take two
steps made, which are next to each other and share unused square.
++ Do you have any good references to recommend?
This time was full of unportability in C, so I had to switch to JAVA and
only reference used was JAVA handbook and language reference. If you
wouldn't like to have portability problems in POTMs - use JAVA!
++ If I had it to do all over - here's what I would try ....
Avoid random somehow. Don't like it.
++ COMPANY? LOCATION? JOB?
Ugale Secondary School. Latvia. Comp.science.
DO FOR FUN? INNERMOST SECRET?
Do you have time for fun or secrets with 255x255 grid?
POTM IDEAS?
While I've got aquainted with programming tasks in different school level
programming contests - there are a lot of them, just pick one!
Regards and good luck to all active POTMers!
=================================================================
============== 21 ====================== Meander =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Meander 6.5 2324/14990 8.8 4849/42545 31.7 753/23887
TIMES: a2b:513 graffiti:595 hand:513 TOTAL:1621_sec
Sorry ... no description available for Meander
=================================================================
============== 22 ====================== Trip =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Trip 32.9 568/18684 0.0 (TIME) 8.3 349/2885
TIMES: a2b:186 graffiti:720 hand:129 TOTAL:1036_sec
=================
Trip submitted by Zsolt Peter at pzsolt@valerie.inf.elte.hu
=================
++ Please summarize the algorithm used by Trip
>
First I found the way from (0,0) to (n,n) with the minimum altitude.
After that I went back to (0,0) with the minimum number of steps, and
until the allowed step number was greater than the stept I did, I put
(~shortcuts) - not shortcuts, but ... - in the back way trying to maximize
tha altitude this way.
++ If I had it to do all over - here's what I would try ....
>
I would do the finding of the backway in an other way, but I don't know
how, yet.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Zsolt Peter (Peter is my family name),
student at Eotvos Lorand University of Science, Budapest.
=================================================================
============== 23 ====================== ObsceneTour =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
ObsceneTour 20.6 568/11724 0.0 (TIME) 14.0 349/4899
TIMES: a2b:590 graffiti:663 hand:590 TOTAL:1843_sec
=================
ObsceneTour submitted by P.Sedik J.Lorinc at Juraj.Lorinc@nbs.sk
=================
++ Please summarize the algorithm used by ObsceneTour
Peter Sedik explains:
1) First, we are looking for the short path using incremental algorithm :
For the each square, we are storing the shortest path length found, the
previous square and the number of steps for that path. We loop through the
scene, until at least one square can be "improved", either by shortening
the path leading to this squares, or by cutting down the number of steps.
The algorithm stops, when no square can be improved. Then we can trace back
the shortest path from bottom right square to the start. Also, the path
limit should be taken into the consideration - in our version we didn't
accept paths, whose steps exceeded the number LIMIT - 2*SIZE.
2) Now we have short path choosen, the next step is to generate the
corresponding long path. We have used "random generation" approach here.
Begin with the bottom right corner, we choose randomly neighbour square
(which isn't occupied) and add it to the path. This continues, until we
reach the starting square. When the square is blocked (no free neighbour),
we should return one square back and try another direction.
3) The long path is then adjusted to the LIMIT length. This is done by
randomly adding (when the path is shorter) or deleting squares. In the
second case, it may happen that no single square can be removed from the
path, then we change the seed for random generator and start again from the
point (2).
4) The "simulated annealing" kind of algorithm is then used the optimize
the long path:
We generate (int the loop) the new long path from the old one by shift of
just one randomly selected square. This modified path is taken as
a source of a new path generation, if and only if the length
doesn't drop under choosen boundary. In this loop, we
always store the best path found. After 200 tries, we take the best path
found as a new source and increase the boundary. The loop ends,
if the path cannot be more optimized. Then, we store the final path
found, change the seed for random generator and
continue again from point (2), until the time limit is reached.
++ Do you have any good references to recommend?
Juraj Lorinc shrugs:
I did some search in local libraries and on Internet about longest (or most
expensive) path problem in graph theory as I did another 'recherche'
anyway. I knew that problem is NP-hard, given limits made him even harder
:-) In fact I found only small amount of useful information from which we
used nothing.
Probably the most fruitful was reading of old POTM solutions where the idea
of different "random" algorithms appeared suprisingly often. Finally we
tried to implement the idea of "simulated annealing" recommended by another
friend, Chalmo.
++ If I had it to do all over - here's what I would try ....
Juraj Lorinc sighs:
We were very short of free time. I'm C-analfabet. We had no Unix machine to
make longer testing - only Peter found some in our old school and he tested
the entry - but the results already on given test example wasn't very
satisfying. Between 15 - 20. The main problem in our algorithm is finding
the initial long path - it is also possible that in the time limit will be
found no one and it means exceeding time with no output. But let's wait for
final test results :-(.
We had a lot of ideas that remained unimplemented - the most interesting is
by my opinion the following:
1) By the algorithm that finds the short path in our actual entry, we can
get also the set of about 5-10 short paths that are tried as initials for
the "random" algorithm.
2) For all squares we can compute the number that characterizes the quality
of edges in his neighbourhood. Then we can sort them by this number. (One
unsolved question is: how to compute this quality ? - I tried some
functions but no one satisfied me...)
3) Take given amount of random squares, in this generation preferring the
squares in the head of described sorting.
4) Find any path through selected squares.
5) Using local optimization (3 kinds - shortening, with equal length,
prolonging) find some long way that cannot be locally optimized.
Well, a lot of other ideas appeared during our discussions but mostly
remained in the words.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Peter Sedik about himself:
I'm working as software developer in the company called Nemetschek.
Location: Bratislava, Slovakia.
Some "doforfuns" : sundown watching, chess programming, billiard,
beerdrinking...
POTM Ideas: Advertise your site, so this nice competition can be more
widespread. I have found POTM website about 3 months ago by randomly
browsing Yahoo. When someone is looking for programmers competition using
search engines, there's only a small chance that he will jump there.
Juraj Lorinc about himself:
Company, location: National Bank of Slovakia, Bratislava, Slovakia.
Job: Officer - specialist, my main duties include MS Excel programming,
Prolog programming - unusual combination, isn't it?
Hobbies: above all chess composition, especially fairy chess, girls (:-)),
mathematics, basketball, books, choir singing and music generally,
programming, solving puzzles, ...
Innermost secret: I WANT TO BECOME FAMOUS!!!
POTM ideas: There are some connected with chess composition - e.g. given
the different pieces and board size, find positions matching given criteria
that would be specified. The point behind is that it may give very
interesting fairy composition - and the programer needn't know anything
about playing chess.
=================================================================
============== 24 ====================== moon_patrol =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
moon_patrol 8.4 1532/12918 0.0 (ERROR) 25.5 483/12309
TIMES: a2b:494 graffiti:502 hand:500 TOTAL:1496_sec
=================
moon_patrol submitted by Jesse Ziser at jz@ccsi.com
=================
++ Please summarize the algorithm used by moon_patrol
Basically, it moves one square at a time, without thinking
ahead (I tried to give it plan-ahead abilities, but it didn't work
well). At each square, it looks at all eight surrounding squares
and assigns a weight to each direction depending on its value
relative to the current square. For trip 1, this weight is the
reciprocal of the difference in height. For trip 2, it's just the
difference in height. It then uses these weights to randomly
pick a direction. Note: for trip 1, moon_patrol is limited to only
3 directions: S, E, and SE. that way, it's always heading toward
the other end. Note 2: for trip 2, an extra condition is added to
all "backward" directions (SW, S, SE, E, NE): You can't go
back if you're almost out of spare moves (in other words, if
your moves don't exceed the length of an L-shaped path to the
end). Got all that? OK. Well, it repeats that whole process for
trip 1 many times, until 3 min. have elapsed. It picks its best
score out of all those runs. Then it does the same for trip 2 for
6 min. It puts the two trips together and, voila! The End.
++ If I had it to do all over - here's what I would try ....
I asked myself this and did everything I thought of. Nothing
else left.
++ COMPANY? LOCATION? JOB? DO FOR FUN?
INNERMOST SECRET? POTM IDEAS?
I'm 17 and don't currently have a job, but I want one. I live in
south Austin, Texas. For fun I (obviously) program my brains
out. I also enjoy digital electronics. As for music, I listen to
Enya and a certain variety of techno (incompatible tastes, I
know). My secret is a "very superior" IQ. (That's what the IQ
test called it.) (I'm not trying to brag or anything) (I also have
my disadvantages) (But I won't tell you any of them :-)
=================================================================
============== 25 ====================== gridders =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
gridders 8.7 1520/13168 11.3 3765/42493 7.7 795/6109
TIMES: a2b:544 graffiti:543 hand:540 TOTAL:1627_sec
=================
gridders submitted by Stefan Foerster at Foerster@augsburg.baynet.de
=================
++ Please summarize the algorithm used by gridders
The main idea is to use evolution as an optimization algortihm.
Since evolution usually is a very slow process I haven't expected
the algorithm to be good enough to win, but I simply wanted to test
genetic algorithms. Some infos about such algorithms can be found in
an old edition of "Scientific American" (I don't find it at the moment).
++ Do you have any good references to recommend?
I now have found the paper which inspired gridders: It appeared
in "Spektrum der Wissenschaft" (i.e. the international edition
of "Scientific American") January 1986. It is one of the monthly
"Computer-Kurzweil" papers (don't know the English title) by
A. K. Dewdney.
++ If I had it to do all over - here's what I would try ....
I more straightforward and simpler algorithm.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
See my homepage: http://home.augsburg.baynet.de/stefan.foerster
=================================================================
============== 26 ====================== ScenicTour =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
ScenicTour 0.0 (ERROR) 10.9 1171/12785 8.9 515/4595
TIMES: a2b:1 graffiti:1 hand:0 TOTAL:3_sec
=================
ScenicTour submitted by Mike Arsenault at mike.arsenault@objectquest.com
=================
++ Please summarize the algorithm used by ScenicTour
I tried a few of them. But the one I settled on was to look ahead 'x'
number of nodes and to find the best path (minimum score for
forward/maximum for return) for those 'x' nodes. Once I found the best
path, then I would take the first node in the direction of that path. For
example, if 'x' was 6 and I was at the upper left node I would look at all
possible 6-node paths, moving down to the right. I would choose the best
6-node path and then I would simple take the first step along that path and
the repeat the process. The thinking was that if I moved to the closest
node that looked the best, I may be missing a real potential gain somewhere
else.
After I achieved a legitimate complete path, I would try to improve on it
by hopefully compressing two movements into one on the forward path or
changing one move into two while increasing the score on the return path.
This process, oddly enough, never did improve on the results, unless there
was a bug in the code :-).
Unfortunately, I didn't spend as much time on this problem as I wanted to.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
ObjectQuest Corporation
Burlington, Ontario, Canada
Senior Software Engineer
=================================================================
============== 27 ====================== HiLowSilverTourney =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
HiLowSilverTourney 4.3 1882/8066 4.4 1571/6835 10.6 485/5157
TIMES: a2b:2 graffiti:3 hand:1 TOTAL:7_sec
=================
HiLowSilverTourney submitted by David Peterson at dpeterso@isd.net
=================
++ Please summarize the algorithm used by HiLowSilverTourney
Direct paths with hi/low search.
++ Do you have any good references to recommend?
Nope.
++ If I had it to do all over - here's what I would try ....
Finding more time.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
United Healthcare Corporation
Senior Software Engineer (Powerbuilder - Sybase)
Kids Taxi driver
Prefer Pascal
=================================================================
============== 28 ====================== imlost =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
imlost 0.0 (TIME) 0.0 (TIME) 18.3 349/6377
TIMES: a2b:721 graffiti:724 hand:78 TOTAL:1524_sec
=================
imlost submitted by Eric Weeks at weeks@dept.physics.upenn.edu
=================
++ Please summarize the algorithm used by imlost
I try to find the best short path going there (lowest
total distance, even if it takes many steps), and then I find the
quickest path back. I then add on additional steps to the return
path, adding on one step at a time, each time adding the single
step that would have the most distance. This algorithm isn't
great (thus my not-so-high scores) but it's easy to implement.
My original plan had been to find the quickest path back, then look
for side excursions that would get me to those high and low points,
and then finally add on a few additional steps to the resulting path
to help use all the steps available. The few times I tried to ride
this side excursion routine, it never worked, and then I never had
the time to go back and make it work. However, I had already
written the part that adds on additional steps one at a time, so
that's what I submitted.
My algorithm for finding the best short path was fairly simple: find
the best short path to every single point, somewhat recursively, and
then in the process I can extract the best short path to the far
corner.
++ If I had it to do all over - here's what I would try ....
I'd try to find more time to work on this! But the side excursion
problems were just taking too long and getting unfun to debug.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I'm working at the University of Pennsylvania, as a physicist
(postdoc).
=================================================================
============== 29 ====================== TwoFlower =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
TwoFlower 0.0 (ERROR) 0.9 4889/4573 17.4 911/15857
TIMES: a2b:501 graffiti:498 hand:490 TOTAL:1491_sec
> =================
> TwoFlower submitted by Don Ross at drdt@world.std.com
> =================
> ++ Please summarize the algorithm used by TwoFlower
First, let me wsay I really, really loved this problem. It is a pity I ran
out of time before I got my homebound algorithm to work... I ended up
submitting my placeholder algorithm which was pretty stupid (although it did
solve the one_way.pgm test problem perfectly).
Because of the threat of running out of time on large maps, my strategy was
to run through a series of passes, allowing a maximum time period for each,
using smarter algorithms for each pass. All path-generation algorigthms
were recursive, allowing me to wander around until I either got to the end
or got somewhere I didn't want to be, in which case I could back up.
The first outgoing pass, I made a straight line from corner to corner. The
second pass I looked for the shortest climb relative to each step with no
forward planning (although I made sure that I never walked directly away
from the destination). This tended to produce switchbacks. I did this in
both directions and chose the best path of the three. The fourth outgoing
pass, I found all the high and low points along the path I had chosen, and
found the optimal path around them without doubling my path length. The
fifth outgoing pass, I optimized out the switchbacks.
As I mentioned, the incoming path was not completed. I basically used a
stupid copy of the outgoing algorithm, which looked for the worst climb
relative to each point and didn't worry about walking backwards. Again I
did this in both directions and took the best of the three.
This gave a fairly good solution, hopefully at the end of five mionutes.
If there was time, I then went back and indexed the top 100 'peak' and
'valley' points (where slope = 0), excluding large plateaus. These I
declared 'off limits' for the outgoing path, and then reran the entire
procedure. This meant (for example) that a winding path through the hills
would not be used for the outgoing path, allowing it instead to be used by
the incoming path, which would make better use of it by jumping on and off
of it. Theoretically. This would give me a second solution, and the
solution I printed out was the better of the two.
Of course, if I ran out of time at any time, I would print what I had then.
The finished incoming algorithm would have taken (will take) this list of
peaks and valleys and build a path connecting as many of them as possible
with short straight lines. Then I would finish off by taking each of these
short lines and trying to pessimize it using the stupid algorithm.
> ++ If I had it to do all over - here's what I would try ....
I'd start earlier! But seriously, I'm not done. I think I would have a
really great solution if I hadn't run out of time, so I won't be looking at
the solutions until I actually finish it and see how it does.
=================================================================
============== 30 ====================== The_Walker =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
The_Walker 2.8 3320/9194 9.2 4889/44985 4.6 911/4221
TIMES: a2b:0 graffiti:0 hand:0 TOTAL:1_sec
=================
The_Walker submitted by Matthew Haley at mhaley3@umbc.edu
=================
++ Please summarize the algorithm used by The_Walker
The_Walker uses a very generalized method. First it reads only the LIMIT
and SIZE of the grid from the file. For the short score The_Walker
believes a straight line is the shortest distance between two points, so it
prints out the points going diagonally and increases the move counter. For
the long distance The_Walker zig-zags back and forth diagonally printing
the points and updating the move counter until either of two conditions
happens
a. Reach point 0,0 or,
b. (LIMIT-count)-1 is less than either the row value or column value which
ever is larger.
If a. The_Walker ends. If b. The_Walker starts going diagonally toward 0,0
until it reachs 0,0 or one of the edges at which point it goes straight to
0,0.
++ If I had it to do all over - here's what I would try ....
I tried a recursive approach that tried to find the shortest route, but
could not stay under 10 minutes just calulating the short route.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
=================================================================
============== 31 ====================== Loopy_Loops =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Loopy_Loops 4.7 702/3320 11.0 445/4889 0.0 (TIME)
TIMES: a2b:2 graffiti:4 hand:723 TOTAL:730_sec
=================
Loopy_Loops submitted by Martin Fouts at fouts@null.net
=================
++ Please summarize the algorithm used by Loopy_Loops
Loopy_Loops parses the input and builds the conective graph of the
array, using the altitude deltas as weights. It builds the graph in
such a way that it can construct the lowest cost path with the
shortest length among the low cost paths path from the start
point to the mid point as it goes.
Once it has the graph it builds a return path using a depth first
search.
The next step was supposed to be a heuristic that substituted legs
until all of the available path was consumed, but that part of the
algorithm is broken.
++ Do you have any good references to recommend?
No. I was clearly in over my head on this problem -- although I had
fun anyway.
++ If I had it to do all over - here's what I would try ....
Fixing the "rubber band" heuristic for substituting legs...
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Self employed, MT View CA, writer/photographer, bicyclist, 17 (no, I
mean 42,) unfortunately none.
=================================================================
============== 32 ====================== Brown_walker =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Brown_walker 8.2 568/4662 0.0 (TIME) 5.3 349/1851
TIMES: a2b:548 graffiti:720 hand:551 TOTAL:1819_sec
++ Please summarize the algorithm used by Brown_walker
Way down: For each point I find way with minimal score. I started
at (0,0). Then I calculate score for neighbours and so on.
When I arrived at (SIZE-1,SIZE-1) way down was found.
Way up: For each point I find ways with length K steps and
maximum score.
++ If I had it to do all over - here's what I would try ....
I didn't think that my program is so bad.
I can't image how I can improve my program?
And I want to know how they solved problem very much.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I'm from Russia. I work in investment company.
I like reading books, surfing Internet, music, etc.
=================================================================
============== 33 ====================== TheseBootsWereMadeForWalkin =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
TheseBootsWereMadeForWalkin 8.0 1708/13600 0.0 (TIME) 4.3 737/3173
TIMES: a2b:4 graffiti:726 hand:3 TOTAL:733_sec
=================
TheseBootsWereMadeForWalkin submitted by Don Pratt at dpratt@dataworks.com
=================
++ Please summarize the algorithm used by TheseBootsWereMadeForWalkin
The basic routine is a simple recursive routine that takes the current
path and the goal and adds one more step to the path. To add a step,
it evaluates the surrounding 8 points. If the point is valid,
it computes a score based on the elevation change to the
new point and the distance between the new point and the goal (points
closer to the goal are ranked higher on the outbound path, lower
on the return path). The point with the best
score is picked, and then it tries to add a new point from there. If it
is unable to build on the path, we remove the last point added, and
use the next highest ranked point.
++ If I had it to do all over - here's what I would try ....
I would probably look into an algorithm that takes a global approach,
looking for areas that have large changes in altitude to include
on the return trip. I would also make
sure to start earlier to try and avoid last-minute porting problems
(sorry Fred).
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I work for DataWorks Corp. in San Diego, CA as a Programmer/Analyst
(though we're getting new titles any day - yippee!). For fun
I enjoy building and flying radio controlled
gliders. My only suggestion (really a request) is keep 'em coming.
=================================================================
============== 34 ====================== Kazak =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Kazak 0.0 (TIME) 0.0 (TIME) 10.8 649/6979
TIMES: a2b:736 graffiti:740 hand:388 TOTAL:1866_sec
++ Please summarize the algorithm used by Kazak
My algorithm is simple (I "invented" it for one game, but later read
it in a book - don't remember which one):
On direct way:
(0) Compute the value (very BIG in the beginning) of every cell (to go
into), and mark, where did we go from (from which neigtbour).
(1) Try to go to all the possible neigtbour cells and compute
the value of this moving
(2) If this value is cheaper that the previous, we rewrite this
value, go to this cell and recompute all its neigtbours.
(3) Stop when aren't possibilities to make something cheaper.
On back way:
The same idea, but with an economy of moves.
Everytime I test to don't repeat any cell (TestChain procedure).
++ If I had it to do all over - here's what I would try ....
I invented a very good algorithm, but it is slow, and I don't have a
time to realize it.
It is for the back way, but can be inverted.
(1) Calculate the average value of one move (let it be X)
(2) Mark all the chains (connections between 2 cells) which are
more expensive than 1.5*X (or 2*X)
(3) Connect all the chains into one big graph
(4) Resolve it as an problem of graph theory, or full-tree search
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
LOCATION - Moscow
JOB - I write a master's thesis and work sometimes as a programmer
(Delphi)
=================================================================
============== 35 ====================== STARSH1P_T1TANIC =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
STARSH1P_T1TANIC 6.8 568/3850 0.0 (TIME) 3.0 349/1033
TIMES: a2b:250 graffiti:721 hand:180 TOTAL:1151_sec
=================
STARSH1P_T1TANIC submitted by Henry Liss at 2hank@prodigy.net
=================
++ Please summarize the algorithm used by STARSH1P_T1TANIC
Short Path:
Each cell was given the following attributes:
#BestDirection - Which direction should I travel if I find
myself on this cell.
#Moves - if I followed all the BestDirections from here
to the goal, how many moves would it take?
#Distance - if I followed all the BestDirections from
here to the goal, what would my total vertical
distance traveled be?
First you mark all the cells as having an invalid or max
#distance/#moves/#direction. Then you mark your goal (location 30,30 if
this was the test sample) with a #distance and #move of zero. Next you
cycle threw each cell starting at your goal, moving backwards to
location 0,0. You ask each cell the following question: Out of the eight
directions, after adding in the distance between me and that direction,
which direction gives me the lowest Total Distance Traveled from my
current location to the goal? (or which would give me the lowest
#Distance) After that is figuered out, I update that cells #Distance,
#move and #BestDirection so that the other cells can point to it,
After you cycle threw all the cells using the above formula, you can
then start with location 0,0, and follow it's BestDirection to the next
cell, to the next cell etc, until you reach your goal.
Programmed in the right way, and given an unlimited number of moves, the
above procedure will generate a perfect low score.
Note:
1) using the above formula, it is not possible to visit the same cell
twice.
2) if you cycle threw all the cells enough times (using the above
formula) you can solve a pgm that looks like a maze.
Long Path:
The long path totally stumped me, I mean I had ideas, but nothing as
nice as my short path. I basiclly ran out of resources, as other areas
of my life needed attention. But look out during the next contest, I'm
determined to take home that rotating trophy one of these days!
The long path is pretty much the same as the short path, except I
subtract the vertical distance between two cells by 255 and take the ABS
value. This fooled my program into looking for the shortest path that
generated the highest score.
++ Do you have any good references to recommend?
No, sorry, I just made it up as I went along.
++ If I had it to do all over - here's what I would try ....
I have no clue... The short path subrouteens are perfect, but I'm
totally stumped by the long path.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I live in East Hartford, Connecticut. I'm really a VB programmer
trying my best to program in Visual C++ for the contest!
I really love creating fast sort routeens, So I guess i'd be really
excited if a future POTM contest contained such a challange!
=================================================================
============== 36 ====================== Bozo5_TM_Tour_De_Chance =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Bozo5_TM_Tour_De_Chance 2.4 3320/8100 3.1 4889/15281 2.9 911/2633
TIMES: a2b:2 graffiti:3 hand:2 TOTAL:8_sec
Sorry ... no description available for Bozo5_TM_Tour_De_Chance
=================================================================
============== 37 ====================== CaveWalker =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
CaveWalker 1.5 3320/4976 5.4 913/4889 1.1 911/1015
TIMES: a2b:23 graffiti:33 hand:18 TOTAL:76_sec
=================
CaveWalker submitted by Trevor Morris at trevor@lab.com
=================
++ Please summarize the algorithm used by CaveWalker
Travel straight from 0,0 to n,n. Travel straight from n,n to
0,n then straight to 0,0.
++ Do you have any good references to recommend?
I have written a long white paper on this highly sophisticated
algorithm, but it is considered proprietary by my company.
++ If I had it to do all over - here's what I would try ....
I would try to find some time to actually implement something
a little more sophisticated.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
=================================================================
============== 38 ====================== ThePathThatNeverEnds =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
ThePathThatNeverEnds 0.8 4976/4070 5.7 913/5229 0.5 2015/989
TIMES: a2b:597 graffiti:597 hand:596 TOTAL:1791_sec
=================
ThePathThatNeverEnds submitted by Darren Davis at jpdavis@webspan.net
=================
++ Please summarize the algorithm used by ThePathThatNeverEnds
The Short Path:
It went along the top and right, and compared that to going along the
left and bottom. Whichever was shorter was used.
Then it moved diagonally up and to the left.
The Long Path:
For about 10 minutes, it tries random paths back to (1 1). Whichever
is the shortest path is used.
Then it prints out 0 0, and ends.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I'm a Junior at Marlboro High School, in Marlboro, NJ
=================================================================
============== 39 ====================== Zamboni_Racer =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Zamboni_Racer 0.0 (ERROR) 6.3 913/5747 0.0 (ERROR)
TIMES: a2b:599 graffiti:329 hand:599 TOTAL:1528_sec
=================
Zamboni_Racer submitted by Paul Banta at pbanta@hotmail.com
=================
++ Please summarize the algorithm used by Zamboni_Racer
Short Path:
In essence, I start at (0,0) and repeatedly move either E, SE, or S
(whichever is the smallest elevation gain). This gives me a fairly short
path that is guaranteed to be less than 2*size moves. I also start at
the other corner and repeatedly move either W, NW, or N (whichever is
the smallest elevation gain). This may give me a different path (in
reverse order) that is also guaranteed to be less than 2*size moves. I
pick the smaller of the two to be my short path. On the test board, the
path from (0,0) to (size-1,size-1) had a total elevation gain of 219
(209 was optimal), and the path from (size-1,size-1) to (0,0) had a
total elevation gain of 215.
Long Path:
I use a little graph stuff to reduce my choices. I start by building
trees (graphs) from the board. I sort all pairs of squares from highest
altitude difference to lowest altitude difference. From this ordered
list of pairs, I add connections. A connection is only made between two
squares if at least one of them isn't already connected to something.
This results in a number of trees that aren't connected to each other.
Next, I repeatedly connect leaves from different trees. Once one leaf is
connected to another leaf, neither are leaves any more. Now I have a
greatly reduced number of paths to choose from and I do a DFS traversal
until time runs out.
++ Do you have any good references to recommend?
Graph algorithms. The classics are Dijkstra, Kruskal, and Primm.
++ If I had it to do all over - here's what I would try ....
An idea that I had for the long path, but couldnt make it work. Start
with the long path being a strait line from one corner to the other.
Then, take the pair of squares that has the largest elevation difference
and try to add them to the path. Then, take the pair of squares that has
the next largest elevation difference and try to add THEM to your path.
Keep trying to add these pairs until all pairs have been tried. Some
pairs wont be added because theyll make the path too long.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Im a computer programmer for TRW in Colorado Springs, Colorado, USA.
For fun I play volleyball, go backpacking, camping, fishing, and hiking.
My innermost secret is Bozo.
=================================================================
============== 40 ====================== Cross_Country =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Cross_Country 1.3 3710/4976 1.4 647/913 2.0 1015/2015
TIMES: a2b:1 graffiti:1 hand:0 TOTAL:3_sec
=================
Cross_Country submitted by Andrew Gauld at andrew.gauld@att.com
=================
++ Please summarize the algorithm used by Cross_Country
Didn't have time to do a decent entry. This one just goes around the edge
of the square, either clockwise or counterclockwise, whichever yields the better
score.
++ If I had it to do all over - here's what I would try ....
Spend more time, do more research.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
AT&T. Lincroft. Programmer. Ski(Downhill). That would be telling. Nope.
=================================================================
============== 41 ====================== nomad =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
nomad 0.0 (ERROR) 1.9 479/913 2.7 373/1015
TIMES: a2b:3 graffiti:4 hand:2 TOTAL:10_sec
Sorry ... no description available for nomad
=================================================================
============== 42 ====================== Frost =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Frost 3.9 1576/6122 0.0 (ERROR) 0.0 (ERROR)
TIMES: a2b:1 graffiti:2 hand:1 TOTAL:4_sec
Sorry ... no description available for Frost
=================================================================
============== 43 ====================== bEEr_Run =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
bEEr_Run 1.1 3320/3710 0.1 4889/647 2.2 911/2015
TIMES: a2b:1 graffiti:2 hand:1 TOTAL:5_sec
=================
bEEr_Run submitted by Dennis Peter at dennis_p@hotmail.com
=================
++ Please summarize the algorithm used by bEEr_Run
Well, tonight or tomorrow night I plan to look 3-deep for the shortest
path using A*. On the way back, I look 2-deep for the longest path and
I will develop (hopefully) a nifty algorithm to use all the moves
allowed. If I find I'm struggling for time, I'll use a dead-simple
algorithm of looking at the adjacent squares (that get me closer to the
target square) and moving to the appropriate one according to whether
I'm going for a minimum or a maximum.
++ Do you have any good references to recommend?
Read lots of stuff on trees and A* searches. And a good C/C++
reference. The rec.games.programmer newsgroup is good, so is
comp.graphics.algorithms. There's hundreds of C/C++ references in the
Internet.
++ If I had it to do all over - here's what I would try ....
I would try to start sooner. Up to now, in total I think I spent 8
hours on the problem, of which 50% was trying to read that damn PGM
file. As for tomorrow, maybe another 2 hours or so. I'm a very busy
person.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I work for Intrinsyc Software Inc. (http://www.intrinsyc.com) in
beautiful Vancouver,BC Canada. I develop Windows CE applications. For
fun I like to hit bars and clubs and party. I like all sports and I'm
fairly athletic. POTM ideas? No searching problems, they're too
boring. No database problems either... too boring. Anything else is
OK.
L8r!
=================================================================
============== 44 ====================== LoopIt =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
LoopIt 0.9 3320/3018 0.9 4889/4389 1.2 911/1057
TIMES: a2b:0 graffiti:0 hand:0 TOTAL:0_sec
Sorry ... no description available for LoopIt
=================================================================
============== 45 ====================== Fit-O-Meter =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Fit-O-Meter 1.7 5162/8678 0.0 (TIME) 0.0 (TIME)
TIMES: a2b:255 graffiti:722 hand:723 TOTAL:1701_sec
=================
Fit-O-Meter submitted by M.Huys F.Vernaillen at mario.huys@barco.com
=================
++ Please summarize the algorithm used by Fit-O-Meter
Shortest path: flooding algorithm with cost determined solely by height
difference.
Longest path: Determine in each step which points can reach the end in
given number of steps. Choose that neighbour whose shortest path is the
most costly (also solely determined by height difference).
++ If I had it to do all over - here's what I would try ....
Try out a lot more ideas. We had plenty.
We were implementing Knuth's stratified longest path algorithm, but
failed in adding pathlength constraint (well, it was the last week
already, so maybe, with some slight adjustments...)
We had stratification plans for the shortest path (not only consider the
shortest path, but also the shortest path in a smaller number of steps).
this would avoid shortest winding path problems.
We wondered how a spider web would do (web points are attracted by
highest points, and pull along their neighbours). Could also be used to
reduce the height map to smaller map, only containing interesting
points.
We didn't implement timing constraints.
There are also genetic algorithms. At least there the survival criterium
could be the goal criterium: biggest long/short ratio.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Barco Graphics. Gent, Belgium. R&D Software Engineers. Programming ?
Keep it secret. The spider web has many possibilities; consider it...
This was just a warming up. Next contest, we'll be there from the
start... with company.
Mario Huys.
Frank Vernaillen.
=================================================================
============== 46 ====================== ScTour =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
ScTour 0.8 4720/3682 0.0 (TIME)
TIMES: a2b:527 hand:0 TOTAL:527_sec
Sorry ... no description available for ScTour
=================================================================
============== 47 ====================== vagabond =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
vagabond 0.0 (ERROR) 0.0 (ERROR) 0.0 (ERROR)
TIMES: a2b:4 graffiti:0 hand:0 TOTAL:5_sec
Sorry ... no description available for vagabond
=================================================================
============== 48 ====================== thereNback =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
thereNback 0.0 (TIME) 0.0 (TIME) 0.0 (TIME)
TIMES: a2b:723 graffiti:720 hand:721 TOTAL:2165_sec
=================
thereNback submitted by Ken Weinert at kenw@ihs.com
=================
++ Please summarize the algorithm used by thereNback
A normal shortest path algorithm followed by a "longest path"
(inverse of the shortest path) and then a check to see if we've made too
many steps. If we've made too many steps then determine the number we need
to cut out and then iterate over the longest path part to see if there are
loops that can be cut out. Remove the shortest of the loops that will leave
us the maximum number of steps.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Full time job: Information Handling Services
Consulting: Quarterflash Software Services
Location: Denver, CO, USA
Fun: Work on software for PBEM game, read, camp
Secret:
=================================================================
============== 49 ====================== crazy_walker =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
crazy_walker 0.0 (TIME) 0.0 (ERROR) 0.0 (TIME)
TIMES: a2b:735 graffiti:157 hand:736 TOTAL:1628_sec
=================
crazy_walker submitted by Georgios Papoutsis at
Georgios.Papoutsis@nws.e-technik.tu-muenchen.de
=================
++ Please summarize the algorithm used by crazy_walker
It first finds the best short path by iteratively computing
for each grid point which is the shortest path to that point using
n steps, for n=1,2,3....
a similar algorithm is used for the long path starting at the
lower right corner, but examining only paths with each step
going to one of the directions
and taking care, that no of the examined paths has
- or - sequence,
ensuring the 'no-point-visited-two-times'-rule. (That makes
the algorithm of a complexity O(^4) which means
it has no chances in the finals... it would be easier
to use just and steps, making it
just O(^2) but much worse (giving in the system
test a score of 14.6 instead of 27.7) which apparently have done
some of the other entries with the 14.6 score).
Actually I woulde like to combine this algorithm with finding
first some points in the grid, which are 'good' (having
large differences to their neighbours) and splitting the whole
path in many smaller, going through these points, and using
the above algorithm for these smaller paths, but I left
the programming for the last day, and so run out of time,
and left the old entry, with no chance to make something in
the finals (besides being so slow and memory consuming, it also
has a bug I found some time ago, which I didn't care to
correct, as that shouldn't be actually the final entry). I just
hope, the next time, I won't leave it to the last day... let's see...
++ Do you have any good references to recommend?
Any basic graph-theory / combinatorial optimization etc. book.
++ If I had it to do all over - here's what I would try ....
not leave the programming for the last day (maybe I'll try the
day before last next time :-) )
see the algorithm description above, for what I would try in
this problem.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Originally from Greece, now PhD student in electrical engineering
in the Munich University of Technology (Germany).
=================================================================
============== 50 ====================== bugsbunny =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
bugsbunny 0.0 (ERROR) 0.0 (TIME) 0.0 (TIME)
TIMES: a2b:220 graffiti:721 hand:722 TOTAL:1664_sec
=================
bugsbunny submitted by James Huang at jameshuang@att.com
=================
++ Please summarize the algorithm used by bugsbunny
// 1. No grid point is to be revisited in any way.
// 2. To facilitate code developing, the adjacent points
// of a gridpoint are assigned with adjacency IDs:
// 4 3 2
// \|/
// 5-0-1
// /|\
// 6 7 8
// 3. The optimal path with the minimal total vertical
// distance traveled is determined by applying the
// theory of Dynamic Programming, which is implemented
// with the repeated back-and-forth sweeps in order to
// catch all S-shaped optimal paths.
// 4. The return path to maximize the vertical distance
// traveled is constructed by linking certain selected
// gridpoints whose maximum altitude differences to the
// adjacent points are in the top percentiles. The way
// to link those selected gridpoints is mainly dependent
// of the number of steps remaining for the return path
// and thus its possible overall shape.
// 5. All linking paths between the selected gridpoints are
// determined by applying the theory of Dynamic Programming
// in order to maximize the vertical distance traveled on
// the parallelogram diagonally formed by the linking pair
// of two selected gridpoints.
++ Do you have any good references to recommend?
None. Ideas were generated by THE CPU atop my neck and between my ears ;-)
.
++ If I had it to do all over - here's what I would try ....
I will try to spend more time on it. Due to my real work for AT&T, I
started the current POTM with less than 2 weeks before the deadline.
Then we had to move from Middletown Center to Lincroft Center.
Amid packing and unpacking, not to mention loss of network
connection, I had a total of less than 5 days for programming and testing.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Working for AT&T at its NJ Lincroft R&D Center as a computer programmer.
Besides for fun, doing this POTM was also for keeping my C/C++ skill
current. I haven't gotten a chance to do serious C/C++ programming
since I joined AT&T about one year ago --- I have been working on
Web and NT platform since then (I really miss those UNIX
workstations :-( ). It took me a while to find a UNIX
machine with C++ compiler and adjust my programming style to it.
INNERMOST SECRET: Hope the UNIX can rejuvenate herself and hold on against
the all-out assault by the NT.
=================================================================
============== 51 ====================== TopoTour =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
TopoTour 0.0 (TIME) 0.0 (TIME) 0.0 (TIME)
TIMES: a2b:737 graffiti:721 hand:736 TOTAL:2195_sec
=================
TopoTour submitted by Bill White at bwhite@utsi.edu
=================
++ Please summarize the algorithm used by TopoTour
TopoTour builds a connected graph from the altitude points in the PGM file
by creating edges for each altitude difference in the eight possible
directions. The "short" path uses Dijkstra's algorithm to find the
shortest, least-cost path to the opposite corner. The "long" path inverts
the edges by subtracting the edge value from the max altitude. The same
Dijkstra algorithm is applied to the inverted graph. This is obviously not
optimal, as the path becomes shortest path, highest cost. A more dynamic
algorithm is needed to optimize the number of moves left after the "short"
path.
++ Do you have any good references to recommend?
"Discrete Mathematical Structures", Gersting.
++ If I had it to do all over - here's what I would try ....
A more dynamic return path algorithm that uses the remaining moves more
effectively.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I'm currently a graduate reesarch assistant pursuing a master's degree in
computer science from the University of Tennesse Space Institute. My thesis
focus is on parallel programming using a network of DSP/FPGA chips and the
Message Passing Interface (MPI) standard. Being a hacker (in the old MIT
sense of the word), I enjoy probing the depths of *NIX systems,
particularly Linux and all it's accoutrements.
=================================================================
============== 52 ====================== Tired_Mouse =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Tired_Mouse 0.0 (TIME) 0.0 (TIME) 0.0 (TIME)
TIMES: a2b:727 graffiti:742 hand:721 TOTAL:2192_sec
Sorry ... no description available for Tired_Mouse
=================================================================
============== 53 ====================== Soujourner =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Soujourner 0.0 (ERROR) 0.0 (ERROR) 0.0 (ERROR)
TIMES: a2b:439 graffiti:527 hand:486 TOTAL:1453_sec
=================
Soujourner submitted by Nico Verboven at nverbove@eps.agfa.be
=================
++ Please summarize the algorithm used by Soujourner
The way I looked at the problem there were two problems. Find a path
with a low cost and a path with an high cost. The first problem I
attacked using the well known A* search algorithm. The algorithm
will remove paths that lead to the same node with an higher cost,
and also limits the search space when it grows to big. Also an estimated
distance o destination is calculated. Paths that cannot reach the target
within this distance are removed also.
For the longest path I took an different approach. It's a depth first search
algorithm recursively implemented. It follows the direction that has the
highest cost(= height diff.). When the iteration depth grows to deep,
the algorithm will jump back a numer of iterations to try a different
path. The longest path algo. will keep looking for somewhat less
than the remaining time. After that the
longest path will be improved with heuristics. With that I mean that
every node of the path is examined to see that if it is possible to
reach the next node through another neighbouring node and
increasing the cost. (if we have spare nodes available).
Another heuristic is try to replace the node b in the subpath a-b-c
with another node a-d-c such that the cost (a,d) + cost (d,c)
is greater than the cost(a,b) + cost(b,c). This works quite well in
practice.
++ Do you have any good references to recommend?
Try this URL:
http://www-cs-students.stanford.edu/~amitp/gameprog.html#Paths
++ If I had it to do all over - here's what I would try ....
To improve my longest path path algorithm. It will give a good result,
but there can be improved a lot.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I work for AGFA Gevaert N.V.
AGFA has its headquarter in
SepteStraat
Mortsel
Belgium
I am an Adjunct ProjectManager and work on applications for digital imaging.
I program for fun, that's why I joined POTM. I always had a special interest
in AI.
Keep up the good work!
=================================================================
============== 54 ====================== Skeptik_Trekker =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Skeptik_Trekker 0.0 (ERROR) 0.0 (ERROR) 0.0 (ERROR)
TIMES: a2b:0 graffiti:0 hand:0 TOTAL:1_sec
Sorry ... no description available for Skeptik_Trekker
=================================================================
============== 55 ====================== Sherpan_Holiday =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Sherpan_Holiday 0.0 (ERROR) 0.0 (ERROR) 0.0 (ERROR)
TIMES: a2b:2 graffiti:3 hand:1 TOTAL:7_sec
Sorry ... no description available for Sherpan_Holiday
=================================================================
============== 56 ====================== Quantum_Rambler =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Quantum_Rambler 0.0 (ERROR) 0.0 (ERROR) 0.0 (ERROR)
TIMES: a2b:1 graffiti:1 hand:0 TOTAL:3_sec
=================
Quantum_Rambler submitted by Joshua Huntington at joshua@yellowmagic.com
=================
++ Please summarize the algorithm used by Quantum_Rambler
Quantum Rambler recursively attempts all possible sets of X moves and
then chooses the best one for the appropriate leg of the journey. It
then backtracks to X-N moves and repeats the process. Each pathlet is
scored based on changes in altitude and distance from goal.
Additionally, for the "long" leg Quantum Rambler it not only tries to
maximize the distance traveled but there is extra code to alternate
between high and low points in subsequent moves. This little fact
made a lot of difference in the test run. Version 2 (which I was too
lazy finish and submit) was going to cycle through the different
values for X and N. Version one has these values hard coded at X=5
N=3 for the short leg and X=3 N=0 for the long leg.
++ If I had it to do all over - here's what I would try ....
If I had to do it all over again I think I would try to make an array
of 1000 paths and after adding a point to each path sort them based on
distance, weeding out the worst ones and using the best ones as
parents for the next batch.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I'm a software developer for Yellow Pages composition programs. I
work in Temecula, CA. I enjoy writing, roller skating, travel, movies
and problems like this.
=================================================================
============== 57 ====================== PhlatTier =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
PhlatTier 0.0 (ERROR) 0.0 (ERROR) 0.0 (ERROR)
TIMES: a2b:5 graffiti:7 hand:3 TOTAL:16_sec
=================
PhlatTier submitted by Robert Creager at Robert_Creager@Mindless.com
=================
++ Please summarize the algorithm used by PhlatTier
Pick the shortest/longest step from the current location. Doesn't
check for multiple uses of a step. First pass algorithm. Wife went
into pre-term labor (at 29 weeks) and didn't make the time to go any
further.
++ Do you have any good references to recommend?
Nope.
++ If I had it to do all over - here's what I would try ....
To get more time!
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
StorageTek - Louisville, CO - Embedded software engineer - Sleep - I
don't know them, too secret - Maybe?
=================================================================
============== 58 ====================== PathFinder =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
PathFinder 0.0 (TIME) 0.0 (TIME) 0.0 (TIME)
TIMES: a2b:723 graffiti:724 hand:725 TOTAL:2172_sec
Sorry ... no description available for PathFinder
=================================================================
============== 59 ====================== OREO =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
OREO 0.0 (TIME) 0.0 (TIME) 0.0 (TIME)
TIMES: a2b:723 graffiti:721 hand:723 TOTAL:2168_sec
=================
OREO submitted by Doug VanNatter at dvannatt@bellsouth.net
=================
++ Please summarize the algorithm used by OREO
Look recursively at all the possible moves from the current location (5 or 6
deep) select the best choice. Repeat this process until the "best" path is
found. Essentially the same thing is done for the reverse trip, but
different code is used to determine what is "best". Illegal moves are
filtered out in both cases. Inefficient moves (moves next to a previous
location) are filtered out in both cases.
++ Do you have any good references to recommend?
No.
++ If I had it to do all over - here's what I would try ....
First a simple change. I noticed that I wasn't always using up all my
allocated moves. Go back through the return trip of the path and when a
diagonal move was taken and an "L" shape move could have been made, insert
the extra move. Continue to do this until all extra moves have been used.
Second, A different algorythm for the trip back. Start with trying to find
the most direct path (straight diagonol line unless some of the moves are
blocked). Save this path and it's "value". Then search the "board" for the
highest and lowest elevations. Create a "direct" path to the highest, then
to the lowest, then to the upper left corner. Assuming success, compare to
the previously saved value. Save the better one. See if there is sufficient
time for more attempts. If so, add the next highest and next lowest spots
and repeat.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
BellSouth
Birmingham, AL
Architecture Specialist
=================================================================
============== 60 ====================== MunroBagger =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
MunroBagger 0.0 (ERROR) 0.0 (ERROR) 0.0 (ERROR)
TIMES: a2b:3 graffiti:5 hand:3 TOTAL:11_sec
Sorry ... no description available for MunroBagger
=================================================================
============== 61 ====================== LongRoad =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
LongRoad 0.0 (ERROR) 0.0 (ERROR) 0.0 (ERROR)
TIMES: a2b:3 graffiti:2 hand:2 TOTAL:8_sec
Sorry ... no description available for LongRoad
=================================================================
============== 62 ====================== GAS =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
GAS 0.0 (ERROR) 0.0 (ERROR) 0.0 (ERROR)
TIMES: a2b:1 graffiti:1 hand:0 TOTAL:3_sec
=================
GAS submitted by Arcadiy Gilinskiy at gas@intbank.yaroslavl.su
=================
++ Please summarize the algorithm used by GAS
I split the problem onto 2 small tasks.
T1) Find the minimum path
T2) Find the max back path
Solution T1:
I look ahead in directions E-E,E-SE,SE-E,SE-SE,SE-S,S-SE,S-S.
and choose the smallest one from this sums. After this I move
the current position in 1 position.
e.g.
sum E-E = 140
sum E-SE = 110
sum SE-E = 130
sum SE-SE = 115
sum SE-S = 112
sum S-SE = 102
sum S-S = 110
In this case current position moves in 1 position in South direction
and loop this process.
If current positon is on East or South the edge of table we must
look in the other direction ,
In South edge we must look in the S-S,S-SW,SW-S
In East edge we must look in the E-E,E-NE,NE-E
Solution T2:
From current point:
I find the max-min point (0 or maxalt),
calculate the sum that I can get if I go to this point,
calculate the C= sum/cnt (where sum - the path sum, cnt - the number of
moves from current point to this max-min point) and choose
the maximum of C and going to the corresposding max-min point and so on.
++ Do you have any good references to recommend?
I don't read the special mathematical books because I hadn't have enouth
time, but in this case IMHO this is strongly necessary.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Company : Bank
Location : Russia, Yaroslavl
Job : FoxPro programmer
POTM Ideas : Create mirror in Russia !!!!
P.S.
Sorry for my bad English and complex (intricate) description!
=================================================================
============== 63 ====================== Colorado_Dragon =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Colorado_Dragon 0.0 (TIME) 0.0 (TIME) 0.0 (TIME)
TIMES: a2b:724 graffiti:722 hand:724 TOTAL:2171_sec
Sorry ... no description available for Colorado_Dragon
=================================================================
============== 64 ====================== ClimbEveryMountain =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
ClimbEveryMountain 0.0 (ERROR) 0.0 (ERROR) 0.0 (ERROR)
TIMES: a2b:1 graffiti:2 hand:1 TOTAL:5_sec
=================
ClimbEveryMountain submitted by Joe Vollbrecht at jvollbrecht@att.com
=================
++ Please summarize the algorithm used by ClimbEveryMountain
select the 'cheapest' (closest to end-point) square on a nearly
direct line to get there, select the most expensive (farthest from
end-point) on a less direct path back.
++ If I had it to do all over - here's what I would try ....
to find more time to actually do it. I had some presumably good
ideas to improve the program, but no time to implement.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
AT&T, Kansas City. I have children, fun is over.
=================================================================
============== 65 ====================== BoringMoves =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
BoringMoves 0.0 (TIME) 0.0 (TIME) 0.0 (TIME)
TIMES: a2b:722 graffiti:742 hand:677 TOTAL:2142_sec
=================
BoringMoves submitted by Ong Chin_Kiat at kiat@rocketmail.com
=================
++ Please summarize the algorithm used by BoringMoves
Standard Dynamic Programming algorithm for both forward and return
path. Return path optimises fewest steps with biggest vertical climb.
Very standard, boring solution, that's why its called BoringMoves. I
entered early with this first version, and is supposed to upgrade it
(so that the algorithm makes full use of the allowed number of steps,
etc. etc). But the contest ended before I could find time to do it.
++ If I had it to do all over - here's what I would try ....
resist the temptation to enter the contest. :P
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
doing my post-graduate in NTU, Singapore.
=================================================================
============== 66 ====================== Blues_Traveller =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Blues_Traveller 0.0 (TIME) 0.0 (TIME) 0.0 (TIME)
TIMES: a2b:721 graffiti:720 hand:689 TOTAL:2131_sec
Sorry ... no description available for Blues_Traveller
=================================================================
============== 67 ====================== Blind_Ambition =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Blind_Ambition 0.0 (TIME) 0.0 (TIME) 0.0 (TIME)
TIMES: a2b:0 graffiti:0 hand:0 TOTAL:0_sec
=================
Blind_Ambition submitted by Eric Prestemon at ecp@io.com
=================
++ Please summarize the algorithm used by Blind_Ambition
The best short path is found, and then the best long path is found
with the remaining length available. This is a naive strategy that won't
survive on tricky grids.
The short path is found simply by keeping track of the current shortest
path to each square. All squares are looped over and their current
shortest path is updated. If any are updated, it loops again.
The long path is found by creating the most direct path between the start
and end, and then repeatedly randomly taking out a piece, picking a new
point nearby and replacing the removed section with a path through that
point. If the new path is better and not too many steps, it becomes
the new current path. This is repeated until time is almost up.
A slight improvement was to update the path even if it was worse (within a
certain range). This allowed more variation in the path and more things
tried.
++ Do you have any good references to recommend?
I wish. I thought about the problem without outside input, really.
++ If I had it to do all over - here's what I would try ....
Working out my algorithm in perl was good.
Not having time to rewrite it in C wasn't as good.
There's actually an algorithm I've tried that can find all the best
short-leg paths, with tradeoffs of height variation vs steps used, that's
just about as long in execution time as the much less useful algorithm I
used.
Combining this set of paths that trade off score and steps with a good
heuristic for quickly generating a long path (which I couldn't come up
with) would probably be the best way to handle "tricky" grids in a
reasonable amount of time.
Depending on how "tricky" the 3 test grids turn out to be, this could even
have been a winning strategy.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I live in Mountain View, CA and I'm sort of a maintenance programmer,
having moved into programming from full-time sysadmin/internet stuff.
I love puzzles/challenges. I just wish I'd had time to give full effort on
this one. It was a fun first effort. I'm anxious to start on the next
contest!
=================================================================
============== 68 ====================== Aimless =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
Aimless 0.0 (ERROR) 0.0 (TIME) 0.0 (TIME)
TIMES: a2b:248 graffiti:738 hand:724 TOTAL:1711_sec
=================
Aimless submitted by Kevin Williams at lorikevn@aol.com
=================
++ Please summarize the algorithm used by Aimless
Very simple. Just pick the best route segments (given a few constraints)
until we reach our out-bound destination. Then change the criteria
and do it again. After we're done, try to make local
improvements until we max out the path length.
++ Do you have any good references to recommend?
I always look forward to Beckett's Hockey Card Monthly and their annual
Alphabetical Price Guide.
++ If I had it to do all over - here's what I would try ....
Take a longer break between consulting contracts and devote more time to the
POTM. Of course, my wife has other priorities...
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Company: Self-employed.
Location: Currently in Omaha.
Job: MVS Systems Programmer-for-hire.
Fun: Fly, bowl, bike (tandem), collect hockey cards.
Secret: My clients secretly support GIMPS, the Great Internet Mersenne Prime
Search (www.mersenne.org) with their unused PC CPU cycles.
POTM Ideas: Solving logic problems
=================================================================
============== 69 ====================== 2path =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
2path 0.0 (TIME) 0.0 (TIME) 0.0 (TIME)
TIMES: a2b:722 graffiti:734 hand:739 TOTAL:2196_sec
=================
2path submitted by Igor Volkov at volkov@im.bas-net.by
=================
++ Please summarize the algorithm used by 2path
1) Using Dijkstra algorithm for the 1st part of path
2) Finding any back path for the rest moves
3) Using 2-exchanges for the back path.
++ Do you have any good references to recommend?
Article "Empirical analysis of heuristics" by B.L.Golden (Chapter 7
of the book "The Travelling Salesman Problem" Editied by E.L.Lawer, ...,
1985, John Wiley & Sons, Ltd.)
++ If I had it to do all over - here's what I would try ....
realize Dijkstra algorithm using heaps.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Institute of Mathematics, Minsk, Belarus.
=================================================================
============== 70 ====================== 2nd_Bounce =============
=================================================================
a2b graffiti hand
ENTRY Ratio min/max Ratio min/max Ratio min/max
================== ===== ========= ===== ========== ===== ==========
2nd_Bounce 0.0 (ERROR) 0.0 (ERROR) 0.0 (ERROR)
TIMES: a2b:0 graffiti:0 hand:0 TOTAL:1_sec
Sorry ... no description available for 2nd_Bounce
=================================================================