#!/usr/bin/python3 import sys # Tri-states UNKNOWN = 'unknown' PRESENT = 'present' # wall ABSENT = 'absent' # wall EXPLORED = 'explored' # cell AVOID = 'avoid' # cell # Colored terminal display CLEAR = '\033[0m' RED = lambda s: f'\033[1;41m{s}{CLEAR}' RED_U = lambda s: f'\033[1;4;41m{s}{CLEAR}' GREEN = lambda s: f'\033[42m{s}{CLEAR}' GREEN_U = lambda s: f'\033[4;42m{s}{CLEAR}' # Standard header line HEADER = '._'*16 + '.' # A value for "unknown number of steps to the target area" FAR_AWAY = 999 class Maze(object): def __init__(self): self.cells = tuple( tuple(Cell() for c in range(16)) for r in range(16) ) for i in range(16): self.cells[15][i].S = PRESENT self.cells[i][0].W = PRESENT # Mark the destination area. for r in (7, 8): self.cells[r][8].W = ABSENT for c in (7, 8): cell = self.cells[r][c] cell.steps = 0 cell.allow = EXPLORED def north_wall(self, r, c): if r == 0: return PRESENT return self.cells[r-1][c].S def east_wall(self, r, c): if c == 15: return PRESENT return self.cells[r][c+1].W def south_wall(self, r, c): return self.cells[r][c].S def west_wall(self, r, c): return self.cells[r][c].W def set_north(self, r, c, status): if r == 0: assert status == PRESENT else: cell = self.cells[r-1][c] assert cell.S == UNKNOWN or cell.S == status cell.S = status def set_east(self, r, c, status): if c == 15: assert status == PRESENT else: cell = self.cells[r][c+1] assert cell.W == UNKNOWN or cell.W == status cell.W = status def set_south(self, r, c, status): if r == 15: assert status == PRESENT else: cell = self.cells[r][c] assert cell.S == UNKNOWN or cell.S == status cell.S = status def set_west(self, r, c, status): if c == 0: assert status == PRESENT else: cell = self.cells[r][c] assert cell.W == UNKNOWN or cell.W == status cell.W = status def choices(self, r, c): "Where can we move from this location?" cells = [ ] # We must have explored this cell, to determine choices. assert self.cells[r][c].allow == EXPLORED if self.north_wall(r, c) == ABSENT: cells.append((r-1, c)) if self.east_wall(r, c) == ABSENT: cells.append((r, c+1)) if self.south_wall(r, c) == ABSENT: cells.append((r+1, c)) if self.west_wall(r, c) == ABSENT: cells.append((r, c-1)) # Remove any cells that are to be avoided. return [ loc for loc in cells if self.cells[loc[0]][loc[1]].allow != AVOID ] def propagate(self): "Propagate STEPS and PATHLEN around the maze." # Set STEPS on every cell that we *know* can reach the destination. # Start from the destination, and work outwards. cells = set((r, c) for r in (7, 8) for c in (7, 8)) seen = cells.copy() steps = 0 while cells: #print('STEPS:', steps, cells) outward = set() for r, c in cells: outward |= set(self.choices(r, c)) self.cells[r][c].steps = steps # likely unchanged # Mark cells we've seen, so we don't revisit them. #print('NEARBY:', outward) #print('ALLOW:', [f'[{r1},{c1}] "{self.cells[r1][c1].allow}" "{EXPLORED}" {self.cells[r1][c1].allow!=EXPLORED}' for (r1,c1) in outward]) # Keep the explored cells; these we need to update. This # is particularly important since we start from the # destination. We only want to set STEPS on EXPLORED cells. cells = set((r2, c2) for (r2, c2) in outward if self.cells[r2][c2].allow == EXPLORED) #print('EXPLORED:', cells) # Move onwards, to unseen cells. steps += 1 cells -= seen seen |= outward @classmethod def load(cls, fp): m = cls() lines = [ l.strip() for l in fp.readlines() if not l.startswith('#') ] assert len(lines) == 17 # 1 line for visual closure of maze # Standard/requirred header. assert lines[0] == HEADER del lines[0] for r in range(16): row = lines[r] assert len(row) == 33 for c in range(16): cell = m.cells[r][c] # Set the "west" wall w = row[c*2] if w == '|': cell.W = PRESENT else: assert w in (' ', '.') cell.W = ABSENT # Set the "south" wall s = row[c*2+1] if s == '_': cell.S = PRESENT else: assert s == ' ' cell.S = ABSENT assert all(m.cells[r][c].W != UNKNOWN and m.cells[r][c].S != UNKNOWN for c in range(16) for r in range(16)) return m def display(self): print(HEADER) for r in range(16): cols = [ ] for c in range(16): cell = self.cells[r][c] if cell.allow == AVOID: assert cell.W != UNKNOWN if cell.W == PRESENT: w = '|' elif cell.S == PRESENT: w = '.' else: w = ' ' if cell.S == PRESENT: cols.append(f'{w}{RED_U("x")}') else: cols.append(f'{w}{RED("x")}') else: if cell.W == PRESENT: w = '|' elif cell.W == UNKNOWN: w = ':' elif cell.S == PRESENT: # Mark a lattice point, due to southern wall. if cell.allow == EXPLORED: w = GREEN('.') else: w = '.' elif self.cells[r][c-1].S == PRESENT: # Mark a lattice point, due to southern wall in the westerly cell. # Maybe green if this cell has been explored. if cell.allow == EXPLORED: w = GREEN('.') else: w = '.' elif cell.allow == EXPLORED: # Part of open area which is EXPLORED. w = GREEN(' ') else: w = ' ' if cell.allow == EXPLORED: # Color this cell GREEN. if cell.steps < 10: if cell.S == PRESENT: s = GREEN_U(str(cell.steps)) else: s = GREEN(str(cell.steps)) elif cell.S == PRESENT: s = GREEN('_') else: # Cannot be UNKNOWN (thus: ABSENT) since we have # explored this cell and marked it EXPLORED. assert cell.S == ABSENT s = GREEN(' ') elif cell.S == PRESENT: s = '_' elif cell.S == ABSENT: s = ' ' else: # We have not discovered this wall yet. s = '.' cols.append(w+s) print(''.join(cols) + '|') class Cell(object): def __init__(self): self.W = UNKNOWN # west wall self.S = UNKNOWN # south wall self.allow = UNKNOWN # allowed to visit this cell? self.steps = FAR_AWAY # steps to landing zone (0 == here!) self.visited = 0 # how many times have we been here? self.pathlen = FAR_AWAY # steps from start position if __name__ == '__main__': m = Maze.load(sys.stdin) m.cells[4][5].allow = EXPLORED m.cells[5][5].allow = EXPLORED m.cells[10][10].allow = AVOID m.cells[6][7].steps = 7 m.cells[6][7].allow = EXPLORED m.display()