Page 1 of 2

Lazy Maze

Posted: Tue Nov 04, 2008 4:09 am
by paradox.is.taken
In case the admins are wondering about why I went though the maze two times, and the first time completely covered the whole maze...my program was looking for the string "edge" and considering it as a falure... which was quite unfortunate when it was contained in the password :)

btw, I was amazed how simple my program was at the end. At first I had matrix and kept track of everything, and was going to traverse it myself with keyboard input... at the end i just needed to keep track of the crossroads and the current string...

Posted: Tue Nov 04, 2008 11:41 am
by gfoot
I just used my flood fill code, making it support the maze size being in memory before the actual maze, making it start from the right corner, and making it output the directions it took after it escapes from the maze. Actually I think I made it start at the finish, so the directions could be output in the right order by simply walking up the stack. Neat.

Posted: Tue Nov 04, 2008 4:36 pm
by Allosentient
I actually drew a map using Windows GDI, and used the map to determine if there were flaws in my code

Posted: Tue Nov 04, 2008 7:57 pm
by gfoot
Sorry, I got mixed up with "Labyrinth". Lazy Maze I just solved by methodically adding different letters to the string until it found the only way out.

Posted: Sun Nov 16, 2008 1:46 am
by sigi
This is a straightforward depth-first search, very comprehensively expressed in Ruby:

Code: Select all

#!/usr/bin/ruby

require 'open-uri'
NAME = 'username'; PW = 'password'
BASE_URI = "http://www.hacker.org/challenge/misc/maze.php?name=#{NAME}&password=#{PW}&steps="
moves = ['D']

while( not moves.empty? )
        puts( current = moves.pop )
        result = open(BASE_URI + current).read
        if result =~ /keep moving/
            %w{L R U D}.each {|d| moves.push( current + d )}
        elsif not result =~ /(boom|off the edge)/
            puts result
            exit
        end
end

Posted: Sun Nov 16, 2008 1:58 am
by tails
gfoot wrote:Lazy Maze I just solved by methodically adding different letters to the string until it found the only way out.
That's neat! I didn't think of it.

I used the right hand method on both Lazy Maze and Labyrinth. It should be somewhat more effective than flooding.

Posted: Sun Nov 16, 2008 3:25 am
by sigi
I'm pretty sure that gfoot also used the "right hand method" (backtracking), he only called it "methodically adding letters".

If you only add letters and never backtrack it's impossible to find a solution in the general case.

Gfoot, maybe you could clarify on what exactly you did to solve this.

Posted: Sun Nov 16, 2008 5:33 am
by tails
I thought gfoot did just the same as your code above does. And it's not the right hand method, I think.

Posted: Sun Nov 16, 2008 6:46 am
by sigi
tails wrote:I thought gfoot did just the same as your code above does. And it's not the right hand method, I think.
No, you are right. Backtracking and Right/Left-Hand methods are different. (Both have in common that they don't necessarily find the optimal solution).

The only reason why I've used the depth-first search is that it's really easy to specify and implement (within the challenge conditions of not knowing anything about the maze and being strictly constrained to solution-string checking).

How would you formulate the right-hand method in Python for the given challenge (taking into account that one always submits a complete string tracing the current solution from the start)?

Posted: Sun Nov 16, 2008 11:05 am
by gfoot
I did exactly what sigi's code does, but recursively.

I imagine the right-hand method is harder to implement, because you need to special-case the backtracking (you're not allowed to go xxxDU for example, you need to contract it to just xxx).

Posted: Wed Mar 25, 2009 7:01 pm
by megabreit
Here's my solution in perl (very similar to the one by sigi):

Code: Select all

#!/usr/bin/perl

use LWP::Simple;

my $url='http://www.hacker.org/challenge/misc/maze.php?name=NAME&password=PASSWORD&steps=';

my $path="D";
my @backtrack;
my @directions=qw( U D L R);
my %opposite=("U"=>"D", "D"=>"U", "L"=>"R", "R"=>"L");
my $content;

while (true) {
        foreach $dir (@directions) {
                next if ( substr($path,length($path)-1,1) eq $opposite{$dir} ); # don't turn around
                push @backtrack,"$path$dir";
        }
        while (true) {
                $path=pop @backtrack;
                $content = get "$url$path";
                die "Couldn't get $url" unless defined $content;
                $content=~ s/<[^>]*>//gs;
                $content=~ s/\n//gs;
                last if ($content ne "boom");
        }
        if ($content ne "keep moving...") {
                print "The End: $content\n";
                last;
        }
}
It's basically the backtracking algorithm. The little "improvement" is, that useless U-turns are skipped.

maze image

Posted: Wed May 20, 2009 8:21 pm
by Hamstaro
Here is a picture how the maze looked like when i solved it. The red point is the exit. I just forgot to mark the start point.

Image

Posted: Wed Jul 22, 2009 8:38 am
by fido2509
Hi,

I solved the maze manually with some support of pen and paper.

That way I chose because the server didn't answer correctly on my requests.
I used PHP with fsockopen(..). I included cookies, referer, user-agent, accept-encoding and all the headerlines firefox uses too. But instead of "keep walking.." and "boom" I got blank pages. with blank I mean HTTP Headers followed by <html><body>\r\n and thats all, meaning EOF($socket) occured.

Could someone please hint me how to get a usable answer?
I solved the maze already, but I want to know why my program didn't work.

Sources at LazyMaze.zip (3kB)

Oh, btw I used a simple DFS to get through.

Fido

Posted: Sat Sep 12, 2009 3:53 pm
by bearson
a short bash script will do, if you have w3m (or curl, etc.) installed :p

Code: Select all

trypath() {
	printf "Try: %s " $1
	res=`w3m -dump 'http://www.hacker.org/challenge/misc/maze.php?steps='$1`
	echo $res
	if echo $res | grep moving &>/dev/null; then
		for i in U D L R; do trypath $1$i; done
	fi
}

trypath 'D'

Posted: Tue Nov 24, 2009 2:35 am
by matter
fido2509 wrote:Hi,

I solved the maze manually with some support of pen and paper.

That way I chose because the server didn't answer correctly on my requests.
I used PHP with fsockopen(..). I included cookies, referer, user-agent, accept-encoding and all the headerlines firefox uses too. But instead of "keep walking.." and "boom" I got blank pages. with blank I mean HTTP Headers followed by <html><body>\r\n and thats all, meaning EOF($socket) occured.

Could someone please hint me how to get a usable answer?
I solved the maze already, but I want to know why my program didn't work.

Sources at LazyMaze.zip (3kB)

Oh, btw I used a simple DFS to get through.

Fido
For PHP, use "file_get_contents($url)" to retrieve a URL. In this case, the URL is "http://www.hacker.org/challenge/misc/ma ... teps=DRRDD", plus the rest of the path on the end. Don't need PHP session, cookies, headers, or anything.

file_get_contents() returns the contents of the page (e.g. <head><body>\r\nboom). So you can easily just check that.