The time draws near - Codewalkers

Codewalkers Forums Sponsor:

You don't need a fax machine to get faxes. Get a fax-to-email fax number from CallWave. Try it free.

May 14th, 2002, 07:40 AM

EvilivE

Join Date: Apr 2007

Location: Milwaukee, WI USA

Posts: 291

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

RE: The time draws near

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

May 14th, 2002, 10: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: 24

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, 11:01 AM

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, 05:34 PM

Anonymous

Registered User

Join Date: Apr 2007

Posts: 22,309

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

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, 06: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, 06:15 PM

Anonymous

Registered User

Join Date: Apr 2007

Posts: 22,309

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

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, 06:49 PM

diclophis

Join Date: Apr 2007

Location: Tampa. FL, USA

Posts: 35

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

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, 06:51 PM

Anonymous

Registered User

Join Date: Apr 2007

Posts: 22,309

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

RE: The time draws near

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

May 14th, 2002, 07: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, 09: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, 07:43 AM

Anonymous

Registered User

Join Date: Apr 2007

Posts: 22,309

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

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, 08:19 AM

EvilivE

Join Date: Apr 2007

Location: Milwaukee, WI USA

Posts: 291

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

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){