Crate aoc_2016_day_24

source ·
Expand description

Advent of Code 2016: Day 24: Air Duct Spelunking

https://adventofcode.com/2016/day/24

Input

Map with # for wall tiles, . for open tiles, and digits 0 to 9 for points of interest. Starting point is always 0.

Part one

Work out the shortest route starting at 0 and passing through all points of interest.

Part two

Same as part one, while also returning to 0 afterwards.

Algorithm

This works in two steps:

  • Work out the shortest route from every point of interest to every other. This uses a simple breadth first path-finding algorithm, starting from each of the points and recording the shortest distance to each of the others.

  • Use search::PrioritySearch to find the shortest path connecting them. As an optimisation, we sort the routes used as search nodes, except for the last item, since we don’t care about the order, only the distance and the point we are setting off from for the next leg.

Modules

Functions