Lazy Maze

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

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

[Allosentient]

I actually drew a map using Windows GDI, and used the map to determine if there were flaws in my code

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

[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

[tails]

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.

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

[tails]

I thought gfoot did just the same as your code above does. And it's not the right hand method, I think.

[sigi]

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

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

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

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

[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

[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'

[matter]

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.