On Day 11 we are dealing with Radioisotope Thermoelectric Generators and microchips. It is actually an optimization task. We have a layout of building with information which RTGs and microchips are placed on which floors. There are 4 floor, one elevator and you need to move all microchips and RTGs to the fourth floor.
But there are some rules you need to follow:
I may missed some rules here, but it is better to just read the whole description on the puzzle page.
We have an input that looks like this:
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.
So we have two different microchips and two corresponding RTGs. Our task is to tell what is the minimal number of steps to move all RTGs and microchips to the fourth floor (following the rules).
This task can be expressed as a graph problem. We have some entry state described in our input file. This will be the positions of RTGs, microchips and elevator. Then for a given state we can make a decision what is best move we can do. Each possible move will take as to another state. States are represented as graph nodes and edges mean that it is possible to move from one state to another.
If we express this problem as a graph, we can solve it with some graph algorithm like Breadth-First Search (BFS). Additional challenge here is that we can have a lot of states to consider and running time can be slow. For the example input we have 5 items to track (2 microchips, 2 RTGs and an elevator). Each item can be on floors 1, 2, 3 or 4, so there are 4^5 = 1024 states (not all are possible). It is not much, but the real input has 11 items which gives us 4^11 = 4194304 states. And in Part B it is 15 items and 4^15 = 1073741824 states. We need to find some way to limit the number of states our algorithm will consider.
Let’s start with parsing the input and building initial state:
@keys = []
def parse_input(filename)
data = File.readlines(filename, chomp: true)
floor_mapping = { "first" => 1, "second" => 2, "third" => 3, "fourth" => 4 }
state = { elevator: 1 }
data.each do |line|
match = line.match(/The ([a-z]+?) floor/)
floor_number = floor_mapping[match[1]]
chips = line.scan(/a ([a-z]+?)\-compatible microchip/).flatten.map { |name| "#{name[0].upcase}M" }
generators = line.scan(/a ([a-z]+?) generator/).flatten.map { |name| "#{name[0].upcase}G" }
chips.each { |chip| @keys.push(chip) }
generators.each { |generator| @keys.push(generator) }
state[floor_number] = {
chips: chips,
generators: generators
}
end
@keys.sort!
state
end
For our test input, our state will look like this:
{
:elevator=>1,
1=>{
:chips=>["HM", "LM"],
:generators=>[]
},
2=>{
:chips=>[],
:generators=>["HG"]
},
3=>{
:chips=>[],
:generators=>["LG"]
},
4=>{
:chips=>[],
:generators=>[]
}
}
We keep track of our elevator and which chips and RTGs are on which floor. Not all states are possible. You can’t keep HM chip and LG generator on the same floor. We can implement a method to check if state is valid:
def valid?(state)
(1..4).all? do |floor_number|
state[floor_number][:chips].all? do |chip|
state[floor_number][:generators].include?(chip.gsub("M", "G")) || state[floor_number][:generators].empty?
end
end
end
Here we are iterating over each floor and checking if microchip have a corresponding generator. Or that no generator is present on this floor.
When considering what moves we can do, we need to keep in mind that we can travel only one floor at a time. So the only possible moves we can consider are moving 1 or 2 items one floor up, or one floor down. We can then implement methods for generating such states from the current one:
def clone_state(state)
hash = { elevator: state[:elevator] }
(1..4).each do |floor_number|
hash[floor_number] = {
chips: state[floor_number][:chips].clone.sort,
generators: state[floor_number][:generators].clone.sort
}
end
hash
end
def move_up(state, keys)
new_state = clone_state(state)
new_state[:elevator] += 1
keys.each do |key|
current_floor_number = (1..4).detect { |floor_number| state[floor_number][:chips].include?(key) || state[floor_number][:generators].include?(key) }
type = key.end_with?("M") ? :chips : :generators
if current_floor_number + 1 > 4
return state
else
new_state[current_floor_number][type].delete(key)
new_state[current_floor_number + 1][type].push(key)
end
end
new_state
end
def move_down(state, keys)
new_state = clone_state(state)
new_state[:elevator] -= 1
keys.each do |key|
current_floor_number = (1..4).detect { |floor_number| state[floor_number][:chips].include?(key) || state[floor_number][:generators].include?(key) }
type = key.end_with?("M") ? :chips : :generators
if current_floor_number - 1 < 1
return state
else
new_state[current_floor_number][type].delete(key)
new_state[current_floor_number - 1][type].push(key)
end
end
new_state
end
We can call it like that:
new_state = move_up(state, ["HM"])
puts new_state.inspect
puts valid?(new_state)
Starting from our initial state we will get:
{
:elevator=>1,
1=>{
:chips=>["LM"],
:generators=>[]
},
2=>{
:chips=>["HM"],
:generators=>["HG"]
},
3=>{
:chips=>[],
:generators=>["LG"]
},
4=>{
:chips=>[],
:generators=>[]
}
}
true
Now we have both HM chip and HG generator on second floor and our new state is valid.
We can implement a method to generate all possible new states from the current one:
def next_states(state)
results = []
current_floor_number = state[:elevator]
floor_keys = state[current_floor_number][:chips] + state[current_floor_number][:generators]
permutations = (floor_keys.permutation(1).to_a + floor_keys.permutation(2).to_a).map { |permutation| permutation.sort }.uniq
permutations.each do |keys|
results.push(move_up(state, keys))
results.push(move_down(state, keys))
end
results.select { |state| valid?(state) }.uniq
end
We can only start on the floor where the elevator is currently. We can combine available items there and generate 1 item permutations and also 2 item permutations. Then for each permutation we can consider moving them up or down. This will generate the list of new states and we need to filter out only valid states.
Let’s now see the final solution:
@keys = []
def parse_input(filename)
data = File.readlines(filename, chomp: true)
floor_mapping = { "first" => 1, "second" => 2, "third" => 3, "fourth" => 4 }
state = { elevator: 1 }
data.each do |line|
match = line.match(/The ([a-z]+?) floor/)
floor_number = floor_mapping[match[1]]
chips = line.scan(/a ([a-z]+?)\-compatible microchip/).flatten.map { |name| "#{name[0].upcase}M" }
generators = line.scan(/a ([a-z]+?) generator/).flatten.map { |name| "#{name[0].upcase}G" }
chips.each { |chip| @keys.push(chip) }
generators.each { |generator| @keys.push(generator) }
state[floor_number] = {
chips: chips,
generators: generators
}
end
@keys.sort!
state
end
def draw_layout(state)
4.downto(1) do |floor_number|
row = Array.new(@keys.size + 2, ". ")
row[0] = "F#{floor_number} "
row[1] = "E " if state[:elevator] == floor_number
@keys.each_with_index do |key, index|
if state[floor_number][:generators].include?(key)
row[2 + index] = key.ljust(3, " ")
elsif state[floor_number][:chips].include?(key)
row[2 + index] = key.ljust(3, " ")
end
end
puts row.join(" ")
end
end
def valid?(state)
(1..4).all? do |floor_number|
state[floor_number][:chips].all? do |chip|
state[floor_number][:generators].include?(chip.gsub("M", "G")) || state[floor_number][:generators].empty?
end
end
end
def clone_state(state)
hash = { elevator: state[:elevator] }
(1..4).each do |floor_number|
hash[floor_number] = {
chips: state[floor_number][:chips].clone.sort,
generators: state[floor_number][:generators].clone.sort
}
end
hash
end
def move_up(state, keys)
new_state = clone_state(state)
new_state[:elevator] += 1
keys.each do |key|
current_floor_number = (1..4).detect { |floor_number| state[floor_number][:chips].include?(key) || state[floor_number][:generators].include?(key) }
type = key.end_with?("M") ? :chips : :generators
if current_floor_number + 1 > 4
return state
else
new_state[current_floor_number][type].delete(key)
new_state[current_floor_number + 1][type].push(key)
end
end
new_state
end
def move_down(state, keys)
new_state = clone_state(state)
new_state[:elevator] -= 1
keys.each do |key|
current_floor_number = (1..4).detect { |floor_number| state[floor_number][:chips].include?(key) || state[floor_number][:generators].include?(key) }
type = key.end_with?("M") ? :chips : :generators
if current_floor_number - 1 < 1
return state
else
new_state[current_floor_number][type].delete(key)
new_state[current_floor_number - 1][type].push(key)
end
end
new_state
end
def next_states(state)
results = []
current_floor_number = state[:elevator]
floor_keys = state[current_floor_number][:chips] + state[current_floor_number][:generators]
permutations = (floor_keys.permutation(1).to_a + floor_keys.permutation(2).to_a).map { |permutation| permutation.sort }.uniq
permutations.each do |keys|
results.push(move_up(state, keys))
results.push(move_down(state, keys))
end
results.select { |state| valid?(state) }.uniq
end
def finished?(state)
score(state) == @keys.size * (16 ** 3)
end
def score(state)
(1..4).map do |floor_number|
(state[floor_number][:chips].size + state[floor_number][:generators].size) * (16 ** (floor_number - 1))
end.sum
end
def encode_state(state)
positions = {}
(1..4).each do |floor_number|
state[floor_number][:chips].each do |chip|
positions[chip] = floor_number
end
state[floor_number][:generators].each do |generator|
positions[generator] = floor_number
end
end
encoding = @keys.map do |key|
positions[key]
end
encoding.unshift(state[:elevator])
encoding.join
end
state = parse_input("11test.txt")
@queue = [[state, 0]]
@visited = { encode_state(state) => true }
max = 0
while !@queue.empty?
current_state, time = @queue.shift
if finished?(current_state)
puts "result = #{time}, #{score(current_state).to_s(16)}"
break
end
if score(current_state) > max
max = score(current_state)
puts "new max = #{max.to_s(16)}"
end
next_states(current_state).sort { |state| -score(state) }.reject { |state| max - score(state) > 8192 }.each do |state|
if !@visited[encode_state(state)]
@queue.push([state, time + 1])
@visited[encode_state(state)] = true
end
end
end
The last loop is our BFS implementation. We start with empty queue, we add there our initial state with 0 steps. In each iteration we peek first element from the queue, we check if we reached our desired final state and if not we add all possible states to the queue.
There are couple of improvements. We have helper method encode_state that is converting our state (hash object) to a string and this will be used as a hash key in @visited hash. We also have score method that returns an arbitrary score for given state. As you can imagine a state with more items closer to the fourth floor is better than state where all items are on the first floor. It works like this, we count number of items on a given floor and use it as next digit in hexadecimal system.
If we look again at our initial state we 2 items on first floor, 1 item on second floor and 1 item on third floor. Our score will be 2 * 16 ^ 0 + 1 * 16 ^ 1 + 1 * 16 ^ 2 = 2 + 16 + 256 = 274, and 112 in hex. By looking single digits of hex score you can see how many items are on each floor as each digit represents just one floor.
Now that we have score method, when exploring new states we can sort them by score and explore those with higher score first. That’s exactly what our BFS implementation is doing.
Using score method we can easily check if the current state is our target. We want to move all items to the last floor, so the most significant digit of our score must be equal to total number of items and rest of digits should be 0. finished? method is doing just that.
One more optimization that we can do is to track the current max score we found so far and then reject states that are way lower. What way lower means? What I consider as way lower is when there is 2 items less on the fourth floor. If you already found a state with 6 items on fourth floor and then explore another state from the queue and it has just 4 items on fourth floor we can skip it. We can still consider states that have just one item less, because you need to take at least one item with you to use the elevator.
How can you check if given state has 2 items less on fourth floor? Well, you can check the most significant digit. Or you can check the difference between two scores. If it is larger than 2 * 16 ^ 3 = 8192.
That’s it. It is probably not the fastest solution, but it calculates the answer in less than 10 seconds. It is fine for me.
In second part we need to do the same thing, but for more items. We need to add additional 4 items to our input. Here is the final solution:
@keys = []
def parse_input(filename)
data = File.readlines(filename, chomp: true)
floor_mapping = { "first" => 1, "second" => 2, "third" => 3, "fourth" => 4 }
state = { elevator: 1 }
data.each do |line|
match = line.match(/The ([a-z]+?) floor/)
floor_number = floor_mapping[match[1]]
chips = line.scan(/a ([a-z]+?)\-compatible microchip/).flatten.map { |name| "#{name[0].upcase}M" }
generators = line.scan(/a ([a-z]+?) generator/).flatten.map { |name| "#{name[0].upcase}G" }
chips.each { |chip| @keys.push(chip) }
generators.each { |generator| @keys.push(generator) }
state[floor_number] = {
chips: chips,
generators: generators
}
end
@keys.sort!
state
end
def draw_layout(state)
4.downto(1) do |floor_number|
row = Array.new(@keys.size + 2, ". ")
row[0] = "F#{floor_number} "
row[1] = "E " if state[:elevator] == floor_number
@keys.each_with_index do |key, index|
if state[floor_number][:generators].include?(key)
row[2 + index] = key.ljust(3, " ")
elsif state[floor_number][:chips].include?(key)
row[2 + index] = key.ljust(3, " ")
end
end
puts row.join(" ")
end
end
def valid?(state)
(1..4).all? do |floor_number|
state[floor_number][:chips].all? do |chip|
state[floor_number][:generators].include?(chip.gsub("M", "G")) || state[floor_number][:generators].empty?
end
end
end
def clone_state(state)
hash = { elevator: state[:elevator] }
(1..4).each do |floor_number|
hash[floor_number] = {
chips: state[floor_number][:chips].clone.sort,
generators: state[floor_number][:generators].clone.sort
}
end
hash
end
def move_up(state, keys)
new_state = clone_state(state)
new_state[:elevator] += 1
keys.each do |key|
current_floor_number = (1..4).detect { |floor_number| state[floor_number][:chips].include?(key) || state[floor_number][:generators].include?(key) }
type = key.end_with?("M") ? :chips : :generators
if current_floor_number + 1 > 4
return state
else
new_state[current_floor_number][type].delete(key)
new_state[current_floor_number + 1][type].push(key)
end
end
new_state
end
def move_down(state, keys)
new_state = clone_state(state)
new_state[:elevator] -= 1
keys.each do |key|
current_floor_number = (1..4).detect { |floor_number| state[floor_number][:chips].include?(key) || state[floor_number][:generators].include?(key) }
type = key.end_with?("M") ? :chips : :generators
if current_floor_number - 1 < 1
return state
else
new_state[current_floor_number][type].delete(key)
new_state[current_floor_number - 1][type].push(key)
end
end
new_state
end
def next_states(state)
results = []
current_floor_number = state[:elevator]
floor_keys = state[current_floor_number][:chips] + state[current_floor_number][:generators]
permutations = (floor_keys.permutation(1).to_a + floor_keys.permutation(2).to_a).map { |permutation| permutation.sort }.uniq
permutations.each do |keys|
results.push(move_up(state, keys))
results.push(move_down(state, keys))
end
results.select { |state| valid?(state) }.uniq
end
def finished?(state)
score(state) == @keys.size * (16 ** 3)
end
def draw_path(state)
results = []
results.push(state)
while @paths[state]
results.push(@paths[state])
state = @paths[state]
end
results.reverse.each do |state|
draw_layout(state)
puts "=" * 30
end
end
def score(state)
(1..4).map do |floor_number|
(state[floor_number][:chips].size + state[floor_number][:generators].size) * (16 ** (floor_number - 1))
end.sum
end
def encode_state(state)
positions = {}
(1..4).each do |floor_number|
state[floor_number][:chips].each do |chip|
positions[chip] = floor_number
end
state[floor_number][:generators].each do |generator|
positions[generator] = floor_number
end
end
encoding = @keys.map do |key|
positions[key]
end
encoding.unshift(state[:elevator])
encoding.join
end
state = parse_input("11.txt")
state[1][:chips].push("EM")
state[1][:chips].push("DM")
state[1][:generators].push("EG")
state[1][:generators].push("DG")
state[1][:chips].sort!
state[1][:generators].sort!
@keys.push("EM")
@keys.push("EG")
@keys.push("DM")
@keys.push("DG")
@keys.sort!
@queue = [[state, 0]]
@visited = { encode_state(state) => true }
max = 0
while !@queue.empty?
current_state, time = @queue.shift
if finished?(current_state)
puts "result = #{time}, #{score(current_state).to_s(16)}"
break
end
if score(current_state) > max
max = score(current_state)
puts "new max = #{max.to_s(16)}"
end
next_states(current_state).sort { |state| -score(state) }.reject { |state| max - score(state) > 8192 }.each do |state|
if !@visited[encode_state(state)]
@queue.push([state, time + 1])
@visited[encode_state(state)] = true
end
end
end
I didn’t change anything in the BFS code, so now it takes much longer to find a solution. Around one minute.
Btw, I also included some code to draw the current layout. I used it for debugging, but it is not used in the solution.