# Initial analysis

We are given again a server based programming challenge. When we connect to the server receive a 3D Maze and we must find the exit of the maze where we will see the flag. It’s similar to the previous Maze 2D challenge but now we are ‘in’ the maze and have to find our way out.

In this challenge, we must use ‘w’, ‘a’, ‘s’, ‘d’ to move in the maze. If we reconnect to the server we will see that the maze is randomly generated and if we move around in the map we could see that sometimes we receive some `Ascii art` like trollface and other known memes. If we receive one of the memes It means that in front of us there is a wall. We should always send one move at once because if we send an invalid or multiple moves at once we will be launched from the server and would have to start again.

# Cheating

If we move around in the maze we could notice that the server is cheating sometimes and puts us a wall in the direction where we are facing at. It is easy noticeable if we walk a hallway up and down and after the 10^th^ instruction we would see that it will put a wall in front of us. We must consider this and turn our player to point to a wall before we reach the 10^th^ move.

# Solution

A possible solution would be to brute force it and just to walk backwards until we find a ‘PAN{‘ in the received stream and if we get stuck we just have to disconnect and retry it again. It might take some execution time but because the map is generated randomly we could be lucky and get the flag easy but because this is a programming challenge we are going to solve it the proper way.

# Solution steps

1) connect to the server and receive data

2) parse the response image (try to identify the image by a unique string or calculate a hash)

3) choose a possible move and increment a counter so that we know when we must turn our player’s direction to a wall

4) save all visited positions so that we know where we have already been

5) see if the server would set a cheating-wall soon (e.g.: in next 4 steps) and walk back the known path so that we can guarantee that we can turn our player’s direction to a wall so that the cheating-wall will be set on an already known wall

6) use a maze solving algorithm to find a way out of the maze (e.g.: Trémaux’s algorithm, https://en.wikipedia.org/wiki/Maze_solving_algorithm#Tr.C3.A9maux.27s_algorithm)

# Solution in Python

``````#!/usr/bin/env python

import binascii
import socket
import sys

class WallType:
UNKNOWN = 0
WALL = 1
DEADEND = 2
HALLWAY = 3
LEFT = 4
RIGHT = 5
INTERSECTION = 6            # left or right
INTERSECTION_FORWARD = 7    # left, right or forward
INTERSECTION_LEFT = 8       # left or forward
INTERSECTION_RIGHT = 9      # right or forward
RND_IMAGE = 10

class MoveDirection:
FORWARD = 0
LEFT = 1
RIGHT = 2
BACK = 3
TURNAROUND = 4

class MazeSolver:
def __init__(self):
self.s = None
self.hostname = ""

self.nMoves = 0
self.position_x = 1
self.position_y = 1
self.dir = ">"
self.BUFFER_SIZE = 1024 * 4

self.maze_width = 21
self.maze_height = 21
self.visited = [[0 for x in range(self.maze_width + 1)] for y in range(self.maze_height + 1)]
self.visited[1][1] = 1
self.fSolved = False
self.Flag = None

self.visited_directions = []

self.directions = {"w": {">": [1, 0, ">"],
"^": [0, -1, "^"],
"V": [0, 1, "V"],
"<": [-1, 0, "<"]},
"s": {">": [-1, 0, ">"],
"^": [0, 1, "^"],
"V": [0, -1, "V"],
"<": [1, 0, "<"]},
"a": {">": [0, 0, "^"],
"^": [0, 0, "<"],
"V": [0, 0, ">"],
"<": [0, 0, "V"]},
"d": {">": [0, 0, "V"],
"^": [0, 0, ">"],
"V": [0, 0, "<"],
"<": [0, 0, "^"]},
}

self.buffer = None
self.current_wall = WallType.UNKNOWN
self.last_wall = WallType.UNKNOWN

def receiveData(self):
buffer = b''
self.last_wall = self.current_wall
self.current_wall = WallType.UNKNOWN
self.buffer = b''
while True:
buffer = b''
try:
buffer = self.s.recv(self.BUFFER_SIZE)
except Exception as e:
pass

self.buffer += buffer

#
# remove initial string
#
if self.nMoves == 0:
self.buffer = self.buffer[25:]
n = self.buffer.find('The possible moves')
if n != -1:
self.buffer = self.buffer[:n -1]

if self.isFlag(self.buffer):
break

self.current_wall = self.getWallType(self.buffer)
if self.current_wall != WallType.UNKNOWN:
break

return self.buffer

def isFlag(self, buffer):
if buffer.find('I want to play a game...') != -1:
return False

if buffer.find('PAN{') != -1:
self.fSolved = True
self.Flag = buffer
return True

return False

def getWallType(self, buffer):
crc = binascii.crc32(buffer) & 0xffffffff

try:
images = {
0x6651a34c:WallType.WALL,
0xaa801a18:WallType.LEFT,
0xfdea4ded:WallType.LEFT,
0xf9a8dfdb:WallType.RIGHT,
0x49f85041:WallType.RIGHT,
0x87ed9b2a:WallType.INTERSECTION_FORWARD,
0xd1c9cabc:WallType.INTERSECTION,
0x6b1094af:WallType.INTERSECTION_RIGHT,
0xb359512f:WallType.INTERSECTION_LEFT,
0x1c2d0dd9:WallType.INTERSECTION_FORWARD,
0x575b474e:WallType.INTERSECTION,
0x2acbd51c:WallType.HALLWAY,
0x33706043:WallType.DEADEND,
0x8805d93f:WallType.HALLWAY,    # deadway but far away
0x5e7857c1:WallType.HALLWAY,
0x42540965:WallType.HALLWAY,
0x6bee9d8d:WallType.HALLWAY,
0x836e026d:WallType.HALLWAY,
0xe0eb9db1:WallType.HALLWAY,
0x58da5c27:WallType.HALLWAY,
0xeb3208ce:WallType.RND_IMAGE,
0xaec3ea3c:WallType.RND_IMAGE,
0x226e2421:WallType.RND_IMAGE,
0xd821a70d:WallType.RND_IMAGE,
0xd41ab114:WallType.RND_IMAGE,
0x5dde57f2:WallType.RND_IMAGE
}
res = images[crc]
except Exception:
res = WallType.UNKNOWN

return res

def printMap(self):
for i in range(len(self.visited[0])) :
l = ""
for j in range(len(self.visited[0])):
if j == self.position_x and i == self.position_y:
l += self.dir
else:
if self.visited[i][j] >= 3:
l += 'x'
elif self.visited[i][j] >= 2:
l += '-'
elif self.visited[i][j]:
l += ' '
else:
l += '#'
print l

def getXYByDirections(self, directions):
new_x = self.position_x
new_y = self.position_y
new_pd = self.dir

for a in directions:
[mx, my, pd] = self.directions[a][new_pd]
new_x += mx
new_y += my
new_pd = pd

return new_x, new_y

def getVisitedCountByDirections(self, directions):
new_x, new_y = self.getXYByDirections(directions)

if (new_x >= 1) and (new_x < self.maze_width) and (new_y >= 1 and new_y < self.maze_height):
return self.visited[new_y][new_x]
return 0

def getNextDirection(self, accepted=['wasd']):
myitems = []
for c in accepted:
res = self.getVisitedCountByDirections(c)
if res <= 2:
myitems.append([c, res])

tmp = sorted(myitems, key=lambda x:x[1])

if len(tmp) > 0:
return tmp[0][0]

# no move found
return ''

def canIWalkThere(self, directions):
new_x, new_y = self.getXYByDirections(directions)

if new_x == 0 or new_y == 0 or self.visited[new_y][new_x] >= 3:
return False

return True

def markVisitedPath(self, directions):
new_x, new_y = self.getXYByDirections(directions)

if new_x == 0 or new_y == 0 or self.visited[new_y][new_x] >= 3:
return False

if self.visited[new_y][new_x] == 0:
self.visited[new_y][new_x] = 2
else:
self.visited[new_y][new_x] += 1
return True

def updatePosition(self, direction, addToVisited = True):
[mx, my, pd] = self.directions[direction][self.dir]
new_x = self.position_x + mx
new_y = self.position_y + my

if new_x == 0 or new_y == 0:
return False

if (new_x >= 1) and (new_x < self.maze_width) and (new_y >= 1 and new_y < self.maze_height):

if addToVisited:
if self.visited[new_y][new_x] == 0:
self.visited[new_y][new_x] = 1

self.position_x = new_x
self.position_y = new_y
self.dir = pd
else:
return False

return True

def sendDirection(self, direction, addToVisited = True):
old_posx = self.position_x
old_posy = self.position_y
old_dir = self.dir

self.s.sendall(direction + '\r\n')
self.visited_directions.append(direction)
self.nMoves += 1
self.receiveData()

if direction != 'a' and direction != 'd' and (self.last_wall == WallType.RND_IMAGE and self.current_wall == WallType.RND_IMAGE) or \
(self.last_wall == WallType.DEADEND and self.current_wall == WallType.DEADEND):
self.position_x = old_posx
self.position_y = old_posy
self.dir = old_dir
return False

self.updatePosition(direction, addToVisited)
return True

def sendDirections(self, directions, addToVisited = True, fSkipWall = True):
for a in directions:
posx = self.position_x
posy = self.position_y
olddir = self.dir

if fSkipWall:
self.skipWall()

self.sendDirection(a, addToVisited)

if a != 'w' and directions != 'aa' and directions != 'dd' and (self.current_wall == WallType.RND_IMAGE or self.current_wall == WallType.DEADEND):
self.position_x = posx
self.position_y = posy

if a == 'w' and self.current_wall == WallType.RND_IMAGE and self.last_wall == WallType.RND_IMAGE:
self.position_x = posx
self.position_y = posy

return True

def skipWall(self):
nStepsBeforeSkip = 4

if self.nMoves == 0 or (((self.nMoves + nStepsBeforeSkip) % 10) != 0):
return False

#
# we have now 4 steps a head so we can walk back the known path and set somewhere a the wall
#

last_cmd = self.visited_directions[len(self.visited_directions) - 1]
if last_cmd == 'a':
self.sendDirections('dwwwa', False, False)

elif last_cmd == 'd':
self.sendDirections('awwwd', False, False)

elif last_cmd == 'w':
self.sendDirections('s', False, False)

last_cmd = self.visited_directions[len(self.visited_directions) - 2]
if last_cmd == 'w':
self.sendDirections('d', False, False)
if self.current_wall != WallType.HALLWAY:
self.sendDirections('wwaw', False, False)
else:
self.sendDirections('dwaas', False, False)

elif last_cmd == 'a':
self.sendDirections('d', False, False)
if self.current_wall != WallType.HALLWAY:
self.sendDirections('wwaw', False, False)
else:
self.sendDirections('dwaas', False, False)

elif last_cmd == 'd':
self.sendDirections('a', False, False)
if self.current_wall != WallType.HALLWAY:
self.sendDirections('wwdw', False, False)
else:
self.sendDirections('awdds', False, False)

def move(self, dir):
fFoundWay = False
nInvalidDirections = 0

while fFoundWay == False and self.fSolved == False:
if nInvalidDirections >= 2:
dir = MoveDirection.TURNAROUND

if dir == MoveDirection.FORWARD:
# go forward
if self.sendDirections('w'):
fFoundWay = True
else:
dir = MoveDirection.LEFT

if dir == MoveDirection.LEFT:
#
# test if we can walk to the left or if its disabled
#
if self.canIWalkThere('wa'):

# go forward one step and then to the left
if self.sendDirections('wa'):
fFoundWay = True
else:
dir = MoveDirection.RIGHT
else:
dir = MoveDirection.RIGHT
nInvalidDirections += 1

if dir == MoveDirection.RIGHT:
if self.canIWalkThere('wd'):
if self.sendDirections('wd'):
fFoundWay = True
else:
dir = MoveDirection.FORWARD
else:
dir = MoveDirection.LEFT
nInvalidDirections += 1

if dir == MoveDirection.TURNAROUND:
if self.sendDirections('aa'):
fFoundWay = True
else:
break

return fFoundWay

def explore(self, buffer):
if self.nMoves == 0:
self.receiveData()

if self.current_wall == WallType.HALLWAY:
self.move(MoveDirection.FORWARD)

elif self.current_wall == WallType.LEFT:
self.move(MoveDirection.LEFT)

elif self.current_wall == WallType.RIGHT:
self.move(MoveDirection.RIGHT)

elif self.current_wall == WallType.INTERSECTION:
# left or right
m = self.getNextDirection(['wdw', 'waw'])
if m == 'waw':
self.markVisitedPath('waw')
self.markVisitedPath('s')
self.move(MoveDirection.LEFT)
elif m == 'wdw':
self.markVisitedPath('wdw')
self.markVisitedPath('s')
self.move(MoveDirection.RIGHT)
else:
self.move(MoveDirection.FORWARD)
return False

elif self.current_wall == WallType.INTERSECTION_FORWARD:
# left, right, forward
m = self.getNextDirection(['ww', 'waw', 'wdw'])
if m == 'waw':
self.markVisitedPath('waw')
self.markVisitedPath('s')
self.move(MoveDirection.LEFT)
elif m == 'wdw':
self.markVisitedPath('wdw')
self.markVisitedPath('s')
self.move(MoveDirection.RIGHT)
elif m == 'ww':
self.move(MoveDirection.FORWARD)
else:
return False

elif self.current_wall == WallType.INTERSECTION_LEFT:
# left or forward
m = self.getNextDirection(['ww', 'waw'])
if m == 'waw':
self.markVisitedPath('waw')
self.markVisitedPath('s')
self.move(MoveDirection.LEFT)
elif m == 'ww':
self.move(MoveDirection.FORWARD)
else:
return False

elif self.current_wall == WallType.INTERSECTION_RIGHT:
# right or forward
m = self.getNextDirection(['ww', 'wdw'])
if m == 'wdw':
self.markVisitedPath('wdw')
self.markVisitedPath('s')
self.move(MoveDirection.RIGHT)
elif m == 'ww':
self.move(MoveDirection.FORWARD)
else:
return False

elif self.current_wall == WallType.WALL:
m = self.getNextDirection(['waw', 'wdw'])
if m == 'waw':
self.move(MoveDirection.LEFT)
elif m == 'wdw':
self.move(MoveDirection.RIGHT)

elif self.current_wall == WallType.DEADEND:
self.move(MoveDirection.FORWARD)    # make sure that the flag isn't in front of us
self.move(MoveDirection.TURNAROUND)

elif self.current_wall == WallType.RND_IMAGE:
#
# oh well, thats a problem.
# try anything..
#
m = self.getNextDirection(['waw', 'wdw', 'ww', 'waaw'])
if m == 'wdw':
self.move(MoveDirection.RIGHT)
elif m == 'ww':
self.move(MoveDirection.FORWARD)
elif m == 'waw':
self.move(MoveDirection.LEFT)
elif m == 'waaw':
self.move(MoveDirection.TURNAROUND)
else:
self.move(MoveDirection.FORWARD)

elif self.current_wall == WallType.UNKNOWN:
print "unknown image2: ", buffer
return False

return True

def solve(self, hostname):
self.hostname = hostname
self.s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
self.s.connect((hostname, 16000))
# self.s.settimeout(0.1)

while self.fSolved == False and self.nMoves < 5000:
if self.explore(self.buffer) == False:
print "ok no solution found, bye"
break
self.printMap()
print "flag: {}".format(self.Flag)

def solve_maze3d(hostname='localhost'):
solver = MazeSolver()
solver.solve(hostname)

if __name__ == "__main__":
if len(sys.argv) > 1:
solve_maze3d(sys.argv[1])
else:
#print "maze2d_solution.py <hostname>"
solve_maze3d("34.211.117.64")

``````

# Running the script

If we run the script we will see the flag in most cases but sometimes it won’t work and that’s because of a bug which occurs when we walk back in our map to skip the cheating-wall. If we walk back and the new position is an intersection and we would turn to left or right, then we would set a wall there and block the intersection. That means that we are caught forever! But if it works it would show us the maze and the flag (aka Pancopter):