Advent of Code 2016 - Day 11

Day 11: Radioisotope Thermoelectric Generators

Useful Links

Concepts and Packages Demonstrated

Breadth-First Search (BFS)Priority Queues and Heaps Classes and Objects Regular Expressions

Problem Intro
Part 1
Part 2
Results

Problem Intro

This puzzle is a classic state-space search problem. We need to move a collection of radioactive generators and their corresponding microchips between four floors of a building using an elevator. The goal is to move all items to the fourth floor in the minimum number of steps.

There are some strict rules:

The elevator can carry one or two items at a time.
The elevator must stop on each floor it passes.
A microchip will be fried if it is on the same floor as a generator that is not its own, unless its own generator is also on that floor.

Here is an example of the input data:

The first floor contains a thulium generator, a thulium-compatible microchip, a plutonium generator, and a strontium generator.
The second floor contains a plutonium-compatible microchip and a strontium-compatible microchip.
The third floor contains a promethium generator, a promethium-compatible microchip, a ruthenium generator, and a ruthenium-compatible microchip.
The fourth floor contains nothing relevant.

Part 1

What is the minimum number of steps required to bring all of the objects to the fourth floor?

This problem can be modeled as finding the shortest path in a graph, where each node in the graph is a possible state of the system (i.e., the location of all items and the elevator). Since we are looking for the minimum number of steps, a Breadth-First Search (BFS) is the perfect algorithm for the job.

Why BFS?

BFS explores a graph layer by layer. It starts at a given node and explores all of its neighbors at the present depth before moving on to the nodes at the next depth level. This guarantees that the first time we reach the goal state, we have found the shortest path in terms of the number of edges (or steps, in our case).

To make the search more efficient, we can use a priority queue (implemented with Python’s heapq module). Instead of exploring all neighbors equally, we can prioritize the states that seem more promising. A good heuristic for this is to prioritize states that are closer to the goal. In our case, the goal is to have all items on the top floor. So, a state with more items on higher floors is better.

Solution Strategy

Represent the state: Create classes to represent the state of the system. I used a Floor class to represent a single floor and an AreaState class to represent the entire building (all floors).
Floor Class: This class knows what items are on it, whether the elevator is there, and, crucially, whether it’s a safe configuration of items.
AreaState Class: This class holds a collection of Floor objects. Its most important method is next_state(), which generates all possible and valid next states from the current state.
BFS with Priority Queue:
- Start with the initial state and add it to a priority queue.
- Keep a set of states_explored to avoid cycles and redundant computations.
- In a loop, pop the state with the highest priority (i.e., the one that seems closest to the goal).
- If the popped state is the goal state, we are done.
- Otherwise, generate all valid next states and add them to the priority queue if they haven’t been explored before.

Solution Code

from __future__ import annotations, generator_stop, generators
import heapq
import logging
import os
import time
import re
from copy import deepcopy
from itertools import combinations
from dataclasses import dataclass
from typing import Sequence

# ... (Floor and AreaState class definitions as in the solution file) ...

def main():
    logging.basicConfig(level=logging.INFO, format="%(asctime)s:%(levelname)s:\t%(message)s")

    input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
    with open(input_file, mode="rt") as f:
        data = f.read().title().splitlines()

    generators_pattern = re.compile(r"[A|An] (..)\\w* Generator")
    chips_pattern = re.compile(r"[A|An] (..)\\w*-Compatible")

    all_items = set(gen + Floor.GEN_TYPE for gen in generators_pattern.findall("".join(data)))
    all_items.update(set(chip + Floor.CHIP_TYPE for chip in chips_pattern.findall("".join(data))))

    AreaState.class_init(len(data), all_items)

    floors: list[Floor] = []
    for i, line in enumerate(data, 1):
        items_found = set(gen + Floor.GEN_TYPE for gen in generators_pattern.findall("".join(line)))
        items_found.update(set(chip + Floor.CHIP_TYPE for chip in chips_pattern.findall("".join(line))))
        floors.append(Floor(floor_num=i, items=items_found, has_elevator=(i==1)))

    init_state = AreaState(floors)

    states_explored = {init_state}
    states_queue:list[AreaState] = []
    heapq.heappush(states_queue, init_state)

    iterations = 0
    while states_queue:
        iterations += 1
        current_state = heapq.heappop(states_queue)

        if current_state.score == AreaState.GOAL:
            break

        for new_state in current_state.next_state():
            if new_state not in states_explored:
                states_explored.add(new_state)
                heapq.heappush(states_queue, new_state)

    logging.info(f"Part 1 solved with {iterations} iterations.")
    logging.info(f"Final state:\n{current_state}")

if __name__ == "__main__":
    main()

Part 2

What is the minimum number of steps required to bring all of the objects, including the two new ones, to the fourth floor?

For Part 2, we are told that two new pairs of items (a generator and a microchip for elerium and dilithium) are added to the first floor. The beauty of our solution is that we can simply add these new items to our initial state and re-run the simulation. The script in the solution file only solves Part 1, but it can be easily modified to solve Part 2 by adding the new items to the all_items set and to the first floor’s items.

Results

2025-10-13 13:36:26,789:INFO:	Goal is: 56
2025-10-13 13:36:26,789:INFO:	Initial state:
F4:   | .   .   .   .   .   .   .   .   .   .   .   .   .   .   |  0 | 
F3:   | .   .   .   .   .   .   .   .   .   .   .   .   .   ThM |  3 | {'ThM'}
F2:   | CuG CuM .   .   .   .   .   .   RuG RuM .   .   ThG .   | 10 | 
F1: E | .   .   DiG DiM ElG ElM PlG PlM .   .   StG StM .   .   |  8 | 
Score: 21, Priority: 35, Parent count: 0
2025-10-13 13:36:27,170:INFO:	Part 1 solved with 1455 iterations.
2025-10-13 13:36:27,170:INFO:	Final state:
F4: E | CuG CuM DiG DiM ElG ElM PlG PlM RuG RuM StG StM ThG ThM | 56 | 
F3:   | .   .   .   .   .   .   .   .   .   .   .   .   .   .   |  0 | 
F2:   | .   .   .   .   .   .   .   .   .   .   .   .   .   .   |  0 | 
F1:   | .   .   .   .   .   .   .   .   .   .   .   .   .   .   |  0 | 
Score: 56, Priority: 0, Parent count: 67
Execution time: 0.3849 seconds

‹›

Learning Python with Advent of Code Walkthroughs