Solution for Advent of Code 2018 - Day 20: A Regular Map

Link to the puzzle text

Part 1

In this puzzle, we have a string showing possible ways through a grid. The ways are encoded similar to a regular expression, where each character either shows a transition between cells in the grid ("NEWS" for the 4 directions) or a branch between possibilities starting with "(" and seperated by "|". We should find the longest shortest path to a reachable cell.

We start by saving the shortest possible path to each cell in a dictionary and have a current position starting in the top left. We parse the input string character by character. Directions are handled by updating the current position and shortest path dictionary. For the branches we keep a stack of previous positions. Whenever we start a branch, we push the current position onto the stack. For branch ends or seperators, we just restore the position before taking the branch.

The answer is then the largest distance we found over all cells. 

Part 2

In part 2, we should find the number of cells reachable in over than 1000 steps.

We can reuse the previous dictionary and count the number of elements with value more than 1000.

Link to my solutions