Maze solver (PAN CTF 2017, programming 1)

maze1.txt

###########
#>        #
# # ##### #
# # #     #
# # #X### #
# # # # # #
# ### # # #
# #   #   #
# # ### ###
#   #     #
###########

maze2.txt

#############
#>    #     #
# ### # ### #
#   # #   # #
# # # ##### #
# # #       #
# ######### #
#       #   #
# ### ### ###
#   #     # #
### ####### #
#   #   #   #
# ### # # # #
# #   # # # #
# ### # # # #
# #   # # # #
# # ### # ###
# # #   #   #
# # ### ### #
# #   #     #
# # # #######
# # #       #
# ######### #
#         # #
######### # #
#   #X  #   #
# ### # ### #
#   # # #   #
# # # # # ###
# #   #     #
#############

maze3.txt

###################
#>      #       # #
# ##### ### ### # #
# #   #     # # # #
### ######### # # #
#             #   #
######### # ##### #
#   X     # #   # #
# ########### # # #
# #           #   #
# # ###############
# #   #       #   #
# ### ### # # ### #
#   #   # # #     #
# # ### ### ##### #
# #   #     # #   #
# ### ####### # ###
# #   #       # # #
# ##### # ##### # #
# #   # # #   #   #
# # # # # # # ### #
#   #   #   #     #
###################

maze4.txt

###########
#>  #     #
# # # ### #
# # #   # #
### # # ###
#   # #   #
# ####### #
#     #X  #
##### # # #
#       # #
###########

maze4b.txt

###############
#>  #         #
# # # #########
# # #         #
# # ######### #
#   #       # #
# ### ##### # #
# #   #   # # #
# # ### ### # #
# # #         #
# # ######### #
# #     X # # #
# ####### # # #
#         # # #
########### # #
#     #   # # #
### # # # # # #
#   #   #   # #
# ########### #
#     #       #
# ### # #######
#   #         #
###############

maze5.txt

#############################
#>  #       #     #         #
# # ### ### # ### # ### #####
# #     # #   #   #   #     #
# ####### ##### ####### ### #
#   #         #   #   # #   #
# # # ##### ##### # # ### ###
# # # #   #     #   #   #   #
### # # # ### ######### ### #
#   #   #   #     #   #   # #
# ######### ### ### # ### # #
# #       #   #     # #   # #
# # ##### ### ####### # ### #
# #   # # #   #   #   #     #
# ### # # # ##### # ####### #
#   # # # #       #       # #
# # # # # # ########### ### #
# # #   # # #    X      #   #
# ##### # # # ########### ###
#       #   #               #
#############################

maze6.txt

#########################
#>  #           #       #
# # # ######### # # ### #
# # #   #   #   # # # # #
# # ### ### # ### # # # #
# #     #   #   # # #   #
# ####### # ### ### ### #
#         # # #   #   # #
##### ##### # ### ### # #
#     #   #     #     # #
# ### # # ##### ####### #
# #   # #   #     #   # #
# ##### ### ##### # # # #
# #     # #   #     # # #
# # ##### ### ##### ### #
# # #     # #     # #   #
# # ### # # ##### ### ###
# #     # #     #   #   #
# ####### # ### ### ### #
#   #   # #  X#   # #   #
# ### # # ####### # # ###
#     #           #     #
#########################

maze7.txt

###########
#>        #
# ### ### #
#   #   # #
### # # # #
#   # # # #
# ##### # #
# #     # #
# ###X### #
#     #   #
###########

maze8.txt

#############################
#>  #     # #   #         # #
# # # ### # # # # ##### # # #
# #   #   #   #   #   # #   #
# ##### ########### # # ### #
#     #         #   #   # # #
# ### ######### # ####### # #
# # # #     #   #   #     # #
# # # # # ### ##### # # ### #
#   #   #   # #     # #     #
### ####### # # ##### #######
#   #       #   # X # #   # #
# ### ########### # # # # # #
# # #   #         # #   # # #
# # ### # # # ########### # #
# #   #   # # #         #   #
# # # ##### ### ##### ##### #
#   #     #         #       #
#############################

maze9.txt

###############
#>  #   #   # #
# # # # # # # #
# # # #   # # #
# # # ##### # #
#   # #   # # #
# ### ### # # #
# #   #   #X# #
# # ### ### # #
#   #     # # #
##### ### # # #
#   # # # #   #
# # # # # ### #
# #     #     #
###############

maze_client.py

from socket import create_connection
import mz

MAZE_SERVER = ('54.69.145.229', 16000)
RECV_SIZE = 8192


def main():
    conn = create_connection(MAZE_SERVER)
    response = conn.recv(RECV_SIZE)
    while True:
        print response
        if "Now " not in response:
            return

        response_lines = response.splitlines()
        find_delim = [x for x in response_lines if x.startswith('Now')][0]
        maze_lines = response_lines[response_lines.index(find_delim)+2:-1]
        maze_text = '\n'.join(maze_lines)

        # Do your thing here with either maze_text or maze_lines.
        maze = mz.Maze(maze_lines)
        solutions = mz.search(maze, *maze.get_startpos())
        solutions.sort(lambda x, y: cmp(len(x), len(y)))
        solution = solutions[0]

        #solution = raw_input("Your solution: ")
        if not len(solution):
            return
        print solution
        conn.send(solution)

        response = conn.recv(RECV_SIZE)


if __name__ == '__main__':
    main()

mz.py

import sys
import os
from time import sleep

class Maze:
	def __init__(self, lines):
		self.maze = [l.strip() for l in lines]
		self.startpos = self.get_startpos()
		pass

	def get_startpos(self):
		for y, l in enumerate(self.maze):
			for x, c in enumerate(l):
				if c not in '#X ':
					return x, y

	def render(self, hx, hy):
		m = ''
		for y, l in enumerate(self.maze):
			s = [c for x, c in enumerate(l)]
			if hy == y:
				s[hx] = '.'
			m += ''.join(s) + '\n'
		return m

	def get(self, x, y):
		try:
			return self.maze[y][x]
		except:
			return '#'

UP		= ('^', 0, -1)
DOWN	= ('V', 0, +1)
LEFT	= ('<', -1, 0)
RIGHT	= ('>', +1, 0)


def move(c):
	for p, dx, dy in [UP, DOWN, LEFT, RIGHT]:
		if c == p: return dx, dy

def coords(x, y, seq):
	l = []
	for c in seq:
		dx, dy = move(c)
		x += dx
		y += dy
		l.append( (x, y) )
	return l

def search(maze, x, y):
	paths = [('', x, y)]
	found = []

	while paths:
		pathseq, x, y = paths.pop()
		pathcount = 0
		#print 'doing %r %d %d' % (pathseq, x, y)
		for p, dx, dy in [UP, DOWN, LEFT, RIGHT]:
			nx = x + dx
			ny = y + dy
			c = maze.get(nx, ny)
			#print '%c %d,%d %c' % (p, nx, ny, c)

			newpath = pathseq + p
			if c in ' ':
				# make sure we don't go into a loop
				clist = coords(x, y, newpath)
				if len(set(clist)) == len(clist):
					# can proceed
					paths.insert(0, (newpath, nx, ny))
					pathcount += 1
			elif c == 'X':
				# found it!
				found.append(newpath)
				pathcount += 1

		#if pathcount == 0: print 'dead:  ' + pathseq
		#print '\n'.join(repr(pp) for pp in paths)
		#print '-' * 10

	return sorted(found, lambda x, y: cmp(len(x), len(y)))

def play(maze, solution):
	x, y = maze.get_startpos()
	for i, c in enumerate(solution):
		dx, dy = move(c)
		x += dx
		y += dy

		print '\n' * 20
		print '\n%s\n' % maze.render(x, y)
		print '\n%s\n' % solution[:i+1]
		raw_input('ENTER to advance')

def main():
	f = open(sys.argv[1], 'r')
	maze = Maze(f.readlines())
	f.close()

	#print maze.get_startpos()
	solutions = search(maze, *maze.get_startpos())
	print '\n'.join(solutions)

	solution = solutions[0]
	play(maze, solution)


if __name__ == '__main__':
	main()