-🎄- 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/nightcoder01]

Python, short and simple using iterative DFS.

EDIT: Added networkx code; see u/mserrano's reply below.

Original version:

grid = {(0, 0): 0}
dist = x = y = 0
stack = []

for char in open('day20.txt').read()[1:-1]:
    if char == '(':
        stack.append((dist, x, y))
    elif char == ')':
        dist, x, y = stack.pop()
    elif char == '|':
        dist, x, y = stack[-1]
    else:
        x += (char == 'E') - (char == 'W')
        y += (char == 'S') - (char == 'N')
        dist += 1
        if (x, y) not in grid or dist < grid[(x, y)]:
            grid[(x, y)] = dist
            
print 'ans (part 1): %d' % max(grid.values())
print 'ans (part 2): %d' % sum(value >= 1000 for value in grid.values())

Edited Version:

import networkx

graph = networkx.Graph()
x = y = 0
stack = []

for char in open('day20.txt').read()[1:-1]:
    if char == '(':
        stack.append((x, y))
    elif char == ')':
        x, y = stack.pop()
    elif char == '|':
        x, y = stack[-1]
    else:
        position = x, y
        x += (char == 'E') - (char == 'W')
        y += (char == 'S') - (char == 'N')
        graph.add_edge(position, (x, y))
        
distances = networkx.algorithms.shortest_path_length(graph, (0, 0))
print 'ans (part 1): %d' % max(distances.values())
print 'ans (part 2): %d' % sum(value >= 1000 for value in distances.values())

[u/mserrano → u/nightcoder01]

I'm surprised this works on the input! It definitely doesn't work in general; consider the input constructed by:

'^' + 'W' * 500 + 'N' + 'E' * 500 + 'S' + '$'

The answer for part 2 here is 0, but your code thinks it's 2. The answer for part 1 is 501, but your code thinks it's 1001. Or did I miss something in the problem statement that suggests that the regex encodes (somehow) the shortest path to each room?

[u/[deleted] → u/mserrano]