Lazy Maze
- MyNameIsAlreadyTaken
- Posts: 31
- Joined: Sun Oct 17, 2010 10:21 am
- Location: Germany
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.
this is a recored of my application
http://www.youtube.com/watch?v=gcgbrT6ytJ8
http://www.youtube.com/watch?v=gcgbrT6ytJ8
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
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
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:
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):
- 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
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] )
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).
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).
Python anyone?
Begin searching with:
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()
Code: Select all
dfs('')
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
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.
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.
I suppose the typo is just here, otherwise I would expect the code to loop forever.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 cannot see marking visited places so the tree structure of the maze prevented cycling.