Solution for Advent of Code 2016 - Day 11: Radioisotope Thermoelectric Generators

Link to the puzzle text

Part 1

In this puzzle we must create a plan for moving chips and generators to a specific floor. The only action we have is to move either one or two objects with an elevator from one floor to the next. Certain configurations of chips and generators on the same floor are prohibited.

 We solve this via an A* search. We model our state space as a dictionary mapping the objects and the elevator to their current floor. In each step we move the elevator together with one or two objects to an adjacent floor. The actions are checked if they result in a valid state. Once all objects are on the top floor, we return the number of actions required to reach this state.

To speed up the search, we use a simple heuristic. In each step we measure the total distance of all objects to the top floor and divide it by two, since we can bring up to two elements. We additionally use a set of visited states with a hash. This function counts the number of chips and generators on each floor and returns a string containining this information.

Part 2

For part 2, we have four additional objects on floor 1. We update our object-to-floor mapping by setting them manually and run the search again. Since A* was quick enough, no further action was needed.

Link to my solutions