# 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.

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 = {}

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:

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

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}
``````