Solution for Advent of Code 2016 - Day 17: Two Steps Forward

Link to the puzzle text

Part 1

In this puzzle we need to find a way through a maze. The difference to other route finding puzzle are the available directions each step. To get the possible directions, we MD5-hash the current route prepended with a seed. The first 4 characters of the hash tell us, if a direction is possible. We need to find the shortest path from the top-left to the bottom right corner.

We keep a list of all currently available paths. In a loop, we take the currently shortest path, check for the possible directions (both by the MD5-hash and restricting paths to the 4x4 grid). If a path leads to the target location, we return its path as the solution.

Part 2

In part 2, we need to find the longest path still leading to the target. Instead of returning the first found path as previously, we save all valid start-target to a list and continue searching. Once there are no longer any paths to check left, we return the longest path as the solution. The solution for part 1 is still available as the first path added to the valid route list.

Link to my solutions