AOC 2018 Day 20: A Regular Map

This article is about my interpretations and solution for the advent of code 2018 day 20 programming puzzle, the solution is by no means optimized from both time/space complexity, so please let me know if you have different solutions :)

The Puzzle

Based on the problem statement(assuming you have already read it), a regexp is giving as input, like ^WNE$, ^WNEE(N|S)$, and so on, which corresponds to maps.

The map can be generated via “walking” the regexp, for example ^WNE$ generates:

#####
#.|.#
#-###
#.|X#
#####

^WNEE(N|S)$ generates

#######
#####.# // <- The N in (N|S)
#####-#
#.|.|.# // <- Can walk (N|S)
#-###-#
#.|X#.# // <- The S in (N|S)
#######

The first question asks what’s most | — you can cross if you follow the shortest path to all the ..
The second question asks what’s the number of . that need to cross at least 1000 | —to access.

My Interpretations

If we can parse the regexp input to a graph with vertices and edges, we can solve both problems by running BFS(breadth-first search, which is one of the best choices for finding the shortest path in unweighted graphs) from the original point.

N,S,W,E represents edges in the graph, and when it comes to (,|,) we need to worry about the “branch”.
Let me start from a DEMO of “walking” the ^WNE$, you start from “(0, 0)”, then walking “WNE”, as the photo below:

We can then represent the graph with a list of vertices and the direction is can walk:

{
  [0, 0]: [[-1, 0]],
  [-1, 0]: [[0, 1], [1, 0]],
  [-1, 1]: [[1, 0], [0, -1]],
  [0, 1]: [[-1, 0]],
}

After we had ^, we can BFS to find the longest distance to any “room” is 3 in this case.

When there are branches, things become a little bit trickier, the photo below is DEMO for walking ^ENWWW(NEEE|SSE(EE|N))$:

Same as before, we can collect the graph metadata along with the walk, and BFS to get the answer.
When there are branches, we need somehow recursively walk the route(my solution for this part is included in the coming section, it takes a lot of lines of code, there are solutions don’t take that many lines, but I didn't get it when writing this 😐).

My Solution

Simply, here is my solution’s code in go :)

This Github repo includes my solutions for other AOC 2018 challenges, take a look if you interested :)