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 http://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 =================================================================