Lazy Maze

markobr · Post by **markobr** » Wed Jun 16, 2010 3:09 pm

I solved it with pen and paper which actually wasn't that time-consuming once I knew some properties of the maze and correctly guessed where the exit might be.

MyNameIsAlreadyTaken · Mon Oct 25, 2010 9:27 pm

I solved it in C++ with a simple backtracking algorithm - it took some time to get libcurl to work as I want it to, after that the program was written very fast. It took an hour to compute the solution, since it took always about 4 or 5 seconds until I got a respond from the server. Is there a way to make that work faster? I used the same handle over and over again, but it was still slow as hell.

seampaul · Post by **seampaul** » Tue Jan 25, 2011 3:47 pm

i solved it by c# and gdi+

seampaul · Post by **seampaul** » Tue Jan 25, 2011 4:29 pm

this is a recored of my application
http://www.youtube.com/watch?v=gcgbrT6ytJ8

nahnoe · Post by **nahnoe** » Tue Jun 14, 2011 4:58 pm

Solved this with exactly the same problem as OP.. I was also looking for "edge".

I used a DFS with a few optimisations. The first was avoiding checking "opposites" such as UD or LR, the second was avoiding visited positions (which I think saved a lot of time) and the third was recording the edge of the maze when it hit it although I didn't use this in the end.

Solved with Perl.. I won't post the code because it's pretty ugly

moose · Post by **moose** » Wed Jul 13, 2011 6:05 am

You could use some kind of backtracking-algorithm. So it would be possible to give the program a string (e.g. "DDDDULURRR") and define an order (D -> U -> L -> R) and it could determine which should be next, without knowing which combinations were used before:

Try to add "D" to the string -> if it works, keep on
If it doesn't work, incement DDDDULURRR. As R is the biggest one, you get DDDDULL

You could also build a number converter to base 4:
D = 3, U=2, L=1, R=0
and then count up. This is very inefficient and would not end with this size (4^121), but I'm quite sure this method can be adjusted.

Here is my bit of python. I made a very simple program, but I guess there is no better method of solving it (that means a method with less server-calls):

Code: Select all

#!/usr/bin/python
# -*- coding: utf-8 -*-

import urllib, sys
from copy import deepcopy

sendto = "http://www.wechall.net/challenge/Z/blackhattale/login.php?action=login&"
cookie = 'PHPSESSID=%s;phpbb2mysql_data=%s;phpbb2mysql_sid=%s;phpbb2mysql_t=%s'

def get(url,cookie):
    u=urllib.URLopener();u.addheader('Cookie',cookie);x = u.open(url)
    return x.read()

def move(direction, cookie):
    raw = get('http://www.hacker.org/challenge/misc/maze.php?steps='+direction, cookie)
    raw = raw.split("<html><body>\n")
    return raw[1].strip()

def makeMove(correct, cookie, currentPos):
    lastStep = correct[-1]
    for i in ['U', 'D', 'L', 'R']:
        if (lastStep == 'U' and i == 'D') or (lastStep == 'D' and i == 'U') and (lastStep == 'L' and i == 'R') and (lastStep == 'R' and i == 'L'):
            continue
        tmp = correct + i
        got = move(tmp, cookie)
        if got != 'boom' and got != 'off the edge of the world':
            if i == 'U':
                c = [currentPos[0],currentPos[1]+1]
            elif i == 'D':
                c = [currentPos[0],currentPos[1]-1]
            elif i == 'L':
                c = [currentPos[0]-1,currentPos[1]]
            elif i == 'R':
                c = [currentPos[0]+1,currentPos[1]]
            print("(%i|%i), %s\t%s" % (c[0], c[1], correct, got))
            if got != 'keep moving...':
                sys.exit()
            makeMove(tmp, cookie, deepcopy(c))

print "Ok, service started"

makeMove('D', cookie, [0,0] )

IIMOG · Post by **IIMOG** » Wed Sep 14, 2011 9:20 pm

I used Java and a stack datastructure for backtracking.

gandhi · Post by **gandhi** » Tue May 07, 2013 8:17 am

did it with prolog.

Prolog has "built-in" backtracking, which made the task pretty easy:

:- use_module(library('http/http_client')).
:- use_module(contains).

solve(STEPS) :-
URL = 'http://www.hacker.org/challenge/misc/maze.php?steps=',
concat(URL,STEPS,URLSTEPS),
http_get(URLSTEPS, REPLY, []),
(concat(STEPS, 'D', NEWSTEPS);
concat(STEPS, 'U', NEWSTEPS);
concat(STEPS, 'L', NEWSTEPS);
concat(STEPS, 'R', NEWSTEPS)),
(contains(REPLY,'keep moving');
solution(REPLY)),
solve(NEWSTEPS).

solution(REPLY) :-
\+ contains(REPLY,'keep moving'),
\+ contains(REPLY,'boom'),
\+ contains(REPLY,'off the edge'),
write(REPLY).

yourMom · Post by **yourMom** » Sun Aug 11, 2013 3:56 pm

Python anyone?

Code: Select all

import requests

base_url = "http://www.hacker.org/challenge/misc/maze.php?steps="

def dfs(cur):
	r = requests.get(base_url + cur);
	print cur
	
	if r.content.find('boom') >= 0:
		return
	elif r.content.find('keep moving') >= 0:
		dfs(cur + 'L')
		dfs(cur + 'R')
		dfs(cur + 'D')
		dfs(cur + 'U')
	else:
		print r.content
		sys.exit()

Begin searching with:

Code: Select all

dfs('')

Hippo · Post by **Hippo** » Tue Apr 01, 2014 9:30 pm

Main part of my code ... I am surprised nobody was scared of possible loops in the maze (at least at the solutions I have seen). I have tracked reachable positions ... I let here comment in my native language

Code: Select all

url="http://www.hacker.org/challenge/misc/maze.php?steps="

def main(args):
  dirs = 'ULDR'
  path = ""
  minX=0;maxX=0;posX=0
  minY=0;maxY=0;posY=0
  dir = ' '
  difs = ((0,1),(-1,0),(0,-1),(1,0))
  reached = {(posX,posY)}
  response=urllib2.urlopen(url+"D")
  body = response.read()
  responses = {body}
  responsefor = {"D"}
  msg_cont = body
  # mozna bude potreba IDA, abychom neminuli nejaky blizky cil,
  # nejprve bych ale vyzkousel DFS
  cont = True
  statcnt=80
  while len(path)>0 or cont:
     statcnt+=1
     if statcnt==100:
        statcnt=0
        for y in xrange(maxY,minY-1,-1):
           msg=""
           for x in xrange(minX,maxX+1):
              msg=msg+'#.'[(x,y)in reached]
           print msg
     if cont:
        ind=0
     else:
        dir = path[-1]
        #print "backing "+path+"(%d,%d)" % (posX,posY)
        path = path[:-1]
        ind = dirs.index(dir)
        posX-=difs[ind][0]
        posY-=difs[ind][1]
        ind +=1
     cont = False
     if ind<4:
        path = path+dirs[ind]
        posX+=difs[ind][0]
        posY+=difs[ind][1]
        if not (posX,posY) in reached:
           if posX<minX:
              minX=posX
           if posX>maxX:
              maxX=posX
           if posY<minY:
              minY=posY
           if posY>maxY:
              maxY=posY
           responded = False
           while not responded:
              try:
                 response=urllib2.urlopen(url+path)
                 responded = True
              finally:
                 if not responded:
                    statcnt+=1
                    if statcnt==100:
                       statcnt=0
                       print "Connection problems. State so far:\n"
                       for y in xrange(maxY,minY-1,-1):
                          msg=""
                          for x in xrange(minX,maxX+1):
                             msg=msg+'#.'[(x,y)in reached]
                          print msg             
           body = response.read()
           if not body in responses:
              responses = responses | {body}
              responsefor = responsefor | {path}
              print path+":\n"+body
           if body == msg_cont:
              cont = True
              reached = reached | {(posX,posY)}
  print responses
  print responsefor
  for y in xrange(maxY,minY-1,-1):
     msg=""
     for x in xrange(minX,maxX+1):
        msg=msg+'#.'[(x,y)in reached]
        print msg

reesylou · Post by **reesylou** » Fri Mar 16, 2018 12:46 pm

Really enjoyed this one. This was the first of the challenges out of the 90ish so far that I actually wrote code for. There are others I will need to, but up until now I haven't needed to.

I chose to try with Python, which I haven't really used before and it worked really well. The code wasn't anything fancy, just a recursive DFS (recurse if the page returned the Keep moving)... ignoring booms, and outputting the path and the returned string for anything else. I didn't even bother optimizing it at all.

Hippo · Post by **Hippo** » Sun Mar 18, 2018 2:56 pm

moose wrote:

Code: Select all

        if (lastStep == 'U' and i == 'D') or (lastStep == 'D' and i == 'U') and (lastStep == 'L' and i == 'R') and (lastStep == 'R' and i == 'L'):
            continue

I suppose the typo is just here, otherwise I would expect the code to loop forever.
I cannot see marking visited places so the tree structure of the maze prevented cycling.