Initial analysis

We are given a server based programming challenge. When we connect to the server we receive a maze challenge and we must find the shortest path from ‘>’ to ‘X’. We must use ‘>’, ‘<’, ‘V’ and ‘^’ to move in the maze.

We can probably solve it manually but after first solved maze it will give us another maze to solve.

We don’t know how many mazes the server will send us and the maze is also generated randomly so we should write a script for it.

Task

Our script must connect to the server, parse the response and send back the correct path.

The maze itself is built with only four characters. ‘#’ and space character are used for the map, ‘>’ indicates the starting point and ‘X’ our end.

To find the shortest path from our starting point to the end we could use Dijkstra’s algorithm but for that we must build a graph. The distance to each other node is 1. To build a graph we must go through each line and add a node every time we see a space character and ignore the # character.

As final step, we must translate our path to a string containing of V, ^, > and <.

Solution steps

1) Connect to the server and receive data

2) Parse maze into a graph

3) Find start and end in the graph

4) Find shortest way from start to end using Dijkstra’s algorithm (distance to each node is 1)

5) Convert our path to a directions string using ‘<’, ‘>’, ‘V’ and ‘^’

Solution in Python

#!/usr/bin/env python

import socket
import sys
from collections import defaultdict

class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = defaultdict(list)
        self.distances = {}

    def add_node(self, value):
        self.nodes.add(value)

    def add_edge(self, from_node, to_node, distance):
        self.edges[from_node].append(to_node)
        self.edges[to_node].append(from_node)
        self.distances[(from_node, to_node)] = distance

def dijkstra(graph, initial):
    visited = {initial: 0}
    path = {}

    nodes = set(graph.nodes)

    while nodes:
        min_node = None
        for node in nodes:
            if node in visited:
                if min_node is None:
                    min_node = node
                elif visited[node] < visited[min_node]:
                    min_node = node

        if min_node is None:
            break

        nodes.remove(min_node)
        current_weight = visited[min_node]

        for edge in graph.edges[min_node]:
            try:
                weight = current_weight + graph.distances[(min_node, edge)]
            except:
                continue

            if edge not in visited or weight < visited[edge]:
                visited[edge] = weight
                path[edge] = min_node

    return visited, path

def find_shortest_path(g, start, end):
    #
    # generate a path and then walk from the end to the start position and make a list out of it
    #
    visited, path = dijkstra(g, start)
    backpath = [end]
    
    while end != start:
        end = path[end]
        backpath.append(end)
    path = list(reversed(backpath))

    return path

def translate_direction(old, n):
    #
    # based on previous and current position it translates the given path to directions
    #
    [x, y] = map(int, n.split(":"))
    [old_x, old_y] = map(int, old.split(":"))

    if x == (old_x + 1):
        # right
        return "V"
    elif x == (old_x - 1):
        # left
        return "^"
    elif y == (old_y + 1):
        # forward
        return ">"
    elif y == (old_y - 1):
        # backwards
        return "<"

def translate_path_to_directions(path):
    result = ""
    for i in range(1, len(path)):
        result += translate_direction(path[i - 1], path[i])
    return result

def find_path(buf):
    lines = buf.strip().split('\n')

    start = ""
    end = ""

    #
    # create a graph, each node will be saved in this format: 'X:Y'
    #
    g = Graph()

    next_pos = [
        [1, 0],     # down (V)
        [-1, 0],    # up (^)
        [0, 1],     # right (>)
        [0, -1]     # left (<)
    ]

    #
    # go through element which is not '#' (because we ignore walls)
    #
    for i in range(len(lines)):
        for j in range(len(lines[0])):
            if lines[i][j] != '#':
                #
                # search for start and end position
                #
                if lines[i][j] == '>':
                    start = "{}:{}".format(i, j)
                elif lines[i][j] == 'X':
                    end = "{}:{}".format(i, j)

                pos = "{}:{}".format(i, j)
                if pos not in g.nodes:
                    g.add_node(pos)

                #
                # go through all next elements (left, right, up and down)
                #
                for k in next_pos:
                    new_x = i + k[0]
                    new_y = j + k[1]

                    #
                    # make sure we are not out of the maze and add the edge to the current node
                    #
                    if (new_x >= 0) and (new_x < len(lines)) and (new_y >= 0) and (new_y < len(lines[0])):
                        new_pos = "{}:{}".format(new_x, new_y)
                        if new_pos not in g.nodes:
                            g.add_node(new_pos)
                        g.add_edge(pos, new_pos, 1)

    path = find_shortest_path(g, start, end)
    return translate_path_to_directions(path)

def solve_maze2d(hostname='localhost'):
    #
    # connect to the server, read data from socket and skip 'Now go!' to have the maze in buffer
    #
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect((hostname, 16000))

    buffer = s.recv(1024 * 10)
    n = buffer.find('Now go!')
    if n == -1:
        return

    buffer = buffer[n + 9:]

    ncount = 1

    while True:
        #
        # find shortest path for given maze and send the result back to the server
        #
        path = find_path(buffer)

        print "Path {}: {}".format(ncount, path)
        s.send(path)

        #
        # receive data and test if we have the correct path
        #
        buffer = s.recv(1024 * 10)

        if (buffer.find("Incorrect path!") != -1) or (buffer.find("Invalid command!") != -1):
            print "Wrong: {}".format(buffer)
            return
        elif buffer.find("Now solve dis") == 0:
            buffer = buffer[18:]
            ncount += 1
            continue

        print "Flag: {}".format(buffer)
        break

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

Running the script

Now we can run our script and we should receive the flag:

$ python maze2d_solution.py localhost

Path 1:
VVVVVVVVVVVVVVVVVVVV>>VV<<VV>>>>VV>>VV>>>>>>^^^^>>VVVV>>^^>>^^^^<<^^^^^^<

Path 2:
>>>>>>>>>>>>VV>>>>>>>>VV<<VVVVVV>>VVVV>>VV>>>>^^<<^^^^>>VV>>VVV

Path 3:
>>>>>>>>VVVVVV>>VVVV<<<<^^<<<<

Path 4:
VVVVVV>>VVVV>>>>>>VV<<<<<<<<VVVVVV>>VVVVVV<<VVVV>>>>^^>>>>^^<<^^<<^^>>>>VV>>VV>>^^^^<<^^>>^^^^^^<<VV<<<<<<<<VV>>>>VV>>

Path 5:
>>>>>>>>VV>>^^>>VV>>^^>>>>VVVV<<VVVV>>^^>>^^>>^^^^>>>>VVVV<<VV<<VV>>>>

Flag: You're aMAZEing! (See what we did there? hehehe)
PAN{my_f1rst_labyM4z3.jpeg}