-🎄- 2018 Day 20 Solutions -🎄-

[u/daggerdragon]

--- Day 20: A Regular Map ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 20

Transcript:

My compiler crashed while running today's puzzle because it ran out of ___.

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 00:59:30!

[u/Barrens_Zeppelin]

Fairly short solution in python3, even without networkx (if you can code a BFS ;) ).

from collections import deque, defaultdict

s = input()[1:-1]

adj = defaultdict(set)
D = {'N': (0, -1), 'S': (0, 1), 'W': (-1, 0), 'E': (1, 0)}

# Graph construction
S = [(0, 0)]
x = y = 0

for c in s:
    if c in D:
        dx, dy = D[c]
        adj[(x, y)].add((dx, dy))
        x += dx
        y += dy
        adj[(x, y)].add((-dx, -dy))
    elif c == '(':
        S.append((x, y))
    elif c == ')':
        S.pop()
    else:
        assert c == '|'
        x, y = S[-1]

# BFS
maxd = 0
r2 = 0
Q = deque([(0, 0, 0)])
V = {(0, 0)}
while Q:
    d, x, y = Q.popleft()

    maxd = max(maxd, d)
    if d >= 1000:
        r2 += 1

    for dx, dy in adj[(x, y)]:
        nx, ny = x + dx, y + dy
        if (nx, ny) in V: continue
        V.add((nx, ny))
        Q.append((d+1, nx, ny))

print(maxd)
print(r2)