Puzzle on Day 19 calls again for max value that can be achieved within the given time limit, so you can assume we have a task similar to Day 16. Btw, solution for Day 16 is here.
This time we are dealing with different mining robots that can collect ore, clay, obsidian and geode. We start with just one ore-collecting robots and no resources. Our task is get as much geode as possible. You can spent collected resources to build new robots. It takes one minute to collect 1 unit of any resource and one minute to build new robot.
Important note! You can build just one robot per round. Initially I missed this restriction and I was considering a lot more cases than necessary.
Having this initial information we can think about our task in similar way as on Day 16. We can describe a state of the game with couple of variables: available resources, available robots and time left.
We start with no resources, one ore-collecting robot and 24 minutes. Now for such state we need to find what is the max number of geode units we can collect. We can solve it recursively. We call our solve method for this initial state, we explore all possible moves and return the max from all states. What are possible next moves:
For each state we have 5 other next states we can explore, so it can be around 5^24 = 59604644775390625 possible states to explore. To make thing worse we need to repeat this 30 times. Our input contains the list of blueprints, which are basically the costs for each robot. We need to examine each blueprint and output the max value possible. Similarly to Day 16 we need to eliminate most of the states that won’t get us anywhere close to the solution.
Let’s start with reading and parsing the input, which looks like this:
Blueprint 1: Each ore robot costs 4 ore. Each clay robot costs 2 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 2 ore and 7 obsidian.
Blueprint 2: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 8 clay. Each geode robot costs 3 ore and 12 obsidian.
Here is the code to load it:
def load_input(filename)
data = File.readlines(filename, chomp: true)
data.map do |line|
blueprint, robots = line.split(": ")
id = blueprint.match(/Blueprint (\d+)/)[1].to_i
robots = robots.split(".").map(&:strip)
robots.map do |robot|
type = robot.match(/Each (.+?) robot/)[1]
costs = robot.scan(/(\d+) (ore|clay|obsidian)/)
[type.to_sym, costs.map { |(count, resource)| [resource.to_sym, count.to_i] }.to_h]
end.to_h
end
end
For the example input it will return the following object:
[
{
ore: { ore: 2 },
clay: { ore: 2 },
obsidian: { ore: 3, clay: 14 },
geode: { ore: 2, obsidian: 7 }
},
{
ore: { ore: 4 },
clay: { ore: 3 },
obsidian: { ore: 3, clay: 8 },
geode: { ore: 3, obsidian: 12 }
}
]
We will store available resources and available robots in hashes as well. We will need to modify them like adding two hashes together when adding collected resources or subtracting two hashes when spending resources on robots. We can use some helper methods for that:
def subtract(h1, h2)
result = h1.clone
h2.each do |key, value|
result[key] ||= 0
result[key] -= value
end
result
end
def add(h1, h2)
result = h1.clone
h2.each do |key, value|
result[key] ||= 0
result[key] += value
end
result
end
def multiply(h, times)
h.clone.map do |key, value|
[key, value * times]
end.to_h
end
Let’s now tackle the solution. In the beginning I wrote very inefficient solution to Part A. I ran it overnight and got correct answer. But then Part B had even more possible cases to explore 5^32 vs 5^24 so I had to optimize it either way. Because I already had the correct answer I was able to experiment with different optimizations and make sure the solution is still correct.
Here is the rest of the code calculating the solution:
def next_states(blueprint, minutes, resources, robots)
states = []
if minutes == 1
# just wait
elsif minutes == 2
if time_to_build(blueprint[:geode], resources, robots) == 1
states.push(next_state(minutes - 1, resources, robots, { geode: 1 }, blueprint[:geode]))
else
# just wait
end
else
if time_to_build(blueprint[:geode], resources, robots) == 1
states.push(next_state(minutes - 1, resources, robots, { geode: 1 }, blueprint[:geode]))
else
[:ore, :clay, :obsidian, :geode].each do |key|
time = time_to_build(blueprint[key], resources, robots)
if time > 0 && time <= minutes - 1 && robots.fetch(key, 0) < max_resource(blueprint, key)
states.push(next_state(minutes - time, resources, robots, { key => 1 }, blueprint[key], time))
end
end
end
end
if states.empty?
states.push(next_state(minutes - 1, resources, robots, {}, {}))
end
states
end
def next_state(minutes, resources, robots, list, costs, times = 1)
[
minutes,
add(subtract(resources, costs), multiply(robots, times)),
add(robots, list)
]
end
def max_resource(blueprint, target)
return Float::INFINITY if target == :geode
blueprint.map do |key, costs|
costs[target] || 0
end.max
end
def max_possible_geodes(blueprint, minutes, resources, robots)
geode_robots = robots.fetch(:geode, 0)
geode = resources.fetch(:geode, 0)
geode + (geode_robots + minutes * geode_robots) * minutes / 2
end
def time_to_build(costs, resources, robots)
costs = subtract(costs, resources)
max = costs.map do |key, value|
if value > 0 && robots.fetch(key, 0) > 0
(value / robots.fetch(key, 0).to_f).ceil
elsif robots.fetch(key, 0) == 0
Float::INFINITY
else
0
end
end.max
return max + 1
end
def solve(blueprint, minutes, resources, robots)
return resources.fetch(:geode, 0) if minutes == 0
return @cache[[minutes, resources, robots]] if @cache[[minutes, resources, robots]]
return 0 if robots.fetch(:geode, 0) > 0 && max_possible_geodes(blueprint, minutes, resources, robots) < @max
if robots.fetch(:geode, 0) == 1 && minutes > @first_geode_robot_at_minutes_left
@first_geode_robot_at_minutes_left = minutes
end
@max = resources.fetch(:geode, 0) if resources.fetch(:geode, 0) > @max
states = next_states(blueprint, minutes, resources, robots).sort_by! { |state| 24 - state[0] }
states.reject! do |(minutes, resources, robots)|
@first_geode_robot_at_minutes_left && minutes < @first_geode_robot_at_minutes_left && robots.fetch(:geode, 0) == 0
end
return resources.fetch(:geode, 0) if states.empty?
max = states.map do |state|
@cache[state] || solve(blueprint, *state)
end.max
@cache[[minutes, resources, robots]] = max
max
end
blueprints = load_input("19.txt")
sum = blueprints.map.with_index do |blueprint, index|
@cache = {}
@iterations = 0
@max = 0
@first_geode_robot_at_minutes_left = 0
max = solve(blueprint, 24, { }, { ore: 1 })
max * (index + 1)
end.sum
puts "Final solution = #{sum}"
Let’s concentrate on next_states method. Our first optimization is that if we have just 1 minute left there is no point at building new robot, because we will have no more time when it is ready.
Second case is if we have 2 minutes left and can build geode robot then that’s the only move. If we build another robot we won’t have more geode collected anyway.
In other cases, if we can build geode robot we should just do this move and do not consider building other robots. If we cannot build geode right now, we explore next states where we build different robot in each.
Another optimization is that it is not worth to explore states where we cannot build a robot. For example, if we are at 23 minutes left and need to wait 2 minutes to get another robot, there is no point to explore state with 22 minutes left. We should just jump into the states where we can actually build new robot.
Since we can only build one robot in the given minute there is no point in getting more robots of particular resource than the max we can spent in the round. Consider blueprint 1 from the example, ore-collecting robot costs 4 ore units, other robots cost 2 or 3 ore units. So the most ore you can spend is 4 units. There is no point in getting more ore-collecting robots. We have max_resource method to calculate max we can spend for given resources. This can limit number of states to explore.
Obviously we should not explore states that have no minutes left. We have time_to_build method to give us information how many minutes we need to wait for a given robot to be ready. It is a time to collect necessary resources plus one minute to build it.
There are more ways to optimize inside our solve method.
First, we can cache the results of solve method using our state as cache key (minutes left, available resources, available robots).
We can use max_possible_geodes method to calculate the max theoretical number of geode we can collect if we will have resources to build one geode robot at each minute. It is basically an arithmetic series. We get our first geode-collecting robot and we collect one geode. We build another robot and collect 2 units next minute. Then we collect 3 units, 4 units and so on. This is true when you have resources to build geode robot each minute. But if you considering a state and there is only 3 minutes left. In such case you can collect max 6 geode units. If you already found another solution that has 7 geode, there is no point in exploring this one.
And the last thing in the code is variable @first_geode_robot_at_minutes_left. It is similar to the previous one. We store the lowest minute when we can get geode robot. If we considering another state where we don’t have geode robot yet and it has higher minute then again there is no point in exploring this state, because we will get less geode units. I am not sure if keeping those both optimizations actually makes sense, because they may duplicate each other.
Anyway with all this stuff it took just 2-3 seconds to find a solution.
Here is the full code:
def load_input(filename)
data = File.readlines(filename, chomp: true)
data.map do |line|
blueprint, robots = line.split(": ")
id = blueprint.match(/Blueprint (\d+)/)[1].to_i
robots = robots.split(".").map(&:strip)
robots.map do |robot|
type = robot.match(/Each (.+?) robot/)[1]
costs = robot.scan(/(\d+) (ore|clay|obsidian)/)
[type.to_sym, costs.map { |(count, resource)| [resource.to_sym, count.to_i] }.to_h]
end.to_h
end
end
def subtract(h1, h2)
result = h1.clone
h2.each do |key, value|
result[key] ||= 0
result[key] -= value
end
result
end
def add(h1, h2)
result = h1.clone
h2.each do |key, value|
result[key] ||= 0
result[key] += value
end
result
end
def multiply(h, times)
h.clone.map do |key, value|
[key, value * times]
end.to_h
end
def next_states(blueprint, minutes, resources, robots)
states = []
if minutes == 1
# just wait
elsif minutes == 2
if time_to_build(blueprint[:geode], resources, robots) == 1
states.push(next_state(minutes - 1, resources, robots, { geode: 1 }, blueprint[:geode]))
else
# just wait
end
else
if time_to_build(blueprint[:geode], resources, robots) == 1
states.push(next_state(minutes - 1, resources, robots, { geode: 1 }, blueprint[:geode]))
else
[:ore, :clay, :obsidian, :geode].each do |key|
time = time_to_build(blueprint[key], resources, robots)
if time > 0 && time <= minutes - 1 && robots.fetch(key, 0) < max_resource(blueprint, key)
states.push(next_state(minutes - time, resources, robots, { key => 1 }, blueprint[key], time))
end
end
end
end
if states.empty?
states.push(next_state(minutes - 1, resources, robots, {}, {}))
end
states
end
def next_state(minutes, resources, robots, list, costs, times = 1)
[
minutes,
add(subtract(resources, costs), multiply(robots, times)),
add(robots, list)
]
end
def max_resource(blueprint, target)
return Float::INFINITY if target == :geode
blueprint.map do |key, costs|
costs[target] || 0
end.max
end
def max_possible_geodes(blueprint, minutes, resources, robots)
geode_robots = robots.fetch(:geode, 0)
geode = resources.fetch(:geode, 0)
geode + (geode_robots + minutes * geode_robots) * minutes / 2
end
def time_to_build(costs, resources, robots)
costs = subtract(costs, resources)
max = costs.map do |key, value|
if value > 0 && robots.fetch(key, 0) > 0
(value / robots.fetch(key, 0).to_f).ceil
elsif robots.fetch(key, 0) == 0
Float::INFINITY
else
0
end
end.max
return max + 1
end
def solve(blueprint, minutes, resources, robots)
return resources.fetch(:geode, 0) if minutes == 0
return @cache[[minutes, resources, robots]] if @cache[[minutes, resources, robots]]
return 0 if robots.fetch(:geode, 0) > 0 && max_possible_geodes(blueprint, minutes, resources, robots) < @max
if robots.fetch(:geode, 0) == 1 && minutes > @first_geode_robot_at_minutes_left
@first_geode_robot_at_minutes_left = minutes
end
@max = resources.fetch(:geode, 0) if resources.fetch(:geode, 0) > @max
states = next_states(blueprint, minutes, resources, robots).sort_by! { |state| 24 - state[0] }
states.reject! do |(minutes, resources, robots)|
@first_geode_robot_at_minutes_left && minutes < @first_geode_robot_at_minutes_left && robots.fetch(:geode, 0) == 0
end
return resources.fetch(:geode, 0) if states.empty?
max = states.map do |state|
@cache[state] || solve(blueprint, *state)
end.max
@cache[[minutes, resources, robots]] = max
max
end
blueprints = load_input("19.txt")
sum = blueprints.map.with_index do |blueprint, index|
@cache = {}
@iterations = 0
@max = 0
@first_geode_robot_at_minutes_left = 0
max = solve(blueprint, 24, { }, { ore: 1 })
max * (index + 1)
end.sum
puts "Final solution = #{sum}"
In second part we need to calculate max geode for just the first three blueprints, but now time available is 32 minutes. Fortunately all the optimizations from part one are enough to solve this quickly. It took less than 10 seconds to get the solution.
Below you can find full code that has some adjustments to produce the answer required for the puzzle.
def load_input(filename)
data = File.readlines(filename, chomp: true)
data.map do |line|
blueprint, robots = line.split(": ")
id = blueprint.match(/Blueprint (\d+)/)[1].to_i
robots = robots.split(".").map(&:strip)
robots.map do |robot|
type = robot.match(/Each (.+?) robot/)[1]
costs = robot.scan(/(\d+) (ore|clay|obsidian)/)
[type.to_sym, costs.map { |(count, resource)| [resource.to_sym, count.to_i] }.to_h]
end.to_h
end
end
def subtract(h1, h2)
result = h1.clone
h2.each do |key, value|
result[key] ||= 0
result[key] -= value
end
result
end
def add(h1, h2)
result = h1.clone
h2.each do |key, value|
result[key] ||= 0
result[key] += value
end
result
end
def multiply(h, times)
h.clone.map do |key, value|
[key, value * times]
end.to_h
end
def next_states(blueprint, minutes, resources, robots)
states = []
if minutes == 1
# just wait
elsif minutes == 2
if time_to_build(blueprint[:geode], resources, robots) == 1
states.push(next_state(minutes - 1, resources, robots, { geode: 1 }, blueprint[:geode]))
end
else
if time_to_build(blueprint[:geode], resources, robots) == 1
states.push(next_state(minutes - 1, resources, robots, { geode: 1 }, blueprint[:geode]))
else
[:ore, :clay, :obsidian, :geode].each do |key|
time = time_to_build(blueprint[key], resources, robots)
if time > 0 && time <= minutes - 1 && robots.fetch(key, 0) < max_resource(blueprint, key)
states.push(next_state(minutes - time, resources, robots, { key => 1 }, blueprint[key], time))
end
end
end
end
if states.empty?
states.push(next_state(minutes - 1, resources, robots, {}, {}))
end
states
end
def next_state(minutes, resources, robots, list, costs, times = 1)
res = [
minutes,
add(subtract(resources, costs), multiply(robots, times)),
add(robots, list)
]
res
end
def max_resource(blueprint, target)
return Float::INFINITY if target == :geode
blueprint.map do |key, costs|
costs[target] || 0
end.max
end
def max_possible_geodes(blueprint, minutes, resources, robots)
geode_robots = robots.fetch(:geode, 0)
geode = resources.fetch(:geode, 0)
geode + (geode_robots + minutes * geode_robots) * minutes / 2
end
def time_to_build(costs, resources, robots)
costs = subtract(costs, resources)
max = costs.map do |key, value|
if value > 0 && robots.fetch(key, 0) > 0
(value / robots.fetch(key, 0).to_f).ceil
elsif robots.fetch(key, 0) == 0
Float::INFINITY
else
0
end
end.max
return max + 1
end
def solve(blueprint, minutes, resources, robots)
return resources.fetch(:geode, 0) if minutes == 0
return @cache[[minutes, resources, robots]] if @cache[[minutes, resources, robots]]
return 0 if robots.fetch(:geode, 0) > 0 && max_possible_geodes(blueprint, minutes, resources, robots) < @max
if robots.fetch(:geode, 0) == 1 && minutes > @first_geode_robot_at_minutes_left
@first_geode_robot_at_minutes_left = minutes
end
@max = resources.fetch(:geode, 0) if resources.fetch(:geode, 0) > @max
states = next_states(blueprint, minutes, resources, robots).sort_by! { |state| 24 - state[0] }
states.reject! do |(minutes, resources, robots)|
@first_geode_robot_at_minutes_left && minutes < @first_geode_robot_at_minutes_left && robots.fetch(:geode, 0) == 0
end
return resources.fetch(:geode, 0) if states.empty?
max = states.map do |state|
@cache[state] || solve(blueprint, *state)
end.max
@cache[[minutes, resources, robots]] = max
max
end
blueprints = load_input("19.txt")[0...3]
result = blueprints.map.with_index do |blueprint, index|
@cache = {}
@iterations = 0
@max = 0
@first_geode_robot_at_minutes_left = 0
max = solve(blueprint, 32, { }, { ore: 1 })
print "."
max
end.reduce(:*)
puts "Final solution = #{result}"