On Day 16 we have another puzzle that took me a lot of time comparing to other ones.
We are working with a graph of rooms containing valves. Opening a valve releases certain amount of pressure and our task is to release as much pressure as possible in 30 minutes. It takes one minute to move to the next room and one minute to open a valve. Not all rooms have valves or actually those valves release 0 pressure.
Since our task is to maximize released pressure we can completely ignore those rooms. We just need to consider them when calculating length of path between rooms with valves that can release positive pressure.
Here is an example input:
Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
Valve BB has flow rate=13; tunnels lead to valves CC, AA
Valve CC has flow rate=2; tunnels lead to valves DD, BB
Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
Valve EE has flow rate=3; tunnels lead to valves FF, DD
Valve FF has flow rate=0; tunnels lead to valves EE, GG
Valve GG has flow rate=0; tunnels lead to valves FF, HH
Valve HH has flow rate=22; tunnel leads to valve GG
Valve II has flow rate=0; tunnels lead to valves AA, JJ
Valve JJ has flow rate=21; tunnel leads to valve II
We have 6 rooms / valves with positive flow rate: BB, CC, DD, EE, HH and JJ. So basically we can define our task as finding the permutation of this set {BB, CC, DD, EE, HH, JJ} that will have the maximum pressure released.
We can use naive approach and check each permutation. The only problem is that for set of size n there n! (n factorial) permutations. For our example input that will be 720, which is not bad. But the real input has 15 valves and 15! = 1307674368000.
This is a NP-hard problem and there are no fast solutions. All usual graph algortihms won’t work here, because they are always about finding minimal value and not maximal. The only way to make it fast is to eliminate permutations that are nowhere close to being maximums.
We can do a recursive method that will explore the graph of possible states to the final solution. Each state can be described with the current node (where we are), list of valves that are still closed, time left and total released pressure.
Our starting start will be:
["BB", "CC", "DD", "EE", "HH", "JJ"] (array of closed valves)When we reach to 0 minutes left we return from our recursive method the total pressure released so far. If we still have time we need to explore what is the best next move. We need to open each valve that is still closed and take the maximum pressure released.
Here is the code for the recursive method:
def solve(graph, start, closed = [], minutes = 30, total = 0)
return total if closed.empty?
next_moves = closed.map do |key|
left = minutes - path(graph, start, key) - 1
pressure = @valves[key] * left
if left < 0
next
end
[key, left, pressure]
end.compact
return total if next_moves.size == 0
results = next_moves.sort_by { |item| item[2] }.map do |(key, left, pressure)|
solve(graph, key, closed - [key], left, total + pressure)
end
results.max
end
# Select only valves with positive flow rate
closed = @valves.map do |id, value|
value > 0 ? id : nil
end.compact
puts solve(d, "AA", closed)
If all valves our open we return total pressure. Then we generate next possible moves. We iterate over still closed valves, we calculate how many minutes will take to reach that valve (we have helper method path) and open it. We also calculate how much total pressure will be released from that valve, which is just flow rate multiplied by minutes left.
If the next move has 0 or more minutes left we can consider it. If it has negative time, we need to skip it as it is not possible to open such valve in our 30 minutes time limit.
If there are no more next moves to consider we need to return from our recursion. If we have moves, we call our function for all new states and we take the maximum value.
We can also sort our next moves by the time left.
I was struggling with this task because initially I forgot about breaking recursion when time left is negative. In the example test case it was possible to open all the valves, so I thought it is the same for the actual input. Lesson learn is to read description carefully :)
I mentioned the helper method path that can return the length of path between two nodes. We can use Floyd-Warshall algorithm to calculate path lengths between all graph nodes:
def floyd(w)
n = w.size
d = w.clone
d_prime = d.clone
n.times do |k|
n.times do |i|
n.times do |j|
d_prime[i][j] = [d[i][j], d[i][k] + d[k][j]].min
end
end
end
d_prime
end
def path(d, key1, key2)
d[key_to_idx(key1)][key_to_idx(key2)]
end
d = floyd(graph)
Here is my full code. Spoiler alert: it is not pretty.
data = File.readlines("16.txt", chomp: true)
@valves = {}
tunnels = {}
@nodes = []
data.each do |elem|
match = elem.match(/Valve (.+?) has flow rate=(\d+); tunnels? leads? to valves? (.+)/)
id = match[1]
rate = match[2].to_i
edges = match[3].split(",").map(&:strip)
@nodes.push(id)
@valves[id] = rate
tunnels[id] = edges
end
@nodes.sort!
def key_to_idx(key)
@nodes.index(key)
end
def idx_to_key(idx)
@nodes[idx]
end
graph = []
@nodes.size.times { graph.push(Array.new(@nodes.size, Float::INFINITY) ) }
tunnels.each do |key, edges|
edges.each do |edge|
graph[key_to_idx(key)][key_to_idx(edge)] = 1
end
end
graph.size.times do |i|
graph[i][i] = 0
end
def floyd(w)
n = w.size
d = w.clone
d_prime = d.clone
n.times do |k|
n.times do |i|
n.times do |j|
d_prime[i][j] = [d[i][j], d[i][k] + d[k][j]].min
end
end
end
d_prime
end
def path(d, key1, key2)
d[key_to_idx(key1)][key_to_idx(key2)]
end
d = floyd(graph)
def solve(graph, start, closed = [], minutes = 30, total = 0)
return total if closed.empty?
next_moves = closed.map do |key|
left = minutes - path(graph, start, key) - 1
pressure = @valves[key] * left
if left < 0
next
end
[key, left, pressure]
end.compact
return total if next_moves.size == 0
results = next_moves.sort_by { |item| item[2] }.map do |(key, left, pressure)|
solve(graph, key, closed - [key], left, total + pressure)
end
results.max
end
closed = @valves.map do |id, value|
value > 0 ? id : nil
end.compact
puts solve(d, "AA", closed)
In the second part we have less time, only 26 minutes, but this time we have two players (you and elephant) that can open valves. We can still reuse most of the code from the first part, but we need to extend the description of our state. We now need to track current nodes for both human and elephant and how much time was left for human and for elephant. When exploring next moves, we need to generate all possible moves for human and elephant and then combine them.
Here is the code for combining moves:
def combine_moves(human_moves, elephant_moves)
all_moves = []
visited_moves = {}
if human_moves.size == 0
elephant_moves.each do |move2|
all_moves.push([nil, move2])
end
end
if elephant_moves.size == 0
human_moves.each do |move1|
all_moves.push([move1, nil])
end
end
human_moves.each do |move1|
elephant_moves.each do |move2|
next if move1[0] == move2[0]
next if visited_moves[[move2[0], move2[1]]]
all_moves.push([move1, move2])
visited_moves[[move1[0], move1[1]]] = true
end
end
all_moves.sort_by! { |elem| (elem[0] ? elem[0][2] : 0) + (elem[1] ? elem[1][2] : 0) }.reverse
end
In the beginning we consider cases when only one player is left with some moves and then we have case when both player can perform next moves. We want to remove moves to the same node by both player and also remove duplicate moves that go to the same node with the same amount of time left.
And here we have our extended solve method. It now receives more params. We have start node for human and elephant, and time left for both human and elephant.
def solve(graph, closed, human_start, human_minutes, elephant_start, elephant_minutes, total = 0)
return total if closed.empty? || (human_minutes == 0 && elephant_minutes == 0)
human_moves = generate_possible_moves(graph, closed, human_start, human_minutes)
elephant_moves = generate_possible_moves(graph, closed, elephant_start, elephant_minutes)
combined_moves = combine_moves(human_moves, elephant_moves)
return total if combined_moves.size == 0
combined_moves.map.with_index do |(human_move, elephant_move), index|
if human_move.nil?
solve(graph, (closed - [elephant_move[0]]).clone, human_start, human_minutes, elephant_move[0], elephant_move[1], total + elephant_move[2])
elsif elephant_move.nil?
solve(graph, (closed - [human_move[0]]).clone, human_move[0], human_move[1], elephant_start, elephant_minutes, total + human_move[2])
else
solve(graph, (closed - [human_move[0]] - [elephant_move[0]]).clone, human_move[0], human_move[1], elephant_move[0], elephant_move[1], total + human_move[2] + elephant_move[2])
end
end.max
end
closed = @valves.map do |id, value|
value > 0 ? id : nil
end.compact
puts solve(d, closed, "AA", 26, "AA", 26)
If all valves are opened we can stop our recursion. We can also stop when both human and elephant reach 0 minutes left.
Then we generate all possible moves for human, for elephant and we combine them together. If there are no next moves we need to stop as well. If we have next moves we can explore all next states and select the maximum value.
The solution I wrote is not that fast. I can probably look for some improvements and ways to eliminate more unnecessary states. Or add some caching. But it took 10 minutes or so to run, I’ve got correct answer and I moved on.
Here is the full code:
data = File.readlines("16.txt", chomp: true)
@valves = {}
tunnels = {}
@nodes = []
data.each do |elem|
match = elem.match(/Valve (.+?) has flow rate=(\d+); tunnels? leads? to valves? (.+)/)
id = match[1]
rate = match[2].to_i
edges = match[3].split(",").map(&:strip)
@nodes.push(id)
@valves[id] = rate
tunnels[id] = edges
end
@nodes.sort!
def key_to_idx(key)
@nodes.index(key)
end
def idx_to_key(idx)
@nodes[idx]
end
graph = []
@nodes.size.times { graph.push(Array.new(@nodes.size, Float::INFINITY) ) }
tunnels.each do |key, edges|
edges.each do |edge|
graph[key_to_idx(key)][key_to_idx(edge)] = 1
end
end
graph.size.times do |i|
graph[i][i] = 0
end
def floyd(w)
n = w.size
d = w.clone
d_prime = d.clone
n.times do |k|
n.times do |i|
n.times do |j|
d_prime[i][j] = [d[i][j], d[i][k] + d[k][j]].min
end
end
end
d_prime
end
def path(d, key1, key2)
d[key_to_idx(key1)][key_to_idx(key2)]
end
d = floyd(graph)
def generate_possible_moves(graph, closed, start, minutes)
closed.map do |key|
left = minutes - path(graph, start, key) - 1
pressure = @valves[key] * left
[key, left, pressure]
end.reject { |(key, left, pressure)| left < 0 }
end
def combine_moves(human_moves, elephant_moves)
all_moves = []
visited_moves = {}
if human_moves.size == 0
elephant_moves.each do |move2|
all_moves.push([nil, move2])
end
end
if elephant_moves.size == 0
human_moves.each do |move1|
all_moves.push([move1, nil])
end
end
human_moves.each do |move1|
elephant_moves.each do |move2|
next if move1[0] == move2[0]
next if visited_moves[[move2[0], move2[1]]]
all_moves.push([move1, move2])
visited_moves[[move1[0], move1[1]]] = true
end
end
all_moves.sort_by! { |elem| (elem[0] ? elem[0][2] : 0) + (elem[1] ? elem[1][2] : 0) }.reverse
end
@iterations = 0
def solve(graph, closed, human_start, human_minutes, elephant_start, elephant_minutes, total = 0)
@iterations += 1
puts @iterations if @iterations % 1_000_000 == 0
return total if closed.empty? || (human_minutes == 0 && elephant_minutes == 0)
human_moves = generate_possible_moves(graph, closed, human_start, human_minutes)
elephant_moves = generate_possible_moves(graph, closed, elephant_start, elephant_minutes)
combined_moves = combine_moves(human_moves, elephant_moves)
return total if combined_moves.size == 0
combined_moves.map.with_index do |(human_move, elephant_move), index|
if human_move.nil?
solve(graph, (closed - [elephant_move[0]]).clone, human_start, human_minutes, elephant_move[0], elephant_move[1], total + elephant_move[2])
elsif elephant_move.nil?
solve(graph, (closed - [human_move[0]]).clone, human_move[0], human_move[1], elephant_start, elephant_minutes, total + human_move[2])
else
solve(graph, (closed - [human_move[0]] - [elephant_move[0]]).clone, human_move[0], human_move[1], elephant_move[0], elephant_move[1], total + human_move[2] + elephant_move[2])
end
end.max
end
closed = @valves.map do |id, value|
value > 0 ? id : nil
end.compact
puts solve(d, closed, "AA", 26, "AA", 26)