You come upon a column of four floors that have been entirely sealed off from the rest of the building except for a small dedicated lobby. There are some radiation warnings and a big sign which reads "Radioisotope Testing Facility".
According to the project status board, this facility is currently being used to experiment with Radioisotope Thermoelectric Generators (RTGs, or simply "generators") that are designed to be paired with specially-constructed microchips. Basically, an RTG is a highly radioactive rock that generates electricity through heat.
The experimental RTGs have poor radiation containment, so they're dangerously radioactive. The chips are prototypes and don't have normal radiation shielding, but they do have the ability to generate an electromagnetic radiation shield when powered. Unfortunately, they can only be powered by their corresponding RTG. An RTG powering a microchip is still dangerous to other microchips.
In other words, if a chip is ever left in the same area as another RTG, and it's not connected to its own RTG, the chip will be fried. Therefore, it is assumed that you will follow procedure and keep chips connected to their corresponding RTG when they're in the same room, and away from other RTGs otherwise.
These microchips sound very interesting and useful to your current activities, and you'd like to try to retrieve them. The fourth floor of the facility has an assembling machine which can make a self-contained, shielded computer for you to take with you - that is, if you can bring it all of the RTGs and microchips.
Within the radiation-shielded part of the facility (in which it's safe to have these pre-assembly RTGs), there is an elevator that can move between the four floors. Its capacity rating means it can carry at most yourself and two RTGs or microchips in any combination. (They're rigged to some heavy diagnostic equipment - the assembling machine will detach it for you.) As a security measure, the elevator will only function if it contains at least one RTG or microchip. The elevator always stops on each floor to recharge, and this takes long enough that the items within it and the items on that floor can irradiate each other. (You can prevent this if a Microchip and its Generator end up on the same floor in this way, as they can be connected while the elevator is recharging.)
You make some notes of the locations of each component of interest (your puzzle input). Before you don a hazmat suit and start moving things around, you'd like to have an idea of what you need to do.
When you enter the containment area, you and the elevator will start on the first floor.
For example, suppose the isolated area has the following arrangement:
The first floor contains a hydrogen-compatible microchip and a lithium-compatible microchip.
The second floor contains a hydrogen generator.
The third floor contains a lithium generator.
The fourth floor contains nothing relevant.
As a diagram (F# for a Floor number, E for Elevator, H for Hydrogen, L for Lithium, M for Microchip, and G for Generator), the initial state looks like this:
F4 . . . . .
F3 . . . LG .
F2 . HG . . .
F1 E . HM . LM
Then, to get everything up to the assembling machine on the fourth floor, the following steps could be taken:
Bring the Hydrogen-compatible Microchip to the second floor, which is safe because it can get power from the Hydrogen Generator:
F4 . . . . .
F3 . . . LG .
F2 E HG HM . .
F1 . . . . LMBring both Hydrogen-related items to the third floor, which is safe because the Hydrogen-compatible microchip is getting power from its generator:
F4 . . . . .
F3 E HG HM LG .
F2 . . . . .
F1 . . . . LM Leave the Hydrogen Generator on floor three, but bring the Hydrogen-compatible Microchip back down with you so you can still use the elevator:
F4 . . . . .
F3 . HG . LG .
F2 E . HM . .
F1 . . . . LM At the first floor, grab the Lithium-compatible Microchip, which is safe because Microchips don't affect each other:
F4 . . . . .
F3 . HG . LG .
F2 . . . . .
F1 E . HM . LM Bring both Microchips up one floor, where there is nothing to fry them:
F4 . . . . .
F3 . HG . LG .
F2 E . HM . LM
F1 . . . . . Bring both Microchips up again to floor three, where they can be temporarily connected to their corresponding generators while the elevator recharges, preventing either of them from being fried:
F4 . . . . .
F3 E HG HM LG LM
F2 . . . . .
F1 . . . . . Bring both Microchips to the fourth floor:
F4 E . HM . LM
F3 . HG . LG .
F2 . . . . .
F1 . . . . . Leave the Lithium-compatible microchip on the fourth floor, but bring the Hydrogen-compatible one so you can still use the elevator; this is safe because although the Lithium Generator is on the destination floor, you can connect Hydrogen-compatible microchip to the Hydrogen Generator there:
F4 . . . . LM
F3 E HG HM LG .
F2 . . . . .
F1 . . . . . Bring both Generators up to the fourth floor, which is safe because you can connect the Lithium-compatible Microchip to the Lithium Generator upon arrival:
F4 E HG . LG LM
F3 . . HM . .
F2 . . . . .
F1 . . . . . Bring the Lithium Microchip with you to the third floor so you can use the elevator:
F4 . HG . LG .
F3 E . HM . LM
F2 . . . . .
F1 . . . . . Bring both Microchips to the fourth floor:
F4 E HG HM LG LM
F3 . . . . .
F2 . . . . .
F1 . . . . . In this arrangement, it takes 11 steps to collect all of the objects at the fourth floor for assembly. (Each elevator stop counts as one step, even if nothing is added to or removed from it.)
In your situation, what is the minimum number of steps required to bring all of the objects to the fourth floor?
Paraphrasing all the rules about the elevator and the chips and the generators:
Some iteresting points to note:
End Goal
Considering all of this, we can approach the problem by first specifying what the end condition is, or when do we know we have the solution. Since our aim is to move all items to the fourth floor, it must mean that all the other floors are empty. Therefore,
if current_floor == 3:
for floor in range(0, 3): --> floors 0 to 2
if floor has items:
return False --> items still to be moved
return True --> Solved!
Modeling generators and microchips
One way to model them is to use their names as strings, or to trim them down to their first intial and attach either a G or M to specify their type. Another way is to model them using integers. In this case, the generator and microchip of the same element has the same absolute value, but different signs. Generators are positive, whereas microchips are negative.
Advantages of this method:
Storing states
We need some way to store the state and to track the number of moves for each state. For this, we use a heap, or to be more specific, a prioritised heap. In a prioritised heap, the elements are returned according to some priority value, which in our case is the cost. To track this value across states, we use a dictionary to store the value against the state, so that we can update it independent of the heap and also so that we can compare if we have found a better path whose value for the same state is lesser.
Initial state
The initial state is as per the input specification. We have some generators and microchips on the specified floors, and we must convert them into the integer-based representation. It is better to model the floor states as tuples since they are immutable, and convert them back into lists when carrying out the moves.
Moves: There are only two directions to move, up and down, which we represent using +1 and -1 as they map well into index operations for lists as well. The number of possible moves is based on which floor we are on. If we are on the first floor, we cannot go down, and if we are on the fourth floor, we cannot go up. Additionally, for each direction, we can take either two items or one. Since we prioritise two items over one, our moves should reflect this.
possible movements = direction in (-1, 1) if current_floor + direction is between 0 and 4
possible moves = combinations of 2 items on current_floor + combinations of 1 item on current floor
Checking valid state: For each move, we then make the changes in the floors by moving the specified items from the current to the specified floor. Then we check if this is a valid state. If it is not, we do not need to continue down the current path, and we move on to the next state from the heap. If however, this is a valid state, then we check if the move was previously stored and if its cost was more than the current one. In either case, we replace the cost with the current one and add it back on the heap. Otherwise, we have traversed this path before, and so no need to store it on the heap again.
Storing costs: We maintain a list of end-state costs so that we can choose the minimum cost.
Input specification
Each line of the input (seems) corresponds to the layout of each floor. So we can use regex to get the appropriate items on each floor.
generators are words followed by 'generator'
microchips are words followed by '-compatible microchip'
In [1]:
import re
generator_pattern = re.compile(r'(\w+) generator')
microchip_pattern = re.compile(r'(\w+)-compatible microchip')
# get all the unique names for elements
elements = set()
with open('../inputs/day11.txt', 'r') as f:
# input by floor
input_data = [
(generator_pattern.findall(line), microchip_pattern.findall(line))
for line in f.readlines()]
# add names to set
for _, microchips in input_data:
for microchip in microchips:
elements.add(microchip)
# attach elements to unique integers, signed (+) for microchips
elements_dict = {element: index + 1 for index, element in enumerate(elements)}
In [2]:
elements_dict
Out[2]:
Create floor state: flattened representation of floor each floor is a sorted tuple with generators as negative integers, and microchips as positive integers
In [3]:
input_floors = tuple(
tuple(
sorted(
tuple(elements_dict[g] for g in generators) +
tuple(-1 * elements_dict[m] for m in microchips)))
for generators, microchips in input_data)
In [4]:
input_floors
Out[4]:
Check for valid state:
In [5]:
def check_valid_state(floor):
if not floor or floor[-1] < 0:
return True
return all(-microchip in floor for microchip in floor if microchip < 0)
Heap:
The heapq module provides the heappush and heappop methods to use a list as a priority heap queue.
States:
Each state is a tuple of the form:
current floor index, floors tuple
Since at the start of the problem we are at the first floor, we start with floor index 0. We then add the initial state to the heap.
Number of moves:
To track the number of moves for each state, we create a dictionary against each state. Internally, python uses hash to index items, so this representation is quite well structured to provide us easy access to cost for each state. We start with cost = 0 for the initial state.
Heuristic:
To make the code end much (much, much) faster, we use a heuristic approach (I came to know about this on the subreddit), where we help the priority queue prioritize low-cost paths. Instead of relying only on the cost of the path, we focus on the end-state, which is the number of items on the fourth floor. The more items there are on the fourth floor, the closer we are to our solution. So we use the following heuristic -
priority = cost - items on fourth floor * CONSTANT
^
|
this is arbitrary, though larger values seem to work faster
Running the algorithm
In [6]:
from heapq import heappush, heappop
from itertools import combinations
states = []
initial_state = tuple([0, tuple(input_floors)])
heappush(states, (0, initial_state))
number_of_moves = {initial_state: 0}
In [7]:
def run():
while states:
_, current_state = heappop(states)
current_floor, floors_tuple = current_state
# check for end state
if current_floor == 3 and all(len(floor) == 0 for floor in floors_tuple[:-1]):
return number_of_moves[current_state]
movements = [
direction for direction in (-1, 1)
if 0 <= current_floor + direction < 4]
moves =\
list(combinations(floors_tuple[current_floor], 2)) +\
list(combinations(floors_tuple[current_floor], 1))
for move in moves:
for direction in movements:
# convert the floor tuple into a mutable list and implement move
floors = list(floors_tuple)
floors[current_floor] = tuple(
x for x in floors_tuple[current_floor] if x not in move)
floors[current_floor + direction] = tuple(
sorted(floors_tuple[current_floor + direction] + move))
# check for valid move
if not all((
check_valid_state(floors[current_floor]),
check_valid_state(floors[current_floor + direction]))):
continue
# create state and cost, check if previously encountered
next_move = (current_floor + direction, tuple(floors))
cost = number_of_moves[current_state] + 1
if next_move not in number_of_moves or cost < number_of_moves[next_move]:
number_of_moves[next_move] = cost
heappush(states, (cost - len(floors[3]) * 25, next_move))
In [8]:
print('answer', run())
You step into the cleanroom separating the lobby from the isolated area and put on the hazmat suit.
Upon entering the isolated containment area, however, you notice some extra parts on the first floor that weren't listed on the record outside:
An elerium generator.
An elerium-compatible microchip.
A dilithium generator.
A dilithium-compatible microchip.
These work just like the other generators and microchips. You'll have to get them up to assembly as well.
What is the minimum number of steps required to bring all of the objects, including these four new ones, to the fourth floor?
In [9]:
elements.add('elerium')
elements.add('dilithium')
elements_dict = {element: index + 1 for index, element in enumerate(elements)}
In [10]:
input_floors = list(
list(
list(elements_dict[g] for g in generators) +
list(-1 * elements_dict[m] for m in microchips))
for generators, microchips in input_data)
input_floors[0].append(elements_dict['elerium'])
input_floors[0].append(-elements_dict['elerium'])
input_floors[0].append(elements_dict['dilithium'])
input_floors[0].append(-elements_dict['dilithium'])
input_floors = tuple(tuple(sorted(floor)) for floor in input_floors)
In [11]:
states = []
initial_state = tuple([0, tuple(input_floors)])
heappush(states, (0, initial_state))
number_of_moves = {initial_state: 0}
In [12]:
print('answer', run())
== END ==