Advent of Code, Day 12-15

The puzzles to start this week have not disappointed! They included two different pathfinding exercises and an interesting string insertion problem.

The first pathfinding puzzle was quite tricky. Given a set of relationships between big and little 'caves,' the goal was to count the number of paths from start to end that entered small caves only once, and then to also count the paths when allowed to enter one of the small caves twice.

Sample set of relationships:

start-A
start-b
A-c
A-b
b-d
A-end
b-end

My strategy was to build a dictionary where each key is a cave name ('A', 'c', 'end', etc) and the associated value is a list of possible exits from that cave. I kept track of the path being followed, and after entering a cave, recursively iterated through its list of exits to find valid ones. If a valid exit was found, that cave was 'entered' and its list of exits evaluated. This was a tricky pattern to figure out, particularly with regards to what constituted a valid exit.

My day 12 code on GitHub

The other pathfinding exercise (day 15) introduced me to Dijkstra's Algorithm for shortest path finding. Given a grid of integer values, the goal was to come up with the lowest sum of values moving up/down/left/right between the upper left corner (start) and the bottom right corner (finish).

At first, I was unsure how to go about solving the puzzle. After brainstorming, I decided to make use of Google, and quickly discovered a number of likely algorithm candidates. After reading about a few, it became clear that Dijkstra's Algorithm was likely my best bet.

My next search was for a clear explanation of the steps to this algorithm. I didn't want to look at pseudocode; rather, I wanted an illustration of how the algorithm works, so I could try to code it myself. I found a great article with some images that explained each step, on which I based my implementation: Implementing Dijkstra's Algorith in Python. Although this article goes on to code the algorithm, I stopped reading halfway through and headed into PyCharm to get coding.

Because of the number of attributes I wanted to track for each node (location on the grid), I wrote a small class and created an object for each node. I was then able to easily track if the node had been visited, it's value and coordinates, and the sum of the shortest (lowest) path between that node and the start.

At the start of each step of the algorithm, it is necessary to search for the node with the lowest distance value that hasn't already been visited. For a 100 x 100 grid, this was trivial, but the puzzle's second part expanded the grid to 500 x 500. Since this was too many nodes to search through in their entirety at each step, I chose to add every active node (any node whose distance had been evaluated but which hadn't been visited yet) to a list, and only searched through that list during each step. This list grew to 600-700 nodes during processing, but that's way better than 250,000 searches in each of the 250,000 steps!

My day 15 code on GitHub