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