======================================= Spelunker ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Spelunker 23084 3645 1771 5768/942 8320/1316 8996/1387 =Andre Wilhelmus ================= Spelunker was submitted by =Andre Wilhelmus at awilhelm@hvsca01.nl.lucent.com ================= HOW DID Spelunker approach the task? Special tricks? It reads the building. Every room (node) has an array of pointers for the available directions (edges). Every direction (edge) has pointers to the next and the previous room (nodes). This is done to get rid of those 3D array indices. Attempts alternate between ns and sn as initial path. For every room in the path, it looks for an adjacent room which is not in the path. The next room in the path should have unused directions because the path extension must end in that room. This strategy prevents removing a part of the existing path and wasting time to check if the new extension path is longer than the path to be removed. The adjacent room which is not in the path is put in a list and a width first search, I think (I should really add more comments to my program,) is used to find its way back to the path. The search prefers directions to rooms with the least number of free directions with the least number of free directions. Directions with an equal score are chosen randomly to allow multiple attempts. When no more extensions can be added, the above procedure is repeated again using the current path but now the end of the extension path is allowed to be anywhere in the current path. The new extension path should be longer than the path to be removed. DID Spelunker iterate in any way? How did it know it was done? It tries multiple attempts until time runs out. The path with the highest number of rooms and the highest number of ups is kept (the number of ups is ignored during path search.) ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? A good evaluation function is very important as well as finding out why the largest building could not even be completed within 10 minutes (an earlier Spelunker version.) For debugging, the path is checked against the building to see if the path is correct. This did not help me when the largest building was up because the input was not fully checked and whole outer walls disappeared because of a bug. WHAT DO YOU DO FOR A LIVING? Writing/maintaining C++/C/Fortran programs. FOR FUN? Learning to write Hiragana. Playing Day of the Tentacle / Maniac Mansion on my Mac. INNERMOST SECRET? Bishoujo Senshi... ^_^ POTM IDEAS? Nope. ================================================================= ======================================= stalker ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR stalker 22862 4612 1398 5732/911 8212/1547 8918/2154 Mihai Badoiu ================= stalker was submitted by Mihai Badoiu at mihaib@lbi.sfos.ro ================= HOW DID stalker approach the task? Special tricks? Stalker is using some backtracking techniques combined with some heuristics. Stalker is trying to maximize a cycle "E->A->B->E" by finding another path from A to B (A->B) bigger than the current one using only building squares that have not been used. Example: ########### ##### # E ### ## ########### The initial cycle is "NS", "SN" or "EW".: Initial cycle (NS): ########### 1 ##### # 2 ### ## ########### After first maximize(NESW): ########### 12 ##### # 43 ### ## ########### After the second maximize(NESSWN): ########### 12 ##### # 63 ### 54 ## ########### A possible maximize: ########### 123##### # 8 4 ### 765 ## ########### ... and so on. The A->B path is founded using some backtracking techniques. To find a better path I used some heuristics: the backtrack function is trying first the neighbor squares that have 1 neighbor then 2 neighbors, 3,4 and at last 5 neighbors. When a square is selected in the path it became inactive, so we have to decrease the number of neighbors of its neighbors. Stalker maximize the cycle while there are A->B paths. DID stalker iterate in any way? How did it know it was done? Stalker is a nice program. I hope not to run out of time! WHAT DO YOU DO FOR A LIVING? I am currently a student at Computer Science High School of Bucharest. I am also working as a programmer at a small software firm in Bucharest named "CERTEH S.R.L." FOR FUN? I like sports very much. In my free time I play basket-ball, soccer and volley-ball. I like reading and watching SF movies. STARTREK is one of my favorite movies because of its modern equipment and treating future problems. I like listening to rock and classic music as well. INNERMOST SECRET? "For tomorrow may rain, so I'll follow the sun." ================================================================= ======================================= mowing3D ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR mowing3D 22564 2410 1408 5636/696 8018/965 8910/749 Bob Hall ================= mowing3D was submitted by Bob Hall at hall@research.att.com ================= HOW DID mowing3D approach the task? Special tricks? Mowing3D uses depth-first search (DFS) as its fundamental primitive operation. It starts out by finding any cycle (using DFS) starting/ending at E. It then walks along the current cycle a step at a time. At each step S it uses DFS to try to find a "side trip" that re-enters the path somewhere (call it F) such that if we replace the segment from S to F along the cycle with the side trip from S to F we get a longer cycle. It then just keeps on trying this, always lengthening the cycle, until it can't find any way to lengthen it. Now, there is the question of in what order does the DFS search examine neighbors of a node. That is, does it look up/down/east/west/north/south first, what next, etc. Mowing3D simply tries the procedure described in paragraph 1 above 720 (=6!) times, once per each choice of fixed preference order. That is, the first time it might try prefering neighbors in the order "UNEWSD" and then rotate through all 720 permutations of those six letters. Of course, I have to have code to stop myself after 10 minutes if necessary, possibly before having examined all the permutations. Therefore, I examine the orders in a "fair" way (with respect to the 3-space symmetries) so that I'm not biased into only examing a few general directions. DID mowing3D iterate in any way? How did it know it was done? As described above, it iterated two ways: first in going through the 720 permutations of "UNEWSD" and within each of those, it iteratively improved the path by looking for extending side trips. It knew it was done by either getting through all 720 permutations or by 10 minutes being up. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? * Research in agents, artificial intelligence, and software engineering. * Fun? what's that? * POTM idea: how about competitive "Connect Four" playing programs? (Connect Four is a tic-tac-toe-like game played on a 6x7 grid. Each move consists of dropping your token in at the top of a column. It ends up placed at the lowest unoccupied row. The first player to get four in a row wins. Their are many variations: varying the dimensions of the grid or the number in-a-row required to win; also, allowing the forming or a 2x2 box or 3x1 L to win as well, etc.) ================================================================= ======================================= sundew ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR sundew 22246 4194 1477 5600/584 7886/952 8760/2658 =Fred Hicinbothem ================= sundew was submitted by =Fred Hicinbothem at fah@potm.ffast.att.com ================= HOW DID sundew approach the task? Special tricks? SUNDEW (South/Up/North/Down/East/West) starts at the main entrance and goes about the building making moves in priority order based on a priority array containing the six possible moves in some specific order. If it can make move ONE, it does - if not, then it proceeds to make move TWO, etc. If it cannot make ANY move, it backs up and doesn't tread on that particular "dead end" again. Eventually, it will either find the way back to the enter square or (in a case which is not allowed) mark everything as a dead end. THEN ... walk the path and look for an adjacent pair of squares that can be added to the path somewhere in the middle ... and keep adding pairs until there are no more to add. DID sundew iterate in any way? How did it know it was done? The difficulty was in choosing the CORRECT sex-tuple of priorities since some worked better than others in different buildings. So, since I had the time I tried all six factorial of them and kept track of which one scored best! I checked the time just in case and tried to order the sex-tuples to try the "most beneficial" first. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? Submit early to get the porting compilation bugs resolved ... WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? Systems Engineer (whatever that is) for AT&T ... this is my fun ... I need a life ... stay tuned! ================================================================= ======================================= Ripple ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Ripple 22016 3694 1788 5464/940 7768/1257 8784/1497 Emerald Chung ================= Ripple was submitted by Emerald Chung at emerald@research.att.com ================= HOW DID Ripple approach the task? Special tricks? Ripple creates an undirected graph out of the building. The vertices represent spaces in the building. An edge connects two vertices if the spaces are next to each other. As its name, Ripple starts from a small cycle (for instance, sn) then gradually expands the cycle. The cycle is traversed by pair in a depth-first order. Each time, a vertex and its next vertex in the cycle are examined. The shortest path (not going through any vertex already in the cycle) between these two vertices, if exists, is inserted into the cycle. DID Ripple iterate in any way? How did it know it was done? Since each vertex may have more than one neighbors, their order in the data structure can be permuted to generate different results. Ripple iterates on neighbor permutations. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? I am working at Bell Labs, distributed software research department. I am also a mother of two boys, 6 and 3. ================================================================= ======================================= Harley_Hamilton ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Harley_Hamilton 21948 5871 1568 5330/1158 7772/1777 8846/2936 =Chad Hurwitz ================= Harley_Hamilton was submitted by =Chad Hurwitz at churritz@cts.com ================= HOW DID Harley_Hamilton approach the task? Special tricks? It computes a 1-tree of all the verticies, and then adjusted the other than 2-degree nodes accordingly to jimmy them into being 2-degree nodes. (note: if all verticies are of two degree in a 1-tree you have a hamiltonian cycle, and a not so bad score.) There were also weights put on flat edges so they would be less likely (than vertical edges) to be chosen in the 1-tree. After the 1-tree was adjusted or trained a good amount, I tried to open up the small cycle in the 1-tree to become larger by finding edges that connected between 1-tree branches. DID Harley_Hamilton iterate in any way? How did it know it was done? yes, if it could, it trained the one-tree and then tried to find a tour, if it could do this more than once with some randomity and additional training within the time limit, it did. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? why would people not wash? it's really simple you just get in the shower (or bath if your prefer) and turn on the water. be sure to get behind both ears, if your ankles can go that far. actually i shouldn't talk... just don't procrastinate, it's the root of all evil, see what it's doing to me? WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? stuff, more stuff, some stuff again, the POTM master should import this info from previous answers. ================================================================= ======================================= I_want_a_guide ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR I_want_a_guide 21468 3392 1665 5144/900 7972/1216 8352/1276 Kurt VandenBranden ================= I_want_a_guide by Kurt VandenBranden at kvd2@bipsy.se.bel.alcatel.be ================= HOW DID I_want_a_guide approach the task? Special tricks? step 1. find any path through the building Starting from the start-position, I just go from position to position, until I am back at the start. If the path is too short when I get back to the start, or when there is no path back to the start, I use backtracking to try it some other way. How to decide what will be the next step: Every position in the building has a number assigned to it. This number is the number of free positions reachable from this position. I always go to the adjacent position with the lowest number assigned to it. This way, I always take the position first that is the more difficult to reach. step 2. try to make the path as long as possible This step is not easy to explain. example: If the path I already found contains a 'north', I try to replace this with: east - north - west or west - north - east or up - north - down or down - north - up if the corresponding positions are still free. You have to try to understand this graphically, it's like trying to put a bump on the existing path. This procedure is tried until the path has reached maximum length, and then you have the finished path. DID I_want_a_guide iterate in any way? How did it know it was done? Yes, I just keep searching for new solutions until I'm almost out of time. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? I'm impressed with the speed of PERL. I thought I wouldn't have a chance against all the C- and C++ programs, but I think I did reasonably well. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? work: I'm a software-ingineer at a big telecommunications firm fun: running Linux on my PC at home, juggling, reading SF thanks Fred, for organising the POTM, I loved competing in it. ================================================================= ======================================= Get_Back ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Get_Back 21302 5672 595 5116/1235 7642/1791 8544/2646 Tim Ruhl ================= Get_Back was submitted by Tim Ruhl at tim@cs.vu.nl ================= HOW DID Get_Back approach the task? Special tricks? I first generate a distance table that shows the shortest distance from a point to the exit. This table is used for a heuristic to find an initial path. Every step tries to go to the point that has the longest minimal path back. After each step a check is made whether it is still possible to get back to the exit. This gives an initial legal path. DID Get_Back iterate in any way? How did it know it was done? After the initial path is found, a check is made whether the path has somewhere a point as neighbor that is not reached in the current best path. If so, this unreached point is made part of the path that reached it and the same search strategy as described above is applied. Search stops when no improvements can be found by going to an unreached point from the current best path. An alarm signal is used to stay within the time limit. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? After every step a check is made whether the exit can still be reached (that's why it is called get back). This search uses a heuristic based on the distance table and a heap to sort all possible moves. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? I'm a PhD student at the Vrije Universiteit Amsterdam. I'm working on parallel programming (the Orca parallel programming language, the Panda portability platform). ================================================================= ======================================= Willie_Wundes ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Willie_Wundes 21290 4123 1374 5196/703 7594/1196 8500/2224 Dave Peterson ================= Willie_Wundes was submitted by Dave Peterson at dpeterso@isd.net ================= HOW DID Willie_Wundes approach the task? Brute force with simple bad route elimination. Special tricks? Got better results with room/wall weights. DID Willie_Wundes iterate in any way? Tried all six opening/ending rooms and all 720 direction orderings. How did it know it was done? Either all possible methods tried, or timed out. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? I came up with the name Willie_Wundes from "Death of a Salesman". Wundes is a dialect variation on wonders, using the six directions. (This contest is a Hamilton Path. The Traveling Salesman Problem is a subset of the Hamilton Path Problem.) WHAT DO YOU DO FOR A LIVING? Programmer level V for Applied Systems, Inc. FOR FUN? Surf the Internet! INNERMOST SECRET? More time to work on the latest POTM. ================================================================= ======================================= antFarm ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR antFarm 21170 4478 1802 5162/1099 7756/1492 8252/1887 Glenn Bradford ================= antFarm was submitted by Glenn Bradford at gmb@sarts.att.com ================= HOW DID antFarm approach the task? Special tricks? From the entrance, antFarm generally goes east and then slices up and down thru the building as it works its way back west and out the exit. At any given room, an evaluation function decides which direction to move next. The function scores higher for the directions taken which are more constraining (have neighboring rooms which are unenterable or have been already entered). This strategy helps avoid creating pockets of unvisited rooms. In the event of ties, east moves are favored followed by up and down moves. On floors which have at least 30% fewer empty rooms than the average empty rooms per floor, scores for going up and down are boosted. Conversely, on floors which have at least 30% more empty rooms than the average empty rooms per floor, scores for going east, west, north, and south are boosted. A chunk of time during antFarm's run is devoted to a more "aggressive go east" strategy. In it, the evaluation score for moving east is artificially boosted, while the score for moving west is artificially diminished. antFarm keeps track of how many times an attempt is made to visit a room, and if these attempts cross a threshold, it considers the room unenterable. This is a method to shortcircuit the search in parts of a building where you might be trapped. These counts are initialized when a path has been backed up to a fairly short length (see below). DID antFarm iterate in any way? How did it know it was done? Depth first search, but if a better soln is not found within a time limit, the recursion "backs out" to a shorter part of the path and then restarts the search from there, hoping to find a more fruitful soln. A switch to the "aggressive go east" stragegy occurs after the "back out". Usually knew it was done by hitting the 600 second time limit. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? I do software development in Network Systems at Lucent Technologies. ================================================================= ======================================= son_of_Sot ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR son_of_Sot 20734 5962 1770 4980/1051 7630/2052 8124/2859 Bob Ashenfelter ================= son_of_Sot was submitted by Bob Ashenfelter at ash@att.com ================= HOW DID son_of_Sot approach the task? Special tricks? There are four solver routines and one improver routine. The solvers are called "deterministic", "random", "semi-deterministic", and "semi-random". Each starts at the entrance and repeatedly picks one of the available moves until it gets back to the entrance. Whenever they get into a dead end (no available moves), they call routine "unmove()" which backs out one move and leaves the vacated space marked so it won't be visited again. The "deterministic" solver always picks the UP move if it is available, then DOWN, EAST, NORTH, SOUTH, and WEST in that order. The "random" solver of course picks randomly from the available moves. The other two solvers are in between, favoring UPs and DOWNs with some degree of randomness. The improver routine takes a pre-existing solution and goes through all the moves looking for situations where there are two unvisited spaces adjacent to the path that it can add to the solution. DID son_of_Sot iterate in any way? How did it know it was done? Yes. The "deterministic" solver is called only once because it always gets the same solution. But the other solvers generate different solutions each time they are called and so they are run over and over, hoping that they will stumble on ever-better solutions. Only the best solution is saved. There are two ways that it knew it was done. One was a time limit, set at 590 seconds. The other was if it had found a best-possible solution. When the building was first read in, the maximum number of moves was computed by counting the empty spaces (plus "E") and rounding down to an even number. The maximum number of UP moves was computed by counting the number of empty spaces with an empty space one floor below and dividing by 2. Whenever a solution with these maximums is found, the program takes an early exit. I didn't really expect this to get used, but it turns out that the "determin- istic" solver gets an optimum solution for the large empty building that was used as a system test. (Actually, the version Fred had at the time didn't have this feature--it had a very short time limit instead.) Once the time limit expires, the improver routine is called to try and improve the previously-best solution. Since one pass of the improver may open up new opportunities for improvement, the improver is run over and over until there is no more improvement. Then it prints out the solution. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? When this problem first came out, I thought there might be a way that it would be similar to the previous POTM, KNIGHTCRAWLER. Hence the name "son_of_Sot", after the name of my previous entry, "Sir_Sot". In the end, I never did find much of a connection, although the overall structure of the two programs is similar. I must confess to not having tried hard enough on this problem. When it first came out, I worked on it some for a couple of weeks, then did nothing for two months. Then I submitted an old program as a new entry because it aced the empty building. Another month passed. Finally, at 6 p.m. on the very last day, I started work on the improver routine. This improved my final standing from moderately poor to moderately good, but I didn't really consider my final entry to be competitive. Here are several of ideas I thought about, but didn't implement. Originally, I thought it would be very important to detect and block off all "dead ends", otherwise a lot of time would be wasted generating moves that would eventually have to be removed. I never did come up with an algorithm for determining which spaces were "dead" and in the end I convin- ced myself that it really wasn't all that important. My improver is good at picking up pairs of empty spaces, but it can never do anything with isolated empty spaces. I needed a routine to migrate such orphans together so the improver could take them. The high-level control of this program needs improvement, but I didn't take the time to do anything about it. Probably I could have moved up a couple of notches in the standings if I had applied the tools I developed more intelligently. Finally, I will leave you with the design of a building so fiendishly devious that I didn't mention it to Fred lest he should use it since my program is not designed to cope with it. Consider a large building that is divided into a large number (several hundred) small closed rooms. Now make exactly two openings in the walls (or floors) of each room such that they are all strung together like beads on a necklace. It would be fairly easy to generate a decent solution to this configuration. Do so, and save it. Finally, add no more than one additional opening to each room so that additional pairs of rooms are connected, creating short circuits in the string of rooms. Consider your choices as you enter each room. There are only two ways out since you have already used up the third getting in. If you choose the wrong exit you will have cut off access to all the short- circuited rooms. Sure, you can enter them, but sooner or later you will run into a dead end and have to back out. With hundreds of binary choices to make, the chance of finding the one true path is astronomically small. And yet you already have found and stored a good solution, you just can't find it once all those extra options are available! One more thing... Son_of_Sot found the most UP moves. I want my YO-YO. >>> POTM-MASTER NOTE: BOB HAS BEEN AWARDED THE YO-YO ... MY ERROR!!! WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? Circuit design. Bicycling, sailing, grow orchids, travel. No way... Nothing new, but I would like to say that I enjoyed the fact that this problem was not too similar to the previous ones. There have been too many POTMs which involved a two-dimensional square array of some kind. This one was three-dimensional. Perhaps we can look forward to N dimensions! ================================================================= ======================================= Witless ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Witless 20716 3900 1154 5408/700 7152/1449 8156/1751 Alex Popiel ================= Witless was submitted by Alex Popiel at popiel@nag.cs.colorado.edu ================= HOW DID Witless approach the task? Special tricks? Immediately after reading the board, Witless did some annoyingly complex graph theory (identification of bi-connected components) to simplify the playing field, and calculate gross maxima for the maximum number of steps/ups possible. This simplified board and corresponding statistics were then saved. Witless then chose a direction order bias and made a simple 2-step path (either north or south of the entrance, depending on edge proximity). Next, Witless did a "ballooning" of the path: if there were two open spaces next to an existing edge of the path, the edge was replaced with three edges going through the two (now filled) spaces. The order of filling was controlled by the direction order bias, above. Once no more ballooning could be done, Witless scanned the path for surrounding open spaces. When an open space was detected, A depth-first search was done to find a path through that space, reconnecting with the existing path at some later point. If such a path was found, then another round of ballooning was done, and the result checked against the original (before the search); if it was better, it was kept, otherwise the original was restored. This was repeated until no more improvement could be made this way. Witless then compared the path with the best path to date, possibly replacing the best path. The direction order bias was then changed, and the board restored to the simplified state immediately after load; a 2 step path was generated, and the entire process repeated. Witless terminated when either it ran out of time (never happened during tests) or it finished all of the preprogrammed direction order biases. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? Several tricks I found (and find) useful: 1) Avoid dynamic memory allocation as much as possible; for well-defined probems with maximum size, it is rarely necessary. Statically (or, occasionally, automatically) allocate for maximal size, and use as much as you need. 2) Lay out your data structures for simplest use. In the case of Witless, this included representing the board (partly) as an array of characters, with I used directly as the read buffer when loading the problem. No character translations were done on the input, and the numbers included in the problem file were never parsed. 3) Put borders around your data spaces, so you don't have to special case edge effects. I added a 0th and an (n+1)th floor to the building, filled with impassible terrain. (The impassible terrain happened to be nulls in the character array, so I didn't have to initialize it, either.) 4) Make array dimensions powers of two whenever possible, even if this causes overallocation of memory; the speed increase from the simplified indexing is noticable. 5) If working in a multidimensional space where directions are barely distinguishable, don't use a multidimensional representation. Instead, flatten it to one dimension, with the various directions transformed into different size offsets. By referring to these offsets in a variable, you can make the same code work for all the directions, instead of just one. 6) Don't grow overly attached to complex algorithms; they rarely work better (or even as well) as the simple ones. (I ended up abandoning all work I had done after the first week of this contest.) Of course, the truly simple (brute-force) solutions rarely work, either... 7) If you think it will work, test it. If you don't think it will work, test it. If you don't think, test it. It's amazing what the tests show. 8) Profilers are your friends. ================================================================= ======================================= janitor ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR janitor 20482 3653 1843 4920/397 7386/790 8176/2466 Greg Youngdahl ================= janitor was submitted by Greg Youngdahl at youngdahl@lucent.com ================= HOW DID janitor approach the task? Special tricks? Basically it used a bruit force approach. One thing I did (and I'm sure it wasn't unique) was to add a basement, attic, and west wall of all '#' characters to the building so I wouldn't have to be checking all the time to see if I was at a boundary, I could just look for '#'s and let them block my path as they would anywhere. DID janitor iterate in any way? How did it know it was done? From any particular square janitor had a sequence of moves that it would try to make. If a move succeeded it would try moving on from the new square trying moves in the same sequence. Once it got blocked (no more possible moves from a given square) it would back up to the previous square and try the next move in the sequence for that square. I ended up using 28 different sequences of moves from any given location in order. These were almost arbitrarily chosen. I found that any particular sequence would generate some result (if it found a path at all) fairly quickly and then as it continued searching it might find a better result that was only a few steps better even though it searched for a long time (I think basically a given approach would end up blocking off a section of the building and would have taken a long time to get back to that area of the building and move into it). I was better off to start over with a new move sequence after a short time of searching. I decided to consume 20 seconds on a given sequence and then give up on that and try another sequence. Is that iteration? Running for 20 seconds on each of 28 move sequences should have run for 9 minutes and 20 seconds, leaving me with 40 seconds to spare (or I could have done a couple more sequences). On my system at work (a Sparc5) I found I could check on the time every 64000 steps and come in within about 5 seconds of that time limit. However on the runs for the contest (on Fred's system) apparently the processor is significantly slower, and each of my runs exceeded the 10 minute limitation by a few seconds (I though when I got the results of my runs in the mail that I was going to be disqualified, but apparently I didn't violate that requirement enough for disqualification). For any substantial building it knew it was done when it ran out of time. In theory (given enough time with a given move sequence) it would have tried every possible move from every possible square and found the ultimate path through the building. But of course 10 minutes was nowhere near enough time to do that for any but the most trivial buildings. Given enought time (or a simple enough building) it would have realized that it had backed up to the starting square again and known it was done. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? Well, my office mate suggested that the people who found 0 paths for any of the buildings ought to be fired ;-) Here is a program for them... main() { printf( "ns\n" ); } I'm also wondering why the VERBOSITY AWARD went to Ripple.c at only 49710 bytes. Janitor.CC was was 66155 bytes. *** POTM-MASTER NOTE: Don't be so proud!!!! WHAT DO YOU DO FOR: A LIVING? software engineer. FOR FUN? guitar player. INNERMOST SECRET? uh... no comment. POTM IDEAS? wait for Fred to send out contest announcements. ================================================================= ======================================= Round+Round ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Round+Round 20422 4415 1650 5290/1029 6908/1345 8224/2041 Daniel vanderZee ================= Round+Round was submitted by Daniel vanderZee at zee@info.nl ================= HOW DID Round+Round approach the task? Special tricks? The program starts by generating one or more random points in the building and attempts to find a path through it. Once it finds a path it randomly deletes sections of the path, inserts new points into the path and attempts to find a path through these points. If a path through these points is found it tries to "sidestep" and "step back" wherever possible, i.e. path sections like ?w? are replaced by ?nws?. Round+round is just a basic genetic algorithm. It starts out with a set of paths, keeps only the best paths, mutilates 'm and starts over. ================================================================= ======================================= rookie ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR rookie 19596 5447 1642 4156/1198 7314/1812 8126/2437 Paul Nelson Sorry ... no description available for rookie ================================================================= ======================================= blind ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR blind 18572 3529 915 2490/442 8008/1365 8074/1722 Carlos Valenzuela ================= blind was submitted by Carlos Valenzuela at carlos@basic.attis.com.mx ================= HOW DID blind approach the task? Special tricks?> It is based on two complementary methods: 1) List all the possible next movement sorted (ascendant) by number of neighbors then choose just the first 3 Group this moves 8 by 8 Generate all possible ways of 8 movements Sort them avoiding isolate squares, choose just the first 2 2) Once that a path exist, find all couples of adjacent squares that can be added to the path DID blind iterate in any way? How did it know it was done? Once that the limit time is reached or when the building is full or almost full (one square free) WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? 28 years, single (not for long time) Bachelors degree on Physicist UNAM Mexico; I work as programmer on EPIA, here we make Software for Banks in Mexico I love Science F. Movies, and walk on the wood About POTM contest I Found very stimulant to see the tables of results from several different test-problems What about let the participant run his own test on the POTM-machine, that way the portability problems and others related could be fixed and worked out more easily Fred, thanks for your assistance and friendly help. I really enjoy this contest. Please feel free to change the style or the grammar of this message. (Please do). ================================================================= ======================================= Minos ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Minos 18242 3718 1758 3130/709 7068/1278 8044/1731 Didier Barzin Sorry ... no description available for Minos ================================================================= ======================================= strider ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR strider 15766 5823 0 2844/1105 5974/1944 6948/2774 George VanAusdall ================= strider was submitted by George Van Ausdall at gva@bob.lc.lucent.com ================= WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? Answering the personal questions first, I'm a programmer working for Lucent Technologies. Previously, I worked for Western Electric, AT&T Technologies, AT&T Network Systems, AT&T Corporate Headquarters, and Bell Labs, even though I only changed my work location one time and changed departments only twice! I enjoy bowling, playing bridge, and solving programming problems. Now, on to the interesting subject: HOW DID strider approach the task? Special tricks? Strider (named after the character in J.R.R. Tolkien's Lord of the Rings) was written in just a few hours over the course of the last two days of the contest, so it's not very sophisticated. In fact, this description is longer than the source code! The representation of the building in strider is the obvious one: a three-dimensional array. There's also a one-dimensional array for storing the sequence of moves. The maximum size of the building specified in the problem description makes this practical. There's no dynamic memory allocation in strider. The only analysis of the building that it does is these two simple things: 1. It determines the true number of columns in the building. I.e., it checks how many columns on the right are completely filled with #s (the rightmost one should always be so). A better test would be how many columns are inaccessible; but that's a lot harder! 2. It counts how many of the three locations directly east of the E and directly east of the two spaces above and below the E have #s. If two or more of these locations have #s, the only possible solutions are the two trivial solutions "ns" and "sn". If analysis #2 does not show that a trivial solution is necessary, strider starts by moving north if the location directly east of the space above the E contains a space. It then moves east. Then, it enters a loop that tries to move up as far as it can, tries to move down as far as it can, and then picks a horizontal direction to move one step. If it can't move in any horizontal direction, it backs up one move and tries again. If it succeeded in moving up or down before unsuccessfully looking for a horizontal direction, it will back up (or down) one floor. Whenever strider backs up, it marks the location that it backed up from, so it will never try to move there again. (This is to guarantee that strider will terminate.) The main loop exits when no horizontal move is possible and it's not possible to back up anymore (in which case it outputs the trivial solution "ns") or when it moves back into column 0. In the latter case, it then moves north or south one step, if necessary, to get to the E. The code for the horizontal moves tries to move in the general directions indicated by the following diagrams (please excuse the crude ASCII art -- I'm not an artist), which show strider's movements in two empty one-floor buildings; one with an even number of columns, and one with an odd number of columns (hence analysis #1 above). The idea is to go north and then go east across the north side of the building. Then, it goes alternately south and north along the columns, gradually heading back to the west. By wandering the building from east to west, the area around the E is left unvisited until the end, maximizing strider's ability to make its way back to the E without having to back up a lot. ---->---->-----+ ---->---->---->---+ E | E | -<-+ +-<-+ v -<-+ +-<-+ +-<-+ | | | | | | | | ^ | ^ | ^ | ^ +->-+ | v | v | v | | | | | | | | | +-<-+ ^ | ^ | ^ | ^ | | v | v | v | +->-+ | | | | | | | | +-<-+ +-<-+ +-<-+ +--<---+ This simple strategy works well in empty buildings of any size, but it tends to leave large areas unvisited in complex buildings. If I'd allowed three days to write strider instead of just two, I'd have added one more thing: After completing the path, look for unvisited locations that are adjacent to visited locations and start a new path through the unvisited locations. If the new path intersects the old path such that the new path is longer than the bypassed part of the old path, splice in the new path. (If the new path comes back to the old path in more than one place, it should pick the place that's closest to where it started the new path.) This can be repeated until there are no more unvisited locations adjacent to visited locations. Finally, strider outputs its sequence of moves. ================================================================= ======================================= boom ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR boom 15724 5783 2 3000/1157 6062/1997 6662/2629 R.Ang I.Soehardjo Sorry ... no description available for boom ================================================================= ======================================= Protein ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Protein 15254 2605 1710 6/0 7180/1379 8068/1226 Kroum Savadjiev ================= Protein was submitted by Kroum Savadjiev at kroum@consulan.com ================= First, i would like to congratulate all my competitors - participants of the POTM for the work done to solving the problem, and, of course, the POTM Master for the overall organisation, which was very good! HOW DID Protein approach the task? Special tricks? I changed my strategy at almost every new version of Protein. First, my approach was to take a valid path ( "sn" is always a valid path ), and then to "swell" him to the maximum level. For exemple, "sn" can be "swelled" to "senw", if possible. Unfortunately, this version was not very good, because at the end there was too many unused places. Also, this version did not pass the second system test - the big empty building, it was very slow. I managed to accelerate the program, but the speed was still insufficient. Then i added a preliminary function before the swelling, which was very fast, but not very efficient in terms of "filling" the building. This function's output was a relatively long path for almost no time, and it was used like "seed" to the subsequent swelling. The big empty building was filled entirely, but in the others buildings there still was too many empty places... My last version uses 3 stages: first, a very quick filling of the building, then a "swelling" of this preliminary path, and, at the end, a "slow" function which tries to fill all the remaining places using an exhaustive iteration for all the time remaining (the first 2 stages usually took 3-4 seconds), in hope that the building will be filled in the most efficient way. I think that Protein behaves not very bad... I have some ideas to improve it, but unfortunately i won't have the time until the end of this POTM. DID Protein iterate in any way? How did it know it was done? After the first two stages, Protein tries to iterate through all possible remaining moves, in order to fill all the empty rooms. This is, of course, impossible on a "real-life" building, but , fortunately, in the first 2 stages almost 90% of the work was done in a very short time. Nevertheless, i still cannot pass through all remaining moves, but for 570 seconds the path is lengthen with some moves. I know that the exhaustive search cannot be the so- lution, unfortunately, when i realised that the first 2 stages was not enough for a good result, there was not much time left to imagine a better solution. My second stage, the "swelling", also uses iteration, in a sense. 1st it was a recursive function, but for performance reasons, i changed the recursivity with an ordinary loop. But i think the question is not about this kind of iteration. At the end, the third stage does not know that the task is done, because the task is almost never done 100%. It just uses all the remaining time... ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? I have just a comment: the POTM-Master was absolutely right saying that entering soon is paying. This, among other things, gives the opportunity to compare our program with the competitors, and to take measures to improve the necessary. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? I live and work in Montreal, a beautyfull city. I work as a programmer, and programming is also my "hobby". At the end, i would like to wish everybody (and myself) better results at the next POTM! ================================================================= ======================================= sagan ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR sagan 15022 2520 24 6/0 6898/1070 8118/1450 Douglas Zongker ================= sagan was submitted by Douglas Zongker at zongker@cps.msu.edu ================= HOW DID sagan approach the task? Special tricks? sagan first determines which squares on the map will never be part of any legal path and fills them in with walls (eliminating blind alleys, etc.). It then represents the remaining rooms as nodes of a graph, with edges connecting adjacent rooms. The graph is collapsed to remove all nodes of degree 2 (so that, for instance, a long hallway will be represented as just one edge in the graph). To generate a path, it starts with a trivial seed path "ns" or "sn", or "ud" or "ew" if those are legal, and tries, by exhaustive search, to replace every subpath with a longer subpath connecting the same rooms. It tries once for each seed path, and then outputs the longest path generated. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? This is my first POTM -- I could use some myself... WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? I'm starting as a CS grad student at the University of Washington. ================================================================= ======================================= Wandering_Plane ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Wandering_Plane 14950 2420 0 6/0 6880/1088 8064/1332 Raj Singh Sorry ... no description available for Wandering_Plane ================================================================= ======================================= Save_The_Worm ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Save_The_Worm 14908 3822 34 6/0 6830/1447 8072/2375 Vance Heron ================= Save_The_Worm was submitted by Vance Heron at vance.heron@jpl.nasa.gov ================= HOW DID Save_The_Worm approach the task? Special tricks? Started with the simplest "legal path" - either ns or sn, then extended it by two moves each time e.g. nusd or nesw. I repeatedly run through the entire path checking for available 2 move extensions. Tricks: Created a "bottom" and "top" floor all #, simplifying checking for legal moves. Built the output string 2 characters at a time - and saved the "best" output string for a single print. DID Save_The_Worm iterate in any way? How did it know it was done? I found I could do an entire "run" very fast and ended up doing several runs, trying different starting moves and orders of extensions. After N tries (currently N=12) I print the best result. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? Tried an approach similar to the 8 queens problem, where I made moves until I either got to the end, or got stuck. Then I backed up and tried different choice from a given position. Took way to long, and ended up repeating backtracks - I still think this approach has potential. I'm not very happy with my current approach, but couldn't come up with a better one with the limited time I had. An approach I haven't quite worked out would be to determine all possible vertical moves, then find ways to connect them at the various levels ?!?. Lost a lot of sleep trying to think of a better approach ;-/ WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? Living - System Engineer, designing and testing systems to capture process and distribute SAR data obtained from earth-observing satellites. Fun - Play with my 2 young children, and sing in a barbershop quartet. I also enjoy hiking, camping, cooking and reading. Recently added POTM :) Innermost Secret - you've got to be kidding. I will say that "save the worm" is a joke refering to the previous JPL/NASA logo, which used a worm like font, recently replaced with the old NASA logo used during the 60s, commonly called "the meatball". POTM Ideas - I like the idea of a program that "plays" against another (I believe you've done that at least once before). Given a sequence of numbers, guess the next one (e.g. 1 11 21 1211 111221 ..) Mastermind type games (guess a sequence of digits, given hints at each move) ================================================================= ======================================= Plima ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Plima 14868 2401 0 6/0 6904/1215 7958/1186 Zeljko Zahtila ================= Plima was submitted by Zeljko Zahtila at zzahtila@vitgdts1.telecom.com.au ================= HOW DID Plima approach the task? Special tricks? The idea behind Plima (high tide) is simple: start from the shortest path (e.g. ns) and try to expend one path segment at a time, i.e. s would be replaced by wse, and the path would become nwse; then w would be replaced by nws, and the path would now be nnwsse. This strategy works well when there are no forbidden rooms. I spent a lot of time developing an algorithm to go around forbidden rooms that worked very well in 2 dimensions but didn't find a way (and time) to port it to 3 dimensions. DID Plima iterate in any way? How did it know it was done? Plima keeps expending a segment until possible, than it moves to the next segment. The algorithm is so simple (and quick) that it didn't have to check for time limits. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? If I had to do it again I would apply knowledge about graphs that I subsequently acquired from Sedgewick: Algorithms in C++. Reading of this book was inspired by this problem. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? For living: computer consultant. For fun: bringing up two sons (Tony 3.5, Mate 1.5). Not much time left for anything else. Time spent on POTM was stolen from my sleep. Secrets: let them keep this status. POTM ideas: None at the moment, if something comes to mind I will let you know. Keep the good work going. ================================================================= ======================================= zigzag ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR zigzag 14718 2143 0 6/0 6776/989 7936/1154 Mark Kuczynski Sorry ... no description available for zigzag ================================================================= ======================================= proto1 ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR proto1 14478 2399 1796 6/0 6584/1119 7888/1280 P.Frants S.Pieterse ================= proto1 was submitted by P.Frants and S.Pieterse at pfrants@cs.vu.nl ================= HOW DID proto1 approach the task? Special tricks? Unfortunately we could not spend as much time as we wanted on this POTM, but here we go. The only thing we did was to create the shortest path first and then we improved that path by adding two steps anywhere possible until the path did not improve anymore. DID proto1 iterate in any way? How did it know it was done? The above algorithm was repeated until time was up. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? We have implemented functions for identifying so-called 'rooms' and our plan was to connect as many of these as possible before applying the improvement algorithm above. That Damn Time... WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? Studying and having fun. Athletics, rc-flying, potm etc. None at the moment, but when we think of one we'll mail Fred. Thank you once again Fred, and all the other competitors! ================================================================= ======================================= Where_to? ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Where_to? 13224 1440 1280 5504/634 7718/806 2/0 Markus Sabadello Sorry ... no description available for Where_to? ================================================================= ======================================= pastaiga ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR pastaiga 12866 2335 260 5304/1081 7562/1254 0/0 K.Boitmanis A.Zogla ================= pastaiga was submitted by K.Boitmanis and A.Zogla at acad.latnet.lv!ugale@kcig2.att.att.com ================= HOW DID pastaiga approach the task? Special tricks? Reading data and initializing: walls and other #'s was stored as some big numbers(20000), reminder of building's main array - 0s; initial path was marked as (-1;-2) (entry as -1); iterating started at -1 with numbering of elements of array 1,2,... which means distance from path (if element's number is 5, distance to path is 5 steps). If any number meets path (negative numbers), length of possible addition to existing path is evaluated and if this is more than distance from current start position of numbering to meeting position, path is prolonged by renumerating (negatives). No searching for path elements through big array, there is temporary array for storing of path elements and searching is performed only in surrounding elements of path in building (n,s,e,w,u,d). After renumbering of path elements numbering of array continues with last used path element for previous numbering. After reaching entry element, all goes round again until no additions had made during one cycle. Built in time control. If time is under halfway (300 secs), attempt to find better solution is performed (another initial path (-1;-2)). Temporary array for storing path (chars). ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? Just remember, correct solution for any task is short and simple. Pastaiga means walking. Main trick. ;-) WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? For POTM as it is any idea, where problem has no one and only correct solution, is OK, like recognition of something from images(text, fingerprints, etc.), packing and unpacking, etc. ================================================================= ======================================= Red29erDevils ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Red29erDevils 8714 3434 1969 2798/1078 0/0 5916/2356 Nils Magnus ================= Red29erDevils was submitted by Nils Magnus at shocc@unix-ag.uni-kl.de ================= HOW DID Red29erDevils approach the task? Special tricks? We first look for an arbitrary path through the store and afterwards we try to enhance this path. ** Find a path: To find any path, we develop a depth-first-search from two starting points. Branches are cut if we touch the other tree or if we have no other way left to go. We select from the resulting intersection points the one imposing the longest path. ** Enhance a path: Given a path, we try to find from each path element to find a path to another possible path element. If we find such a new path and it is longer than the old connection, they're swapped. DID Red29erDevils iterate in any way? How did it know it was done? We iterated over our path. One can think of running with an air-empty bicyle-tyre trough the building from entry to exit and pumping air into it afterwards. Shouldn't we be able to pump any more air into the tyre (the path), we're finished. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? A great one. I'm still not sure if this problem is really NP-complete. I assume it is, but allowing only little differences compared to the optimal solution this problem should be solvable in rather short time. But reality is different... :-\ I learned C++ is nice to code (for some respect), but rather clumsy in execution. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? Distracting the focus from the dark side of life, e. g. physics exams and similar stuff. I guess I should become programming contestant pro. Thinking about solutions we discussed cellular (sp?) automats (e. g. life) acting as independent solvers of bigger problems... Just an idea... ///Nils, who was supported by Peter and Tun ================================================================= ======================================= DownAndOut ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR DownAndOut 8394 849 742 464/92 0/0 7930/757 Jim Eadie ================= DownAndOut was submitted by Jim Eadie at jim_eadie@cc.chiron.com ================= It was apparent from the start that a recursive approach was needed in order to search for a MAXIMUM path as opposed to just a path. However that would have needed a pretty large stack. So an iterative approach ( tail - recursion) was used and the first path found was used. Another restriction, the 25K source code limit, also influenced my approach. I could not develop much code to evaluate and prune any paths found. I pretty much experimented with searching in the directions n,e,s,w,u,d and permutations of that set. Some arrangements were quickly discarded as they invariable generated short paths. Before the actual search begins I scanned the maze to identify those squares which could not possibly be in the path as they only have on entry point. I figured this would help in reducing the backtracking effort out of dead ends. I identified the task as being over by just testing the resulting move against the known entry square. It very quickly became apparent that many squares were being left un-wandered and also that they could have been included in the path. I spent a fair bit of time looking for a way to incorporate these squares AFTER a path had been found. I developed a "splice" function. It looked for at least 2 adjacent empty squares ( ie nn, ss, uu, etc) which might be reached from a nearby by pair of squares on the path. I then looked to see if a deviation could be made from the found path to incorporate these empty squares. For example on a path of ...nn..., next to 2 empty squares on the east side, one could turn this into ...enwn... This splice was repeated until no further possibilities existed. The final approach to the problem came when the empty maze became the test system. Unfortunately all the above did not help in solving the problem in the allowed time limit!!! In a fit of lazyness I just modified the program to only scan the lowest floor, and then let the slice fill in the rest. ================================================================= ======================================= Marketroid ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Marketroid 8068 1290 895 6/0 0/0 8062/1290 Steven Burnap ================= Marketroid was submitted by Steven Burnap at sburnap@wsgc.com ================= HOW DID Marketroid approach the task? Special tricks? Not as well as I'd have liked :-) Basically there are two phases. First, it examines the input and replaces any unreachable spaces with a '#'. Unreachable spaces are those either surrounded by '#'s or adjacent to only one '#' (dead ends). It makes multiple passes until no more such spaces are found. Then it does a more in-depth analysis to find large areas with only one entrance. All spaces in these are also filled with '#'s. This makes the second phase easier as the program doesn't have to worry about dead ends. In the second phase, it creates a minimum path ("ns" or "sn") and then tries to expand on that path until either it cannot or it runs out of time. The first part of this is to search the path for two adjacent used spaces that are next to two adjacent unused spaces. This is then expanded from a two-square path to a four square path. It stops this when it can no longer find any such spaces. At this point Marketroid usually has a pretty good path and has used less then five seconds of time. It then starts scanning for subpaths that seem to be adjacent to many unused spaces. It then clips the subpath out and tries to find and better path (recursively). It does this until it runs out of time. DID Marketroid iterate in any way? How did it know it was done? Yes. All of the steps are short and guarantee a valid path that is at least no worse then when the step started. It is then done when it runs out of time. (To be on the safe side, it starts cleaning up and printing output when there are 30 seconds left. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? This solution seems to work pretty well for getting a decent path quickly, but for getting the best solution I think a whole other approach is needed. The second part of the expansion phase would only add ten or so spaces to the path on buildings the size of the test building. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? I'm a computer programmer working on OS/2, AIX and Z80 Point of Sale software (mostly in C, some in C++) for Williams-Sonoma. ================================================================= ======================================= Run_A_Muck ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Run_A_Muck 5268 574 1953 5268/574 0/0 0/0 Jim Wright ================= Run_A_Muck was submitted by Jim Wright atjwright@seattleu.edu ================= HOW DID Run_A_Muck approach the task? Special tricks? Run a muck started out as a Brute Force Algorithm. It did not score very high on the first test, so I decided to find a better algorithm. I looked at what most people used for the TSP, and that was Linear Algebra. I found that the simplex method gave me the Maximum moves through the building, but it also gave me too many small paths and loops to contend with. So I looked at the Stepping Stone Algorithm from Operations Research. This is the algorithm that worked the best, however it took too long to solve the bigger buildings. I then took the Brute force algorithm and graphed it on to the Stepping Stone, if the building is big then Run A Muck will use brute force, smaller buildings use the Stepping Stone. Both of these algorithms take too long so they find as many paths it can in Ten minutes and then prints the largest one. The stepping Stone may not hit the most ups it can, but the Brute force algorithm tries going up first then down second ensuring that the first long path it finds has the most ups. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? By the way, I'm Jim Wright, I work for the Boeing Company, as well as getting my Masters in Software Engineering. My idea for a POTM is to build a Adventure Game Solver. This would require building an Adventure Game in C and then having an interface where you send a string of commands into the C game and then receives a string of what the game did back to the entry. It will do this until a 'You have solved this game' message appears. ================================================================= ======================================= YAIA ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR YAIA 5266 998 1312 5262/998 2/0 2/0 Emery Lapinski ================= YAIA was submitted by Emery Lapinski at ewl@panix.com ================= HOW DID YAIA approach the task? Special tricks? I never felt like I got a very good mental handle on how to deal with this problem. (I still can't think of a way to brute force a solution.) After a few false starts and frequent redesigns I came up with what seemed to give me a fairly decent path through the buildings I tested without being too easily fooled. From a given location YAIA moves to an available location that: a) is furthest away from the exit and b) still allows YAIA to reach the exit. Based on rather specious heuristics it is easily fooled so I find paths for each possible move off the entrance space, time permitting. I planned on taking the initial guess and tweaking it to find better paths. I never thought of a good way to do it. (Like I said, I could never get a good mental model of what I wanted YAIA to do.) DID YAIA iterate in any way? How did it know it was done? No real iteration. Each step taken was followed by a series of calculations, but steps were never untaken. YAIA knew it was done when it had found a path for each possible move off the entrance space. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? YAIA does not stand for "Yet Another" anything, but instead is an abbreviation for an old joke about a sign hanging above a urinal in a mens' room. Are you sure you want to hear it? OK. It's not funny. "Our aim is to keep this bathroom clean. Your aim is appreciated." It seemed appropriate. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? I earn money as a computer programmer designing GUIs and implementing them in Java (until quite recently it was Galaxy/C++). For fun I like to go to the gym, go SCUBA diving, play with my computer and revising my WWW pages. My secrets are hidden away even from myself. ================================================================= ======================================= SeeMyThumb ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR SeeMyThumb 4820 1161 44 4816/1161 2/0 2/0 Brace Stout Sorry ... no description available for SeeMyThumb ================================================================= ======================================= CheeseHead ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR CheeseHead 3856 886 1777 1694/386 2162/500 0/0 Mike Buchmann ================= CheeseHead was submitted by Mike Buchmann at mikeb@cray.com ================= HOW DID CheeseHead approach the task? Special tricks? For each move I computed the number of steps each block was away from the exit position. To do this, I simply looked at each adjacent block and added one to the lowest value, starting with the exit block having a value of one. Since we are really only interested in the blocks adjacent to the current location, I have added a check so once these blocks have been assigned a value to continue. The move is then to the square furthest away from the exit (highest value), unless time is running out (< 1 min) then the program heads for the exit. I also ran the program (time permitting) through three times for the three possible first moves. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? The secret is to find your moves quickly, I have yet to perfect this. Just a little note, you can get a lot more moves out in ten minutes when you run your code on a Cray super-computer! If you would like to order one, just send me a note ($30 million should get you a really nice one). WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? I am a computer programmer for Cray Research (now an SGI company) working in the design automation department. My work has mainly been with printed circuit board design. I would like to thank Fred for organizing and running this event. It really has been fun to work on and to compete. One small suggestion I have is to place the supporting programs (timing code, maze generation...) on the POTM web site. I will be posting my entry on the internet after September 1st at http://home.cray.com/~mikeb/potm (I am assuming that mine will not be the winning entry). I would like to see others solutions. If you would like to share your solution with me, send it to mikeb@cray.com. ================================================================= ======================================= LostSoul ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR LostSoul 372 64 1785 6/0 110/11 256/53 Byon Garrabrant ================= LostSoul was submitted by Byon Garrabrant at byon@netcom.com ================= HOW DID LostSoul approach the task? Special tricks? The plan was to start with an empty path, choose a random direction and two random points in the path, and add the direction at the first point and the opposite direction at the other point and test for success. If it fails, try another random set, else make that the new path and start over. Sometimes it tries several additions before checking for a valid add. DID LostSoul iterate in any way? How did it know it was done? It just kept adding steps until it could add no more (many attempts without growth), then it compared that path to the best, saved it if better and started over with an empty path. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? It was a lot of fun to write, but the timing was tricky to solve on the test platform since I used a different platform WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? Computer Game Programmer for Virgin Interactive for money and fun. Amatuer Radio (KD6BCH) just for fun. Keep up the good work on the PTOM! ================================================================= ======================================= ROGUE ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR ROGUE 82 6 469 6/0 0/0 76/6 Michael Strauch Sorry ... no description available for ROGUE ================================================================= ======================================= XaaShuffle ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR XaaShuffle 28 0 603 18/0 4/0 6/0 Mark Huizer ================= XaaShuffle was submitted by Mark Huizer at xaa@stack.urc.tue.nl ================= Hey... forget it :-) I couldn't find the time to do anything on it :-( ================================================================= ======================================= Maze_Master ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Maze_Master 6 0 0 2/0 2/0 2/0 Ertugrul Tabak Sorry ... no description available for Maze_Master ================================================================= ======================================= RoamAndRamble ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR RoamAndRamble 6 0 0 2/0 2/0 2/0 Russ Cox ================= RoamAndRamble was submitted by Russ Cox at rsc@research.att.com ================= HOW DID RoamAndRamble approach the task? Special tricks? Basically, it used recursive descent to try all paths, with some optimizations. It checked every few steps to see what was isolated and what was not. If it counted and found that there were not enough unisolated squares to find a better path than before, it bailed out. That was about it. It opted for up and down before any other moves so that I had the tiebreaker thing all set. Early on, I was 11th but second in up/downs. Unfortunately, recursion wasted a lot of stack space and the program dumped core on Fred's machine. So I wrote a printf statement and mailed it in, and never bothered to fix it. So that's the secret to my speed (and low score). DID RoamAndRamble iterate in any way? How did it know it was done? The operating system told it so. It sent SIGsomething and dumped core. Actually, the current version is just a printf, so there was no loop. In the real program (which runs only on real machines :) it recurses until it notices that time ran out. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? Not really. Don't use recursion. Write your own stack. Spend more time on it than I did. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? I don't do anything for a living, really. I go to school at Delbarton School (high school senior) in Morristown. For fun I do crazy things like this programming contest. I don't have any ideas for POTM or an innermost secret. ================================================================= ======================================= Swifter_Drifter ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Swifter_Drifter 6 0 0 2/0 2/0 2/0 Scott Everett Sorry ... no description available for Swifter_Drifter ================================================================= ======================================= CARAMBA ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR CARAMBA 6 0 666 6/0 0/0 0/0 Ralph Meira ================= CARAMBA was submitted by Ralph Meira at ralph.meira@sophia.attgis.com ================= HOW DID CARAMBA approach the task? Special tricks? Iteration based on a algorithm that usually works well for the "chess knight's walk" problem. I just introduced an extra function that wouldn't allow a move into a position that could not be traced back towards the entrance. DID CARAMBA iterate in any way? How did it know it was done? My biggest problem ! Because I iterated, every time the program arrived at a better solution I would store and continue. Close to the time_limit I would break-off to the end and print out the best solution. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? Don't underestimate large empty buildings ! WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? ;-) ================================================================= ======================================= vasco_da_nada ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR vasco_da_nada 6 0 1365 2/0 2/0 2/0 Salman Nawaz ================= vasco_da_nada was submitted by Salman Nawaz at sal@coltrane.cb.lucent.com ================= HOW DID vasco_da_nada approach the task? Special tricks? No special tricks, in my opinion. I guessed from the beginning that it would not be possible to try all possible paths in ten minutes. I took a pseudo-random approach where I start at the entrance, find all initial moves, and then for each possible initial move, make moves according to a heuristic of "udnesw"; i.e., ups are most preferred, followed by downs, followed by norths, etc. I make legal moves using the heuristic until either I find myself back at the entrance or I hit a dead end. If I find myself back at the entrance, I stop and start over with the next initial valid move. If I hit a dead end, I take moves back until I'm no longer at a dead end or I find that I can't get any solution with the current path. The final version is as just described, but attempts the initial valid move paths for a total of three different heuristics ("deunsw", "udnesw", and "nduesw"). DID vasco_da_nada iterate in any way? How did it know it was done? Iteration was simply as described above. Again, vasco_da_nada knew it was done only by happenstance: either it just found itself back at the entrance and knew it had to stop, or it found itself at a dead end and found that it would have to take back all of its moves to avoid the dead end (a zero-length "solution"), and would just give up and go to the next attempt. The total number of "attempts" in this sense is the number of heuristics (three) times the number of initial legal moves (two or three, depending on the input). ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? It was a wonderful exercise. I've been coding in C regularly for about ten years, and I still found myself needing to revisit my "C Traps and Pitfalls" book. I initially was dynamically allocating all large data structures with malloc(). Changing to static allocation more than halved execution time in most cases I tested. Unfortunately, it didn't magically cause vasco_da_nada to find the optimum solution. I was amazed that in one case, for a simple three-story building with five rows and ten columns, one initial path took 65 moves to find a solution, another path took about 150,000 moves to find a solution, and the third path ran for an entire weekend and I had to kill it. Just goes to show you how many possible combinations there are when you try to iterate in a solution space of, oh, somewhere around seven to the eightieth power? (and that's for the smallest possible building...) WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? For a living: I work in (Lucent Technologies!) Bell Laboratories' BCS (Business Communications Systems) business unit, and particularly in Multimedia Messaging and Response (voice mail and voice response systems, for example) as a software/systems-engineer/next-to-last-line-of-technical-support person. We affectionately call it Current Engineering for Intuity AUDIX. For fun: Budding guitar player with a little previous piano instruction, very very amateur poet/songwriter/singer. It's okay, at least I can amuse myself. I also enjoy playing pool and engaging in heated conversations about history, politics and society (often at the same time!). Also, weeding my yard (freaky, huh?). Innermost secret: Reduced my TV consumption to less than five hours a week in 1982. Reduced it further to approximately zero in June of this year. Shhh, don't tell anybody; they'll find out how much of a freak I really am. And no, I didn't toss it off a building or smash it with a sledgehammer; it's in a dark corner of my basement attached to a VCR so I can rent a movie one of these days. ================================================================= ======================================= Crazy_Scheme ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Crazy_Scheme 6 0 2004 6/0 0/0 0/0 Mike Mossey ================= Crazy_Scheme was submitted by Mike Mossey at dgr.jpl.nasa.gov!mossey@att.com ================= HOW DID Crazy_Scheme approach the task? Special tricks? I call it "inflating." It starts with the path 'ns', a known complete path (let's call a complete path, starting and ending at the door, a "loop"). Then it looks for two consecutive squares on the path A and B that have empty space next to them. It tries to make a new path segment that starts at A and ends at B. If it finds one, then it has extended the loop...the new loop is guaranteed to be a loop and guaranteed to contain all the original squares on the loop and all the new squares. DID Crazy_Scheme iterate in any way? How did it know it was done? It tried to apply the inflating process over and over until it couldn't find a place to apply it. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? One of the nice things about Scheme (a Lisp variant) is the garbage collection. This let me construct functions that had no side effects and still operate efficiently. Let me explain: All my functions that operate on the structures that represent the building, the path, etc. have no side effects. Eg, the function that inflates the path takes a building/path structure as an argument and returns an entirely new building/path structure (well effectively new...more in a bit). The old building/path structure still exists in case I need it for backtracking or something like that, and in general the lack of side effects makes the expressions I use simpler and more easily understood. "But darn these buildings take a lot of memory, and the new path might only represent a small change. You mean you copy the entire building into the new structure even when most of it is the same? Isn't that inefficient?" Actually I don't have to copy much at all. Scheme (and Lisp) data structures are often trees with pointers linking the parent nodes to child nodes. I can copy the parts of the tree that I don't need to change by copying the pointers of high-level nodes, and not many are required to get most of the tree. So the old data and new data ~share structure~. "But when you go to free data, you can't free any parts shared with other data structures. Isn't that a great deal of complexity?" I never explicitly free data...the garbage collector does it for me, and does an efficient job of it too. It knows when parts of the tree have been forgotten about, and quietly frees them so that they may become reincarnated as new useful data, begin the Great Cycle again, and move a step closer to nirvana. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? For a living I program computers at Nasa's Jet Propulsion Laboratory. For fun I compose music following the tradition of what is commonly called "classical music." My innermost secret is the weight of my liver in grams accurate to 4 places---and I'm not talking. As far as POTM ideas, the ones I've seem so far are pretty darn good. ================================================================= ======================================= AmazingStories ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR AmazingStories 4 0 671 0/0 2/0 2/0 Ruud deJong Sorry ... no description available for AmazingStories ================================================================= ======================================= WalkAbout ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR WalkAbout 4 0 932 0/0 2/0 2/0 Charles Roberson Sorry ... no description available for WalkAbout ================================================================= ======================================= CrazyWalk ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR CrazyWalk 0 0 0 0/0 0/0 0/0 Wim Decroix Sorry ... no description available for CrazyWalk ================================================================= ======================================= Ramblin_Man ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Ramblin_Man 0 0 0 0/0 0/0 0/0 Vince Wolodkin Sorry ... no description available for Ramblin_Man ================================================================= ======================================= TheExtraStep ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR TheExtraStep 0 0 0 0/0 0/0 0/0 Jeffrey Pogodzinski Sorry ... no description available for TheExtraStep ================================================================= ======================================= Wanderer ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Wanderer 0 0 0 0/0 0/0 0/0 John Hitchcock Sorry ... no description available for Wanderer ================================================================= ======================================= dalmation ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR dalmation 0 0 0 0/0 0/0 0/0 Ken Weinert Sorry ... no description available for dalmation ================================================================= ======================================= delver ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR delver 0 0 0 0/0 0/0 0/0 David Wells Sorry ... no description available for delver ================================================================= ======================================= ImLost ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR ImLost 0 0 774 0/0 0/0 0/0 Michael Goldshteyn Sorry ... no description available for ImLost ================================================================= ======================================= legume ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR legume 0 0 1324 0/0 0/0 0/0 Mark Schnitzius Sorry ... no description available for legume ================================================================= ======================================= LuckyBlindDrunk ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR LuckyBlindDrunk 0 0 1980 0/0 0/0 0/0 Ray Cole Sorry ... no description available for LuckyBlindDrunk ================================================================= ======================================= Mr_Magoo ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR Mr_Magoo 0 0 1987 0/0 0/0 0/0 Justin Legakis Sorry ... no description available for Mr_Magoo ================================================================= ======================================= pathbreaker ============= ================================================================= ENTRY MOVES UPS SECS amaze.me multiplic potm.bldg AUTHOR pathbreaker 0 0 1992 0/0 0/0 0/0 John Williams ================= pathbreaker was submitted by John Williams at jwill@chromatic.com ================= HOW DID pathbreaker approach the task? Special tricks? Pathbreaker attempted to pull the problem apart by finding the critical ( shortest ) path and selectively breaking one of the links. This relied on local information, so globally it was not optimized. I followed up by taking the remaining cubes and attempting to splice them into the existing path. DID pathbreaker iterate in any way? How did it know it was done? The first pass was where the problem was broken down and commitments made. The iterative passes are where remaining cubes were spliced in if possible. ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? Basically I ran out of time for pathbreaker development. The first pass is the really important one, and I tried a few tweaks to optimize the selection of a path to break. More analysis here would probably yield better results. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? POTM IDEAS? I'm a verification engineer and mostly hack perl and verilog. I wish I had time to have fun! =================================================================