The time draws near - Codewalkers

Codewalkers Forums Sponsor:

May 14th, 2002, 08:40 AM

EvilivE

Join Date: Apr 2007

Location: Milwaukee, WI USA

Posts: 291

Time spent in forums: < 1 sec
Reputation Power: 3

RE: The time draws near

I agree, it was fun. I think my other-half is glad its over.

May 14th, 2002, 11:06 AM

Anonymous

Registered User

Codewalkers God 35th Plane (22000 - 22499 posts)

Join Date: Apr 2007

Posts: 22,309

Time spent in forums: < 1 sec
Reputation Power: 25

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

May 14th, 2002, 12:01 PM

Laxersaz

Join Date: Apr 2007

Location: Neuss, NRW, Germany

Posts: 21

Time spent in forums: < 1 sec
Reputation Power: 0

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!

May 14th, 2002, 06:34 PM

Anonymous

Registered User

Join Date: Apr 2007

Posts: 22,309

Time spent in forums: < 1 sec
Reputation Power: 25

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...

May 14th, 2002, 07:08 PM

zodiak

Join Date: Apr 2007

Location: Portugal

Posts: 4

Time spent in forums: < 1 sec
Reputation Power: 0

RE: The time draws near

yeah, very good.

May 14th, 2002, 07:15 PM

Anonymous

Registered User

Join Date: Apr 2007

Posts: 22,309

Time spent in forums: < 1 sec
Reputation Power: 25

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)

May 14th, 2002, 07:49 PM

diclophis

Join Date: Apr 2007

Location: Tampa. FL, USA

Posts: 35

Time spent in forums: < 1 sec
Reputation Power: 3

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/

May 14th, 2002, 07:51 PM

Anonymous

Registered User

Join Date: Apr 2007

Posts: 22,309

Time spent in forums: < 1 sec
Reputation Power: 25

RE: The time draws near

heartily agree, this was a pleasant distraction. nice puzzle, matt, look forward to the next one!

May 14th, 2002, 08:27 PM

jameadows

Join Date: Apr 2007

Location: Ashland, OR US

Posts: 7

Time spent in forums: < 1 sec
Reputation Power: 0

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

May 14th, 2002, 10:54 PM

johndoe110479

Join Date: Apr 2007

Location: Bucharest, Romania

Posts: 9

Time spent in forums: < 1 sec
Reputation Power: 0

Send a message via Yahoo to johndoe110479

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

May 15th, 2002, 08:43 AM

Anonymous

Registered User

Join Date: Apr 2007

Posts: 22,309

Time spent in forums: < 1 sec
Reputation Power: 25

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

May 15th, 2002, 09:19 AM

EvilivE

Join Date: Apr 2007

Location: Milwaukee, WI USA

Posts: 291

Time spent in forums: < 1 sec
Reputation Power: 3

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:

Original - php Code

// fill the 2d array

while (!feof($fp)){
    $ch = fgetc($fp);
    if (!feof($fp)){
      if ($ch == "W"){
        $maze[$row][$col] = $ch;
        $col++;
      } else if ($ch == " "){
        $maze[$row][$col] = -1;
        $col++;
      } else if ($ch == "n"){
        $row++;
        $col = 0;
      } else if ($ch == "S" || $ch == "E"){
        $maze[$row][$col] = $ch;
        if ($ch == "S"){
          $s_row = $row;
          $s_col = $col;
        } else {
          $e_row = $row;
          $e_col = $col;
        }
        $col++;
      }
    }
  }
  fclose($fp);

// define boundries
  $b_right  = sizeof($maze[0]);
  $b_bottom = sizeof($maze);

// start algorithm from 'E'. this will mark only one 'space' and record
  // its coordinates, which 'space' is determined by which side 'E' is
  // located. No need to check for 'E' in a corner.

if ($e_col == sizeof($maze[0]) - 1){
    $maze[$e_row][$e_col - 1] = $c_count;
    $c_count++;
    $tmp_row = array($e_row);
    $tmp_col = array($e_col - 1);
  } else if ($e_col == 0){
    $maze[$e_row][$e_col + 1] = $c_count;
    $c_count++;
    $tmp_row = array($e_row);
    $tmp_col = array($e_col + 1);
  } else if ($e_row == sizeof($maze) - 1){
    $maze[$e_row - 1][$e_col] = $c_count;
    $c_count++;
    $tmp_row = array($e_row - 1);
    $tmp_col = array($e_col);
  } else {
    $maze[$e_row + 1][$e_col] = $c_count;
    $c_count++;
    $tmp_row = array($e_row + 1);
    $tmp_col = array($e_col);
  }

// goto the coordinate(s) that have been marked and mark its adjacent
  // 'spaces' if applicable (check for -1).

while (sizeof($tmp_row) != 0){
    $orig_size = sizeof($tmp_row);
    for ($i = 0; $i < $orig_size; $i++){
      // ckeck up
      if ($tmp_row[0] - 1 > 0){
        if ($maze[$tmp_row[0] - 1][$tmp_col[0]] == -1){
          $maze[$tmp_row[0] - 1][$tmp_col[0]] = $c_count;
          array_push($tmp_row, $tmp_row[0] - 1);
          array_push($tmp_col, $tmp_col[0]);
        } else if ($maze[$tmp_row[0] - 1][$tmp_col[0]] == "S"){
          break 2;
        }
      }
      // check down
      if ($tmp_row[0] + 1 < $b_bottom - 1){
        if ($maze[$tmp_row[0] + 1][$tmp_col[0]] == -1){
          $maze[$tmp_row[0] + 1][$tmp_col[0]] = $c_count;
          array_push($tmp_row, $tmp_row[0] + 1);
          array_push($tmp_col, $tmp_col[0]);
        } else if ($maze[$tmp_row[0] + 1][$tmp_col[0]] == "S"){
          break 2;
        }
      }
      // check left
      if ($tmp_col[0] - 1 > 0){
        if ($maze[$tmp_row[0]][$tmp_col[0] - 1] == -1){
          $maze[$tmp_row[0]][$tmp_col[0] - 1] = $c_count;
          array_push($tmp_row, $tmp_row[0]);
          array_push($tmp_col, $tmp_col[0] - 1);
        } else if ($maze[$tmp_row[0]][$tmp_col[0] - 1] == "S"){
          break 2;
        }
      }
      // check right
      if ($tmp_col[0] + 1 < $b_right - 1){
        if ($maze[$tmp_row[0]][$tmp_col[0] + 1] == -1){
          $maze[$tmp_row[0]][$tmp_col[0] + 1] = $c_count;
          array_push($tmp_row, $tmp_row[0]);
          array_push($tmp_col, $tmp_col[0] + 1);
        } else if ($maze[$tmp_row[0]][$tmp_col[0] + 1] == "S"){
          break 2;
        }
      }
      array_shift($tmp_row);
      array_shift($tmp_col);
    }
    $c_count++;
  }

 
  // fill the 2d array
 
  while (!feof($fp)){
    $ch = fgetc($fp);
    if (!feof($fp)){
      if ($ch == "W"){
        $maze[$row][$col] = $ch;
        $col++;
      } else if ($ch == " "){
        $maze[$row][$col] = -1;
        $col++;
      } else if ($ch == "n"){
        $row++;
        $col = 0;
      } else if ($ch == "S" || $ch == "E"){
        $maze[$row][$col] = $ch;
        if ($ch == "S"){
          $s_row = $row;
          $s_col = $col;
        } else {
          $e_row = $row;
          $e_col = $col;
        }
        $col++;
      }
    }
  }
  fclose($fp);
 
  // define boundries
  $b_right  = sizeof($maze[0]);
  $b_bottom = sizeof($maze);
 
  // start algorithm from 'E'. this will mark only one 'space' and record
  // its coordinates, which 'space' is determined by which side 'E' is
  // located. No need to check for 'E' in a corner.
 
  if ($e_col == sizeof($maze[0]) - 1){
    $maze[$e_row][$e_col - 1] = $c_count;
    $c_count++;
    $tmp_row = array($e_row);
    $tmp_col = array($e_col - 1);
  } else if ($e_col == 0){
    $maze[$e_row][$e_col + 1] = $c_count;
    $c_count++;
    $tmp_row = array($e_row);
    $tmp_col = array($e_col + 1);
  } else if ($e_row == sizeof($maze) - 1){
    $maze[$e_row - 1][$e_col] = $c_count;
    $c_count++;
    $tmp_row = array($e_row - 1);
    $tmp_col = array($e_col);
  } else {
    $maze[$e_row + 1][$e_col] = $c_count;
    $c_count++;
    $tmp_row = array($e_row + 1);
    $tmp_col = array($e_col);
  }
 
  // goto the coordinate(s) that have been marked and mark its adjacent
  // 'spaces' if applicable (check for -1).
 
  while (sizeof($tmp_row) != 0){
    $orig_size = sizeof($tmp_row);
    for ($i = 0; $i < $orig_size; $i++){
      // ckeck up
      if ($tmp_row[0] - 1 > 0){
        if ($maze[$tmp_row[0] - 1][$tmp_col[0]] == -1){
          $maze[$tmp_row[0] - 1][$tmp_col[0]] = $c_count;
          array_push($tmp_row, $tmp_row[0] - 1);
          array_push($tmp_col, $tmp_col[0]);
        } else if ($maze[$tmp_row[0] - 1][$tmp_col[0]] == "S"){
          break 2;
        }
      }
      // check down
      if ($tmp_row[0] + 1 < $b_bottom - 1){
        if ($maze[$tmp_row[0] + 1][$tmp_col[0]] == -1){
          $maze[$tmp_row[0] + 1][$tmp_col[0]] = $c_count;
          array_push($tmp_row, $tmp_row[0] + 1);
          array_push($tmp_col, $tmp_col[0]);
        } else if ($maze[$tmp_row[0] + 1][$tmp_col[0]] == "S"){
          break 2;
        }
      }
      // check left
      if ($tmp_col[0] - 1 > 0){
        if ($maze[$tmp_row[0]][$tmp_col[0] - 1] == -1){
          $maze[$tmp_row[0]][$tmp_col[0] - 1] = $c_count;
          array_push($tmp_row, $tmp_row[0]);
          array_push($tmp_col, $tmp_col[0] - 1);
        } else if ($maze[$tmp_row[0]][$tmp_col[0] - 1] == "S"){
          break 2;
        }
      }
      // check right
      if ($tmp_col[0] + 1 < $b_right - 1){
        if ($maze[$tmp_row[0]][$tmp_col[0] + 1] == -1){
          $maze[$tmp_row[0]][$tmp_col[0] + 1] = $c_count;
          array_push($tmp_row, $tmp_row[0]);
          array_push($tmp_col, $tmp_col[0] + 1);
        } else if ($maze[$tmp_row[0]][$tmp_col[0] + 1] == "S"){
          break 2;
        }
      }
      array_shift($tmp_row);
      array_shift($tmp_col);
    }
    $c_count++;
  }

#13

May 15th, 2002, 09:27 AM

diclophis

Join Date: Apr 2007

Location: Tampa. FL, USA

Posts: 35

Time spent in forums: < 1 sec
Reputation Power: 3

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

May 15th, 2002, 10:25 AM

jameadows

Join Date: Apr 2007

Location: Ashland, OR US

Posts: 7

Time spent in forums: < 1 sec
Reputation Power: 0

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

May 15th, 2002, 10:36 AM

pswitek

Join Date: Apr 2007

Location: Warsaw, Poland

Posts: 6

Time spent in forums: < 1 sec
Reputation Power: 0

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.

Thread Tools	Search this Thread
Email this Page	Search this Thread: Advanced Search
Display Modes	Rate This Thread
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode	Rate This Thread: