Solution for Advent of Code 2016 - Day 24: Air Duct Spelunking

Link to the puzzle text

Part 1

In this puzzle, we are in a maze and have to find the shortest path containing all of certain numbered fields. The order in which we visit the fields is free to choose.

To find the shortest permutation, we iterate over all permutations and calculate the total length. For each permutation like "0123", we divide it into several breadth-first searches, first from "0" to "1", then "1" to "2" and so on. The search itself could be copied from previous solutions and a heuristic was not needed.

total_length = 0
for (start, end) in zip(route, route[1:]):
    start_pos = number_positions[start]
    total_length += calc_length(...)
min_length = min(min_length, total_length) 

To improve the performance, we cache the distances from each numbered field to all others. This cuts down the number of searches we have to do. Additionally we can stop a calculation for a permutation once our length until now is larger than the minimal length until now.

Part 2

For part 2, we need the shortest permutation where we additionally return to our starting position.

During the search over all permutations, we simply added the return to the start to all paths before calculating the total length. The previous solution was fast enough without any additional changes.

if return_to_start:
    route.append("0")

Link to my solutions