85 lines
2.3 KiB
Python
85 lines
2.3 KiB
Python
import copy
|
|
from random import randint
|
|
|
|
WALL = 0
|
|
EMPTY = 1
|
|
PATH = 2
|
|
DEAD = 3
|
|
|
|
|
|
class CS235Maze(object):
|
|
def __init__(self, data):
|
|
self._data = data
|
|
self._size = len(data)
|
|
|
|
def _solve(self, x, y, z, path):
|
|
if x < 0 or y < 0 or z < 0 or \
|
|
x >= self._size or y >= self._size or z >= self._size:
|
|
return False
|
|
elif self._data[x][y][z] != EMPTY:
|
|
return False
|
|
elif x == self._size - 1 and y == self._size - 1 \
|
|
and z == self._size - 1:
|
|
self._data[x][y][z] = PATH
|
|
path.append((x, y, z))
|
|
return True
|
|
else:
|
|
self._data[x][y][z] = PATH
|
|
if self._solve(x - 1, y, z, path) or \
|
|
self._solve(x + 1, y, z, path) or \
|
|
self._solve(x, y - 1, z, path) or \
|
|
self._solve(x, y + 1, z, path) or \
|
|
self._solve(x, y, z - 1, path) or \
|
|
self._solve(x, y, z + 1, path):
|
|
path.append((x, y, z))
|
|
return True
|
|
else:
|
|
self._data[x][y][z] = DEAD
|
|
return False
|
|
|
|
def solve(self):
|
|
path = []
|
|
success = self._solve(0, 0, 0, path)
|
|
path.reverse()
|
|
return success, path
|
|
|
|
def __str__(self):
|
|
r = derp_transpose(self._data, self._size)
|
|
rs = ''
|
|
for i in xrange(self._size):
|
|
for j in xrange(self._size):
|
|
for k in xrange(self._size):
|
|
rs += '{} '.format(r[i][j][k])
|
|
rs += '\n'
|
|
rs += '\n'
|
|
return rs
|
|
|
|
|
|
def make_maze(size=8):
|
|
r = []
|
|
for i in xrange(size):
|
|
r.append([])
|
|
for j in xrange(size):
|
|
r[i].append([randint(0, 1) for k in xrange(size)])
|
|
r[0][0][0] = 1
|
|
r[size - 1][size - 1][size - 1] = 1
|
|
return CS235Maze(r)
|
|
|
|
|
|
def parse_maze(maze):
|
|
maze = maze.replace('\r', '')
|
|
soilded = [[[int(i) for i in j.split()]
|
|
for j in k.split('\n')]
|
|
for k in maze.split('\n\n') if k]
|
|
cleaned = derp_transpose(soilded, size=len(soilded))
|
|
return CS235Maze(cleaned)
|
|
|
|
|
|
def derp_transpose(s, size=8):
|
|
r = copy.deepcopy(s)
|
|
for i in xrange(size):
|
|
for j in xrange(size):
|
|
for k in xrange(size):
|
|
r[i][j][k] = s[k][j][i]
|
|
return r
|