|
|
|||||||||
|
|||||||||
| |||||||||
|
|
|
| ||||||||||||||||||||||||||
![]() |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Rate Thread | Display Modes |
|
#1
|
|||
|
|||
|
RE: The time draws near
I agree, it was fun. I think my other-half is glad its over.
|
|
#2
|
|||
|
|||
|
RE: The time draws near
I cannot quite agree. It was clasiccal problem, sometimes formulated as finding the shortest path between two towns. This problem also has good solution, described in many books on algorithms
|
|
#3
|
|||
|
|||
|
RE: The time draws near
I'm not quite sure if my solution works in every maze possible. I had much fun coding anyway and I'm really looking forward to the next challenge!
|
|
#4
|
|||
|
|||
|
RE: The time draws near
I agree, this was a lot of fun. My only complaint is that there isn't a clear list of judging criteria. Sure, if you read through the entire forum, Matt gives some tidbits here and there, but there needs to be a good clearly defined list of goals, for example:
1. Function 2. Speed 3. Resource Usage 4. Code Length That way, we know what we need to concentrate on first. My Solution: http://www.digitalsickness.com/contest/ Let me know what you guys think... |
|
#5
|
|||
|
|||
|
RE: The time draws near
yeah, very good.
|
|
#6
|
|||
|
|||
|
RE: The time draws near
very good work
what cpu(s) does the server have? my solution http://www.s0nix.de/path.php (running on a dual PIII 500MhZ) |
|
#7
|
|||
|
|||
|
The time draws near
This proved to be a rather interesting challenge. I am allready looking forward to the next one. I know i learned alot about the upper limits of PHP and some techniques to optimize every cpu cycle in my scripts. who woulda thought a maze could be such a complex thing, both mathmaticly and in terms of code. I am looking forward to seeing the results on this one.
-Jon p.s. Here is mine: http://sig.mine.nu/maze/ |
|
#8
|
|||
|
|||
|
RE: The time draws near
heartily agree, this was a pleasant distraction. nice puzzle, matt, look forward to the next one!
|
|
#9
|
|||
|
|||
|
RE: The time draws near
Me too, me too! This was a great fun diversion and a good challenge to push my fledgling PHP chops.
The only problem is I've been writing so much PHP lately that when I get back to my day job writing C++ code I keep putting the dang $ in front of my variables! Thanks Matt. I'm looking forward to the next one |
|
#10
|
|||
|
|||
|
RE: The time draws near
Thumbs up for all the coders who solved the problem...
Most of all, thumbs up for Matt: the man who came up with the idea of this contest. I really hope this contest will not dissapear. Best wishes for all PHP coders! |
|
#11
|
|||
|
|||
|
RE: The time draws near
Now that the deadline's passed, I'd love to see some of your code -- especially those of you who managed to solve the 201x201 map in under 1 second...
I'll start: http://www.0wn.org/contest/maze/maze.phps Matt, if you'd rather us not share, just let me know and I'll edit my post. Thanks, Chris Lambert, chris.lambert@vbulletin.com |
|
#12
|
|||||
|
|||||
|
RE: The time draws near
I ran this code against a 200x200 maze and it solved it in somewhere between .65 and .70 seconds. This is the "work horse" of the code. If you care to see the rest of it go here.
php Code:
|
|
#13
|
|||
|
|||
|
RE: The time draws near
http://sig.mine.nu/maze/libZork.phps
Is the main file for my script... the major relization came when i figured out that maze routing ISNT a recursive algorithm. While fidning a path out of a maze at all costs can be recursive (e.g. wall walkers etc etc). In the cases we were set to solve it was a known fact where the start, and the end was, and also that a route from start to end did infact exist.. we just had to measure it. I just imagined a scenrio where i could split, or 'make new threads' for each path. Imagine this, you start at the end/beginging of the maze and you have a ball of string in your hand you start walking in the only direction you can go (or use the upcoming fork in the road scenario) letting the string out as you walk. whenever you come to an intersection, the universe splits into as many forks it needs to, say we came to a 4 wayt intersection + 2 new universes would be created with you and your ball of string, in each different universe you went a different path through the maze. And when the first person to arrive at the exit blows a horn all the other universes cease to exist, leaving you alone in your one universe with a ball of string that maps out the shortest route through the maze. cut the string and measure it and badda boom, you have how long it is. Also, if you might have guess several of yous can arrive at the exit at the same time.. in which case its a trivial matter of of deciding which route to take, as they are all the same length.. but some may have more turns or maybe one route had booby traps or something. It would be upto you to decide which one to keep. My guess is that maze routing would be a task that lends itself to quantum computing quite easily. And dont think that maze routing is trivial either... anyone ever view a cpu under a microscope... looks alot like a maze. Makes my mind spin, how about you? -Jon |
|
#14
|
|||
|
|||
|
RE: The time draws near
Well, you showed me yours so I'll show you mine:eek:
There's a working example at: http://65.18.150.149/mazer/ and the code is at: http://65.18.150.149/mazer/mazer.php.txt There are also some links to mazes on the first URL. It did manage to solve the 200x201 maze and on my new host it was finally able to solve the 372x278 maze that someone posted here a while ago. I think the script might have been running out of memory on the other host. I think my reasoning was pretty similar to diclophis, an object cloning itself at intersections. It's funny that you'd mention string because my objects kept track of the path by appending a string with U,D,L,R for the various ups, downs, lefts and rights. When it was done it measured the length of its string using, what else, strlen(). |
|
#15
|
|||
|
|||
|
RE: The time draws near
I have not analysed your code in detail, but only took a fast look. It looks to me, that you used Dijkstra algorithm. This is a known algorithm and you can find it described in many books on algorithms. This is probably the only algorithm, that solved the maze without recursion.
Now, when many people implemented this same algorithm, I wonder how Mat is going to select a winner. Especially, that the only published criteria is functionality. |
![]() |
| Viewing: Codewalkers Forums > PHP Contests > Older Contests > The time draws near |
| Thread Tools | Search this Thread |
| Display Modes | Rate This Thread |
|
|
|
|
|