Skip to content

Instantly share code, notes, and snippets.

@Julien00859

Julien00859/deemaze_large.txt

Created January 15, 2023 02:33
Show Gist options
  • Save Julien00859/23042eb5af33e0756cae577f91dfe520 to your computer and use it in GitHub Desktop.
Save Julien00859/23042eb5af33e0756cae577f91dfe520 to your computer and use it in GitHub Desktop.
Download ZIP
Deepmaze visualizer
Raw
deemaze_large.txt
#a# #b# #c#
################################# ### ###
################################### ### ##################
### ### ### ####################
### \\\\################# ### ### ### ###
### ////################# ### ### ### ###
### +----------###-+ ### ### +-###----------+ ###
l############## c | ### ### ##### a ####### #####d
###############l | ### ### ######l d###### #######
| | ### ### ### | | ###
| 1111 e######## ### ######k 2222 e###########
| 1111 ####### ### ##### 2222 ###########
| | ### | | ###
#########j | ### | f###########
######### i | ### | h g ##########
### +-###----------+ ### +-----%%%--###-+
### ### ### %%% ###
### ### ### /^^^\ ###
##### ### ### ##########//^^^\\###
k###### ############################ ###########/ %%% \### ##########e
##### ############################## ### %%% ############
#### ### ### %%% ###
#### ########### ### ### %%%%%%%% ###
### ############## ### ### %%%%%%%%%% ###
### ### +-----###------+ ### ### +-%%%------%%%-+ ###
### ###### b ######### ### ##### a c ######
### #####l d######### ### ######l d######
### | | ### ### ### | | ###
### #####k 3333 | ### ### ######k 4444 e######
### ###### 3333 | ### ### ##### 4444 #####
j###### ### | | ### ### | | ####f
###### ### | | ### ###########j | ######
### | g | ### ########### h | ###
### +----------###-+ ### ### +------###-----+ ###
### ### ### #### ###################
################### ### ### #################
################# ### ###
### ### ####################
### ### ####################
#i# #h# #g#
Raw
deepmaze.py
import ast
import collections
import contextlib
import curses
import curses.ascii
import heapq
import sys
import time
from functools import partial, lru_cache
from types import SimpleNamespace
class Maze:
PATHWAYS = set('#/\\^>')
ALT_PATHWAYS = set('%^')
DOORS = set('abcdefghijkl')
WALLS = set(' |-+')
def __init__(self, ascii_maze, start, edges, paths):
self._ascii_maze = ascii_maze
self.height = len(ascii_maze)
self.width = len(ascii_maze[0])
self.start = (start[0] - 1, start[1] - 1)
self.edges_qc2p = {
(quadrant, case): (y - 1, x - 1)
for quadrant, case, (y, x) in edges
}
self.edges_p2qc = {
(y - 1, x - 1): (quadrant, case)
for quadrant, case, (y, x) in edges
}
self.paths = paths
def __getitem__(self, pos):
if type(pos) is int:
return self._ascii_maze[pos]
y, x = pos
return self._ascii_maze[y][x]
def __iter__(self):
return iter(self._ascii_maze)
@classmethod
def fromfile(cls, mazepath, configpath):
with open(mazepath) as mazefile:
grid = mazefile.read().splitlines()
with open(configpath) as configfile:
config = ast.literal_eval(configfile.read())
# fix trim
maxlen = max(len(line) for line in grid)
for lineno, line in enumerate(grid):
if len(line) < maxlen:
grid[lineno] = format(line, f'<{maxlen}')
return cls(grid, **config)
def quadrant(self, y, x):
return y // (self.height // 2), x // (self.width // 2)
def pathway_at(self, y, x):
alt_path_edges = {
self.edges_qc2p[(0, 1), "h"],
self.edges_qc2p[(1, 1), "a"],
self.edges_qc2p[(1, 1), "c"],
}
return self.ALT_PATHWAYS if (y, x) in alt_path_edges else self.PATHWAYS
def neighbores(self, y, x, pathway=None):
if pathway is None:
pathway = self.pathway_at(y, x)
return [
(ny, nx)
for ny, nx
in [(y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)]
if 0 <= ny < self.height and 0 <= nx < self.width
if self[ny, nx] in pathway or (
self[ny, nx] in self.DOORS and self[y, x] not in self.DOORS
)
]
@lru_cache()
def explore(self, start, onvisit=None):
exploration = collections.deque([start])
pathway = self.pathway_at(*start)
visited = set()
paths = []
while exploration:
pos = exploration.popleft()
if onvisit:
onvisit(*pos)
visited.add(pos)
if self[pos].isalpha() and pos != start:
paths.append(pos)
exploration.extend(
npos for npos
in self.neighbores(*pos, pathway)
if npos not in visited
if npos not in exploration
)
return paths
class Screen:
PERIOD = 0
def __init__(self, stdscr=None):
curses.curs_set(0)
self.stdscr = stdscr
self.clock = time.time()
if not curses.can_change_color():
raise RuntimeError("The terminal doesn't support colors")
colors = [
curses.COLOR_BLACK, curses.COLOR_WHITE, curses.COLOR_BLUE,
curses.COLOR_CYAN, curses.COLOR_GREEN, curses.COLOR_MAGENTA,
curses.COLOR_RED, curses.COLOR_YELLOW,
]
for i, (bg, fg) in enumerate(
((c1, c2) for c1 in colors for c2 in colors if c1 != c2), start=1):
curses.init_pair(i, fg, bg)
@contextlib.contextmanager
def animate(self, period=None):
self.stdscr.timeout(period or self.PERIOD)
try:
yield
finally:
self.stdscr.timeout(-1)
def refresh(self, maze):
self.stdscr.clear()
for lineno, line in enumerate(maze):
self.stdscr.addstr(lineno, 0, line)
self.stdscr.addstr(lineno + 2, 0, ' ' * maze.width)
def status(self, maze, exploration):
stdscr = self.stdscr
maxy, maxx = stdscr.getmaxyx()
# Stats
stdscr.addstr(maze.height + 1, 0,
f"Time spent: {time.time()-self.clock:> 8.2f}")
stdscr.addstr(maze.height + 2, 0,
f"Queue size: {len(exploration):>8d}")
# Queue viewer
def _explo_key(step):
current_pos, history, levels = step
return len(levels), len(history), history, current_pos
i = -1
history_width = 6
colomn_width = 10
frmt = "{:2d}-{:<%s}" % history_width
area = (maxx - maze.width - 1) // colomn_width * maxy - 1
for i, step in enumerate(heapq.nsmallest(area, exploration, _explo_key)):
_, history, levels = step
x = maze.width + i // maxy * colomn_width + 1
y = i % maxy
text = frmt.format(len(levels), history[-history_width:])
stdscr.addstr(y, x + 1, text, curses.color_pair(len(levels) + 2))
stdscr.addstr(y, x, '>' if step == exploration[0] else ' ')
for i in range(i + 1, area):
x = maze.width + i // maxy * colomn_width + 1
y = i % maxy
stdscr.addstr(y, x, " " * colomn_width)
def colorize(self, y, x, maze, color):
self.stdscr.addstr(y, x, maze[y, x], curses.color_pair(color))
self.stdscr.getch()
def main(stdscr, maxdepth=10):
maxdepth = int(sys.argv[1])
maze = Maze.fromfile('deepmaze_large.txt', 'deepmaze_large.py')
if stdscr:
screen = Screen(stdscr)
max_height, max_width = stdscr.getmaxyx()
if max_height < maze.height or max_width < maze.width:
raise RuntimeError("The terminal is too small to render the maze")
screen.refresh(maze)
exploration = collections.deque([(maze.start, '', [])])
while exploration:
if stdscr:
with screen.animate(1):
stdscr.getch()
screen.status(maze, exploration)
current_pos, history, levels = exploration.popleft()
if len(history) >= maxdepth:
continue # too deep
with screen.animate() if stdscr else contextlib.nullcontext():
doors = maze.explore(
current_pos,
onvisit=(
partial(screen.colorize, maze=maze, color=len(levels)+2)
if stdscr else None
)
)
for door in doors:
next_level, case = maze.edges_p2qc[door]
if next_level == 'exit':
if not levels:
return history
# go up a level
next_pos = maze.edges_qc2p.get((levels[-1], case), None)
if next_pos:
exploration.append((
next_pos, history + case.upper(), levels[:-1],
))
elif levels and levels[-1] == next_level:
# cycle detected, skip
continue
else:
# go down a level
next_pos = maze.edges_qc2p['exit', case]
exploration.append((
next_pos, history + case, levels + [next_level],
))
if stdscr:
screen.status(maze, exploration)
stdscr.getch()
if __name__ == '__main__':
if len(sys.argv) == 1:
sys.exit('usage: {} maxdepth [--nogui]'.format(sys.argv[0]))
if '--nogui' in sys.argv:
history = main(None)
else:
history = curses.wrapper(main)
if history:
print("Solution:", history)
else:
print("No solution found.")
Raw
deepmaze_large.py
{
"start": (5, 8),
"edges": [
# quad case y x
("exit", "a", (1, 18)),
("exit", "b", (1, 40)),
("exit", "c", (1, 63)),
("exit", "d", (8, 80)),
("exit", "e", (20, 80)),
("exit", "f", (31, 80)),
("exit", "g", (40, 63)),
("exit", "h", (40, 40)),
("exit", "i", (40, 18)),
("exit", "j", (31, 1)),
("exit", "k", (20, 1)),
("exit", "l", (8, 1)),
((0, 0), "c", (8, 27)),
((0, 0), "e", (11, 29)),
((0, 0), "i", (15, 18)),
((0, 0), "j", (14, 16)),
((0, 0), "l", (9, 16)),
((0, 1), "a", (8, 54)),
((0, 1), "d", (9, 65)),
((0, 1), "e", (11, 65)),
((0, 1), "f", (14, 65)),
((0, 1), "g", (15, 63)),
((0, 1), "h", (15, 58)),
((0, 1), "k", (11, 52)),
((0, 1), "l", (9, 52)),
((1, 0), "b", (26, 22)),
((1, 0), "d", (27, 29)),
((1, 0), "g", (33, 27)),
((1, 0), "k", (29, 16)),
((1, 0), "l", (27, 16)),
((1, 1), "a", (26, 54)),
((1, 1), "c", (26, 63)),
((1, 1), "d", (27, 65)),
((1, 1), "e", (29, 65)),
((1, 1), "h", (33, 59)),
((1, 1), "j", (32, 52)),
((1, 1), "k", (29, 52)),
((1, 1), "l", (27, 52)),
],
"paths": {
(4, 7): [(7, 26)],
(0, 62): [(7, 53), (8, 64)],
(0, 17): [(7, 0), (8, 15), (10, 28)],
(7, 79): [(10, 64), (13, 64)],
(8, 51): [(10, 51)],
(7, 0): [(8, 15), (0, 17), (10, 28)],
(19, 79): [(26, 64), (28, 64)],
(19, 0): [(13, 15)],
(30, 0): [(14, 17), (26, 28), (39, 39), (0, 39)],
(30, 79): [(32, 58)],
(39, 39): [(26, 28), (0, 39), (14, 17), (30, 0)],
(39, 17): [(32, 26), (28, 15)],
(31, 51): [(39, 62), (14, 62)],
(39, 62): [(31, 51), (14, 62)],
(14, 62): [(31, 51), (39, 62)],
(32, 58): [(30, 79)],
(32, 26): [(39, 17), (28, 15)],
(14, 17): [(30, 0), (26, 28), (0, 39), (39, 39)],
(13, 64): [(7, 79), (10, 64)],
(14, 57): [(25, 53), (25, 62)],
(26, 28): [(39, 39), (0, 39), (14, 17), (30, 0)],
(13, 15): [(19, 0)],
(26, 51): [(28, 51)],
(28, 51): [(26, 51)],
(25, 53): [(25, 62), (14, 57)],
(25, 21): [(26, 15)],
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment