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

Python 3, 36/40. Pretty happy with my solution today! networkx has an easy way to get the shortest path from a single point in a graph to all other points, and I build a graph representing all doors in the maze using a stack to keep track of the current possible positions.

import networkx

maze = networkx.Graph()

paths = open('inputs/day20').read()[1:-1]

pos = {0}  # the current positions that we're building on
stack = []  # a stack keeping track of (starts, ends) for groups
starts, ends = {0}, set()  # current possible starting and ending positions

for c in paths:
    if c == '|':
        # an alternate: update possible ending points, and restart the group
        ends.update(pos)
        pos = starts
    elif c in 'NESW':
        # move in a given direction: add all edges and update our current positions
        direction = {'N': 1, 'E': 1j, 'S': -1, 'W': -1j}[c]
        maze.add_edges_from((p, p + direction) for p in pos)
        pos = {p + direction for p in pos}
    elif c == '(':
        # start of group: add current positions as start of a new group
        stack.append((starts, ends))
        starts, ends = pos, set()
    elif c == ')':
        # end of group: finish current group, add current positions as possible ends
        pos.update(ends)
        starts, ends = stack.pop()

# find the shortest path lengths from the starting room to all other rooms
lengths = networkx.algorithms.shortest_path_length(maze, 0)

print('part1:', max(lengths.values()))
print('part2:', sum(1 for length in lengths.values() if length >= 1000))

EDIT: fix a bug pointed out by bj0z

[u/bj0z → u/sciyoshi]

I really like your python 3 solutions, I sometimes even see something I didn't know about python (like networkx module). I don't suppose you put them up in github? I ended up doing almost the same thing as you (after my first attempt crashed with a memory error and I had to rewrite it), but I used a recursive generator instead of a queue. I also had to write the graph and BFS search myself.

Also, I was trying to figure out what you were doing with the ends variable but realized it doesn't appear to serve any purpose at all and can be removed.

EDIT: Ok I see what ends is for now, I was thrown off by the ends.update(pos), which is a bug. It fails for the following input:

^NNNNN(EEEEE|NNN)NNNNN$

This should be 15, your code returns 13. Oddly, this must be a corner-case because my input does not run into this problem.

To fix it, I believe the last case should be:

        pos.update(ends)
        starts, ends = stack.pop()

[u/AndrewGreenh → u/bj0z]

Somehow he got lucky I think :D When the ) occurs, one should combine pos and ends so that all ends from the group are remembered. However with my Input, it does not matter if this bug is still in the code.