Day 20: Donut Maze
by Simon Berger
Links:
We’re blessed with another graph problem today. I can only imagine the pain this type of problem causes to someone who isn’t familiar with graph theory. To be fair, all puzzles so far involved very basic concepts, but I think it’s still a lot to take in if you’ve never dealt with it before. I, for one, enjoy modelling the problems so they can be seen as a graph problem so I’m totally here for it.
We yet again have to find the shortest path between two spatial states, only this time we get to deal with portals. Funnily enough, portals – in terms of graph theory – don’t add a lot, if any, complexity. They just create an edge between two vertices which normally wouldn’t have one. What we have is a graph where each vertex describes a position and there is an edge between two vertices if we can move between them. We’ve seen this before so we know we can perform BFS to find the shortest path between two positions.
The second part quite literally introduces a new dimension to this by making the portals work differently. When going through a portal this new dimension changes. Some portals increase it by one and some decrease it. This dimension is called “level”. We still have to find the shortest path between two states, but in addition to the spatial dimensions we now also have to consider the level. This changes our graph so that for each position there are now multiple vertices, one for each level. Much like before we can use BFS to find the shortest path. The first part is just a specialisation of this problem in that we’re looking for the shortest path to a position regardless of the level it is at.
The hardest part today is most certainly parsing the input. I would even go as far as to claim that manually handling the input is significantly easier than parsing it programmatically. The problematic part is the portals. They are labelled with more than one character and they’re either left-to-right or top-to-bottom. Because of this label, portals can only be found at the edges of the map. The map itself is a square annulus (I just learned this word and I love it!). This is important because portals on the outer border of the map decrease the level by one and those lying on the inner border increase it by one. For the second part it’s fundamental that we can distinguish between the two portal types so we need to somehow detect the shape of the annulus.
I want to quickly go over how my code parses the input. There are three distinct steps (they could be performed in one step, but it’s easier to do them separately).
First, go over each position in the map and look at the tile:
If it’s a “walkable” tile (identified by the character .) remember that this position is traversable.
If it’s a character part of a portal label, keep track of it together with its position.
Otherwise it’s either a wall or empty space. Either way, move on to the next position.
We have identified all traversable positions and all characters that are part of portal labels. I’m also using this step to determine the outer border of the annulus. The second step is to parse the portal label characters to find the label and position of each portal.
To do this look at each character and its corresponding position:
Look at the surrounding four positions. If there is another character on the left or on top, ignore this character and move on to the next iteration (This is to avoid reading the label backwards).
If there is a character on the right, remember that the label is left-to-right. Otherwise, remember that the label is top-to-bottom.
Continue moving in the direction of the label (right or down) until no further characters are found. Combine all encountered characters to get the label.
The position of the portal is either right before the label starts or right after it. Check both positions and chose whichever is traversable.
After all this we know the position and label of each portal, but we also want to know which portals are connected to each other. This is trivial to do; just find the two positions that share the same label.
We still need to determine which portals are part of the outer or the inner border. Because we already determined the outer border of the annulus in the first step this isn’t that hard. For each portal position check if the position is on the outer border. If it isn’t then it has to lie on the inner border.
And now finally we’re truly done and we can use the previously discussed methods to find the solutions to the puzzles. I hope that after reading this you agree with me when I say the true challenge today didn’t come from solving the puzzle, but parsing it.
tags: graph theory - recursive spaceOverview
Previous day Next day