Day 20 - regex parsing and more path finding

This is essentially a path-finding problem; the regex is a tree of legal steps to reach a location, and from that tree you can construct all possible legal moves across the map. We can then find the longest possible path from this.

Note that the shortest route is required; no meandering around to get to the furstest room. The input probably includes ways to open doors between rooms that open up shortcuts to the furthest rooms. So we can build a graph of the rooms and connections first (taking care to reuse a room when it already exists at that location), then use a path finding algorithm to determine which path is longest.

The regex encodes many bracnhing paths, but the string can be treated as a stack and we only have to track the branch tips. We start with the tip of a single root branch (our starting point), and each time we reach a (, we push our current set of brannches on the stack, create a new set to track the new branches and continue on with parsing; each | creates a new set of branch tips based on the top of the stack, and with ) we can pop from the stack and continue on as before with the accumulated branches.

Finding the longest path is a simple exhaustive traversal of the graph, where we avaid visiting rooms we have seen before unless our new path is shorter. Because we already track per-room distances, part 2 was trivial.

In [1]:
import re
from collections import deque
from dataclasses import dataclass, field
from functools import reduce
from typing import Iterable, Iterator, Mapping, Optional, Tuple

Pos = Tuple[int, int]
_delta = {'N': (0, -1), 'W': (-1, 0), 'E': (1, 0), 'S': (0, 1)}
_doors = dict(zip('NWES', '-||-'))
_inverse = dict(zip('NWES', 'SEWN'))
_tokenize = re.compile(r'(\(|\||\)|[NWSE]+)').finditer

# not really frozen, we allow manipulation through __getitem__ and __setitem__
# but the N, S, W, E directions are not part of the hash.
@dataclass(frozen=True)
class Room:
    x: int = 0
    y: int = 0
    N: 'Node' = field(default=None, compare=False, repr=False)
    W: 'Node' = field(default=None, compare=False, repr=False)
    S: 'Node' = field(default=None, compare=False, repr=False)
    E: 'Node' = field(default=None, compare=False, repr=False)

    @property
    def pos(self) -> Pos:
        return (self.x, self.y)

    def open_door(self, dir: str) -> 'Room':
        room = self[dir]
        if room is None:
            dx, dy = _delta[dir]
            room = self[dir] = Room(self.x + dx, self.y + dy)
            room[_inverse[dir]] = self
        return room

    @property
    def available(self) -> Iterator[str]:
        return (d for d in 'NSWE' if self[d] is not None)
            
    def __getitem__(self, dir: str) -> 'Room':
        if dir not in 'NSWE':
            raise AttributeError(dir)
        return self.__dict__[dir]
    
    def __setitem__(self, dir: str, room: 'Room') -> None:
        if dir not in 'NSWE':
            raise AttributeError(dir)
        self.__dict__[dir] = room
    
    def __repr__(self) -> str:
        doors = ''.join(d if self[d] is not None else d.lower() for d in 'NSWE')
        return f"{type(self).__name__}(x={self.x}, y={self.y} {doors})"

    
class RegularMap:
    start: Optional[Room]

    def __init__(self, start: Room):
        self.start = start
        
    @classmethod
    def from_regex(cls, regex: Iterable[str]) -> 'RegularMap':
        stack = deque()
        start = Room()
        here = {start}
        new_branch_tips = None
        for token in (m.group() for m in _tokenize(regex)):
            if token == '(':
                stack.append(set(here))
                new_branch_tips = set()
            elif token == '|':
                new_branch_tips.update(here)
                here = set(stack[-1])
            elif token == ')':
                new_branch_tips.update(here)
                stack.pop()
                here = new_branch_tips
            else:
                here = {reduce(Room.open_door, token, r) for r in here}
        return RegularMap(start)
    
    def furthest_room(self) -> int:
        queue = deque([(self.start, 0)])
        distances = {self.start.pos: 0}
        while queue:
            room, distance = queue.popleft()
            distance += 1
            for dir in room.available:
                next_ = room[dir]
                if next_.pos in distances and distances[next_.pos] <= distance:
                    continue
                distances[next_.pos] = distance
                queue.append((next_, distance))
        return max(distances.values()), sum(1 for d in distances.values() if d >= 1000)
    
    def _by_coords(self) -> Mapping[Pos, Room]:
        # collect coords
        queue = deque([self.start])
        rooms = {self.start.pos: self.start}
        while queue:
            room = queue.popleft()
            for dir in room.available:
                next_ = room[dir]
                if next_.pos in rooms:
                    continue
                rooms[next_.pos] = next_
                queue.append(next_)
        return rooms

    def __str__(self):
        rooms = self._by_coords()
        minx, miny = (min(vs) for vs in zip(*rooms))
        maxx, maxy = (max(vs) for vs in zip(*rooms))
        width, height = abs(maxx + 1 - minx), abs(maxy + 1 - miny)
        lines = [['#'] * (width * 2 + 1) for _ in range(height * 2 + 1)]
        for (x, y), room in rooms.items():
            lines[(y - miny) * 2 + 1][(x - minx) * 2 + 1] = 'X' if room.pos == (0, 0) else '.' 
            for dir in room.available:
                dx, dy = _delta[dir]
                lines[(y - miny) * 2 + 1 + dy][(x - minx) * 2 + 1 + dx] = _doors[dir]
        
        return '\n'.join([''.join(l) for l in lines])
In [2]:
tests = {
    "^E(N|S)E$": ('#######\n###.|.#\n###-###\n#X|.###\n###-###\n###.|.#\n#######', 3),
    "^ENWWW(NEEE|SSE(EE|N))$": ('#########\n#.|.|.|.#\n#-#######\n#.|.|.|.#\n#-#####-#\n#.#.#X|.#\n#-#-#####\n#.|.|.|.#\n#########', None),
    "^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$": ('###########\n#.|.#.|.#.#\n#-###-#-#-#\n#.|.|.#.#.#\n#-#####-#-#\n#.#.#X|.#.#\n#-#-#####-#\n#.#.|.|.|.#\n#-###-###-#\n#.|.|.#.|.#\n###########', None),
    "^ESSWWN(E|NNENN(EESS(WNSE|)SSS|WWWSSSSE(SW|NNNE)))$": ('#############\n#.|.|.|.|.|.#\n#-#####-###-#\n#.#.|.#.#.#.#\n#-#-###-#-#-#\n#.#.#.|.#.|.#\n#-#-#-#####-#\n#.#.#.#X|.#.#\n#-#-#-###-#-#\n#.|.#.|.#.#.#\n###-#-###-#-#\n#.|.#.|.|.#.#\n#############', 23),
    "^WSSEESWWWNW(S|NENNEEEENN(ESSSSW(NWSW|SSEN)|WSWWN(E|WWS(E|SS))))$": ('###############\n#.|.|.|.#.|.|.#\n#-###-###-#-#-#\n#.|.#.|.|.#.#.#\n#-#########-#-#\n#.#.|.|.|.|.#.#\n#-#-#########-#\n#.#.#.|X#.|.#.#\n###-#-###-#-#-#\n#.|.#.#.|.#.|.#\n#-###-#####-###\n#.|.#.|.|.#.#.#\n#-#-#####-#-#-#\n#.#.|.|.|.#.|.#\n###############', 31),
}

for regex, (expected_str, expected_distance) in tests.items():
    test_rmap = RegularMap.from_regex(regex) 
    assert str(test_rmap) == expected_str
    if expected_distance:
        assert test_rmap.furthest_room()[0] == expected_distance
In [3]:
import aocd

data = aocd.get_data(day=20, year=2018)
regular_map = RegularMap.from_regex(data)
In [4]:
furthest_room, far_rooms = regular_map.furthest_room()
print('Part 1:', furthest_room)
print('Part 2:', far_rooms)
Part 1: 3991
Part 2: 8394

The animation produced below can be viewed online via the Jupyter notebook viewer; the GitHub renderer filters them out.

In [5]:
%matplotlib inline
import re
from matplotlib import animation, rc
import matplotlib.pyplot as plt
import numpy as np

rc('animation', html='html5')

def animate_parse(regex):
    rooms = RegularMap.from_regex(regex)._by_coords()
    minx, miny = (min(vs) for vs in zip(*rooms))
    maxx, maxy = (max(vs) for vs in zip(*rooms))
    width, height = abs(maxx + 1 - minx), abs(maxy + 1 - miny)
    del rooms
    
    stack = deque()
    start = Room()
    here = {start}
    branches = None
    frames = [[start.pos]]

    for token in (m.group() for m in _tokenize(regex)):
        if token == '(':
            stack.append(here)
            branches = here = set(here)
        elif token == '|':
            branches.update(here)
            here = set(stack[-1])
        elif token == ')':
            branches.update(here)
            stack.pop()
            here = branches
        else:
            for dir in token:
                coords = []
                frames.append(coords)
                new_here = set()
                for room in here:
                    room = room.open_door(dir)
                    coords.append(room.pos)
                    new_here.add(room)
                here = new_here

    frames += (None for _ in range(512))  # full fade for remainder
                
    fig, ax = plt.subplots(figsize=(8, 8))
    fig.subplots_adjust(left=0, bottom=0, right=1, top=1, wspace=0, hspace=0)
    ax.set_axis_off()
    
    grid = np.zeros((width, height), dtype=np.uint8)
    image = ax.imshow(grid, vmin=0, vmax=255, cmap='magma')
    
    def render(coords):
        a = image.get_array()
        a[(a > 0) & (a < 255)] += 1
        if coords:
            coords = tuple(zip(*((y - miny, x - minx) for x, y in coords)))
            a[coords] = 1
        return image,

    anim = animation.FuncAnimation(
        fig, render, frames, interval=10, blit=True,
        repeat_delay=1000
    )
    plt.close(fig)
    return anim

animate_parse(data)
Out[5]: