Advent of Code 2016 - Day 11 - Radioisotope Thermoelectric Generators

On the eleventh day of Advent of Code 2016, we are tasked with moving all the supplied Generators and Microchips to the top floor using a single elevator.

Having since read through some of the AoC subreddit, I can see that this is an infamous AoC day puzzle. The puzzle description itself is rather detailed, so I would delegate to this to get an understanding of the problem at hand. In summary, we are required to move all the Generators and Microchips to the top floor of a four-floor building. To achieve this, we are provided with a single elevator, which can go up or down one level at a time, moving one or two objects in the process. There are a couple of rules surrounding how a floor can be left upon each transition (which the problem definition lays out). This initially reminded me of the Chicken Crossing puzzle.

Part 1

For part one, we are required to determine the minimum number of steps required to bring all of the objects to the fourth floor. We will begin (as we always do) by parsing the supplied input (the initial object floor states) into a representation we can process going forward.

def parse_floors(input):
    return [set(re.findall(r'(\w+)(?:-compatible)? (microchip|generator)', line))
            for line in input.splitlines()]

This will return a list of all the floors’ initial states (zero-indexed) as sets in the form NAME microchip and NAME generator. From here, we can begin to model the rules surrounding a valid floor transition.

def is_valid_transition(floor):
    return len(set(type for _, type in floor)) < 2 or \
           all((obj, 'generator') in floor
               for (obj, type) in floor
               if type == 'microchip')

At a high level, a floor is deemed valid if it is empty, only contains a single type (generators/microchips) of object, or, if there are multiple types, every microchip has its associated generator on that floor. With the ability to now verify if a supplied floor is valid or not, we can continue modelling a means to generate all the possible transitions based on a supplied state.

def next_states(state):
    moves, elevator, floors = state

    possible_moves = chain(combinations(floors[elevator], 2), combinations(floors[elevator], 1))

    for move in possible_moves:
        for direction in [-1, 1]:
            next_elevator = elevator + direction
            if not 0 <= next_elevator < len(floors):
                continue

            next_floors = floors.copy()
            next_floors[elevator] = next_floors[elevator].difference(move)
            next_floors[next_elevator] = next_floors[next_elevator].union(move)

            if (is_valid_transition(next_floors[elevator]) and is_valid_transition(next_floors[next_elevator])):
                yield (moves + 1, next_elevator, next_floors)

The function above takes in a state (total moves performed, position of the elevator, and floor objects) as a tuple and yields all the possible valid state transitions we could perform from this position. Thanks to Python’s out-of-the-box combinatorics support, we can leverage this to simplify our solution. With the ability to generate the next possible states from a given initial state, we now need a means of verifying if we have met our end goal state.

def is_all_top_level(floors):
    return all(not floor
               for number, floor in enumerate(floors)
               if number < len(floors) - 1)

From here, we can now create a BFS implementation that traverses all the possible state transitions until it finally meets our end goal state. Using BFS, we can be sure that this results in the shortest possible move total.

def min_moves_to_top_level(floors):
    seen = set()
    queue = deque([(0, 0, floors)])

    while queue:
        state = queue.popleft()
        moves, _, floors = state

        if is_all_top_level(floors):
            return moves

        for next_state in next_states(state):
            if (key := count_floor_objects(next_state)) not in seen:
                seen.add(key)
                queue.append(next_state)

But wait, what is this count_floor_objects function?! So… to cut a long story short, I initially went about running this solution pruning any exact floor states that we had already encountered to help performance. This, sadly, did not provide a solution reaching the end goal in an adequate amount of time 😢. After pondering other techniques to help effectively prune the search space, I resorted to finding some clues online. The clue I found asked the question, ‘what classifies a unique floor state?’. After even more pondering and experimentation, I finally landed on what this clue meant.

def count_floor_objects(state):
    _, elevator, floors = state
    return elevator, tuple(tuple(Counter(type for _, type in floor).most_common()) for floor in floors)

Providing that the floor state is valid (which all are when returned from next_states), we do not care about the name of the actual objects. What this means is that a floor can simply be represented as a unique state based on the total number of generators and microchips that are on that floor (each pair is replaceable). In doing this, we cut the search space down dramatically 🎉.

With all the building blocks now in place, we can parse the input and call min_moves_to_top_level. In doing so, we are returned the desired answer to this super-tough problem 🌟!

def part1(input):
    return min_moves_to_top_level(parse_floors(input))

Part 2

Fortunately, part two is only a small spin on what is asked in part one. We are now asked to calculate the minimum number of moves required based on the input state, along with two additional object pairs found on the first floor. With a small addition, we can answer this question using the same min_moves_to_top_level function 🌟.

def part2(input):
    floors = parse_floors(input)
    floors[0] = floors[0].union([('elerium', 'generator'), ('elerium', 'microchip'),
                                 ('dilithium', 'generator'), ('dilithium', 'microchip')])
    return min_moves_to_top_level(floors)

What a day!