Module aoc::year2016::day11

Radioisotope Thermoelectric Generators

Solves using a BFS from the starting position where each next state is the possible elevator moves either one floor up or down. This was faster than using A* with a heuristic.

A huge critical optimization is the observation that generators and chips are fungible. Only the total number of generators and chips on each floor is important. The rules for a valid floor are either:

• Any amount of microchips only with no generators.
• The amount of generators is greater than the number of microchips, ensuring that each chip is paired with its generator.

This allows us to efficiently memoize previously seen states and reject any that we’ve seen before extremely quickly. Other optimizations:

• If we can move 2 items up, then skip only moving 1 item up.
• If we can move 1 item down, then skip moving 2 items down
• If floor 1 is empty then don’t move items back down to it, similarly if both floor 1 and floor 2 are empty then don’t move items to them.

As a further optimization we assume that there are no more than 15 generators and microchips and store the total packed into a single byte for each floor. This reduces the size of each state to only 8 bytes making it quick to copy and hash.

Structs

• Floor 🔒
• State

Functions

• bfs 🔒
• parse
• part1
• part2