NickyMeulemanNime
Metadata
  • Date

  • By

    • Nicky Meuleman
  • Tagged

  • Part of series

  • Older post

    Advent of Code 2022 Day 18

  • Newer post

    Advent of Code 2022 Day 20

Table of contents
  1. Day 19: Not Enough Minerals
  2. Parsing
  3. Part 1
    1. Helpers
    2. Final code
  4. Part 2
    1. Final code
  5. Final code

Advent of Code 2022 Day 19

Day 19: Not Enough Minerals

https://adventofcode.com/2022/day/19

You want to collect the geodes.

No manual labor here, let robots do that!

  • A geode-cracking robot collects geodes.

  • Those need obsidian to be made, collected by obsidian-collecting robots.

  • Those need clay to be made, collected by clay-collecting robots.

  • Those need ore to be made, collected by ore-collecting robots.

  • You have 1 ore-collecting robot in your backpack.

  • You have a portable robot factory in your backpack.

You can kickstart the robot-partycollection!

  • Each robot collects 1 of its resource type per minute.
  • The factory can create 1 robot per minute, consuming the resources it needs to make that type of bot.

The amount of resources the factory needs for each bot depends on the used blueprint.

Todays input is a list of blueprints, a list of costs for the factory.

An example input looks like this (but each blueprint is on a single line in the real input):

input.txt
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.

Parsing

I want to represent one blueprint as a list of lists.

Each item in the outer list is a cost for a robot type. (4 types) Each cost is a list of ore amounts. (4 types)

An example for the first blueprint in the example:

  • Each ore robot costs 4 ore so the cost list is: [4, 0, 0, 0]
  • Each clay robot costs 2 ore so the cost list is: [2, 0, 0, 0]
  • Each obsidian robot costs 3 ore and 14 clay so the cost list is: [3, 14, 0, 0]
  • Each geode robot costs 2 ore and 7 obsidian so the cost list is: [2, 0, 7, 0]

Puttin all those cost lists together: [[4, 0, 0, 0], [2, 0, 0, 0], [3, 14, 0, 0], [2, 0, 7, 0]]

Used in parsing function:

  • An ore bot costs only ore
  • A clay bot costs only ore
  • An obsidian bot costs ore and clay
  • A geode bot costs ore and obsidian
day_19.rs
// each cost is [ore_amount, clay_amount, obsidian_amount, geode_amount]
// [ore_bot_costs, clay_bot_costs, obsidian_bot_costs, geode_bot_costs]
fn parse() -> Vec<[[u16; 4]; 4]> {
let input = std::fs::read_to_string("src/day19.txt").unwrap();
let mut blueprints = Vec::new();
for line in input.lines() {
let mut iter = line.split_ascii_whitespace();
// ore bots cost ore
let ore_bot_costs = [iter.nth(6).unwrap().parse().unwrap(), 0, 0, 0];
// clay bots cost ore
let clay_bot_costs = [iter.nth(5).unwrap().parse().unwrap(), 0, 0, 0];
// obsidian bots cost ore and clay
let obsidian_bot_costs = [
iter.nth(5).unwrap().parse().unwrap(),
iter.nth(2).unwrap().parse().unwrap(),
0,
0,
];
// geode bots cost ore and obsidian
let geode_bot_costs = [
iter.nth(5).unwrap().parse().unwrap(),
0,
iter.nth(2).unwrap().parse().unwrap(),
0,
];
let blueprint = [
ore_bot_costs,
clay_bot_costs,
obsidian_bot_costs,
geode_bot_costs,
];
blueprints.push(blueprint);
}
blueprints
}

Part 1

The question asks for the sum of all blueprint quality levels.

A blueprint’s quality level can be calculated by multiplying the ID with the maximum amount of geodes you can open in 24 minutes using that blueprint.

In skeleton code:

pseudocode.rs
let blueprints = parse();
blueprints
.iter()
.map(|blueprint| max_geodes(blueprint))
.enumerate()
.map(|(idx, geodes)| (idx + 1) * geodes)
.sum()

That skeleton code is is alright. The complexity is in calculating the maximum amount of geodes a blueprint can produce.

Helpers

Today’s main event, a “search a bunch of states and take the maximum of something” algorithm!

It uses a queue filled with states so far.
We start by inserting a state with an empty inventory, 1 ore bot, and 0 elapsed time.

For each state that is popped off the queue:

  • we try to build every type of bot.
  • we gather resources
  • we add the possibly made bot to the bot-pool
  • we subtract the cost of the possibly made bot from the inventory

We keep adding new states to that queue and recording the maximum amount of geodes while we loop. If a state would exceed the time limit, we continue with the next item in the loop instead.

Eventually, the queue empties and the number in max_geodes at that time is the maximum possible amount of geodes for that blueprint.

use std::collections::VecDeque;
struct State {
// [ore, clay, obsidian, geode]
inventory: [u16; 4],
// [ore_bots, clay_bots, obsidian_bots, geode_bots]
bots: [u16; 4],
// elapsed time in minutes
elapsed: u16,
}
fn max_geodes(blueprint: &[[u16; 4]; 4]) -> u16 {
let max_time = 24;
let mut max_geodes = 0;
let mut q = VecDeque::new();
q.push_back(State {
inventory: [0, 0, 0, 0],
bots: [1, 0, 0, 0],
elapsed: 0,
});
while let Some(State {
inventory,
bots,
elapsed,
}) = q.pop_front()
{
// for every bot cost, run simulation
for i in 0..blueprint.len() {
let costs = &blueprint[i];
// Find the limiting resource type for the costs.
let wait_time = (0..3)
.map(|idx| {
match costs[idx] {
// state has enough of current resource in inventory to cover that part of the target bot cost. 0 wait time
cost if cost <= inventory[idx] => 0,
// no target bot type made yet
// we can't build it (it takes more than max_time to build it).
_ if bots[idx] == 0 => max_time + 1,
_ => (costs[idx] - inventory[idx] + bots[idx] - 1) / bots[idx],
}
})
.max()
.unwrap();
// if that choice would cause the time limit be to exceeded, skip
// the + 1 is so the built bot has the chance to do something, it merely being built is not enough
let new_elapsed = elapsed + wait_time + 1;
if new_elapsed >= max_time {
continue;
}
// gather ores with previously available bots
let mut new_inventory = [0; 4];
for idx in 0..bots.len() {
new_inventory[idx] = inventory[idx] + bots[idx] * (wait_time + 1) - costs[idx];
}
// increase bot type for the bot we just built
let mut new_bots = bots;
new_bots[i] += 1;
q.push_back(State {
inventory: new_inventory,
bots: new_bots,
elapsed: new_elapsed,
})
}
let geodes = inventory[3] + bots[3] * (max_time - elapsed);
max_geodes = geodes.max(max_geodes);
}
max_geodes
}

Final code

day_19.rs
pub fn part_1() -> usize {
let blueprints = parse();
blueprints
.iter()
.map(|blueprint| max_geodes(blueprint))
.enumerate()
.map(|(idx, geodes)| (idx + 1) * usize::from(geodes))
.sum()
}

Part 2

An elephant ate most of the blueprints, only the first 3 are left.

The question asks for the product of all remaining blueprint’s maximum number of gathered geodes, in 32 minutes.

pseudocode.rs
let blueprints = parse();
blueprints
.iter()
.take(3)
.map(|blueprint| max_geodes(blueprint))
.product()

Combined with changing the let max_time = 24; to let max_time = 32; aaaaaaaaaaand

That is not enough (unless you have a beefy computer, and lots of patience).

The key is not making bots you don’t need.

Bots you don’t need are bots that don’t help towards unbottlenecking production. If you need 5 ore to build a bot, it doesn’t matter if we have 5 in our inventory, or 5000, the bot gets built just as fast.

So, if we have the amount of bots that’s equal to the maximum cost of that type for any bot, we’re gathering enough of that resource every turn to never be bottlenecked. Producing more of that type would not be beneficial, they’d just do unnecessary work.

The changes:

fn max_geodes(blueprint: &[[u16; 4]; 4]) -> u16 {
// calculate the maximum amount for every type of bot so that the creation of a new bot of any type is never bottlenecked
// it doesn't make sense to build more bots than that maximum if the resources a bot type generates are
// enough to cover that type (ore, clay, obsidian) cost for any possible bot (per question, you can only build 1 bot per turn)
// for geode bots, there is no logical maximum amount
// [ore, clay, obsidian, geode]
let mut max_robots = [u16::MAX; 4];
for i in 0..3 {
max_robots[i] = blueprint.iter().map(|cost| cost[i]).max().unwrap();
}
let max_time = 32;
let mut max_geodes = 0;
let mut q = VecDeque::new();
q.push_back(State {
inventory: [0, 0, 0, 0],
bots: [1, 0, 0, 0],
elapsed: 0,
});
while let Some(State {
inventory,
bots,
elapsed,
}) = q.pop_front()
{
// for every bot cost, run simulation
for i in 0..blueprint.len() {
// if we already have enough of this bot type, skip
if bots[i] == max_robots[i] {
continue;
}
let costs = &blueprint[i];
// Find the limiting resource type for the costs.
let wait_time = (0..3)
.map(|idx| {
match costs[idx] {
// state has enough of current resource in inventory to cover that part of the target bot cost. 0 wait time
cost if cost <= inventory[idx] => 0,
// no target bot type made yet
// we can't build it (it takes more than max_time to build it).
_ if bots[idx] == 0 => max_time + 1,
_ => (costs[idx] - inventory[idx] + bots[idx] - 1) / bots[idx],
}
})
.max()
.unwrap();
// if that choice would cause the time limit be to exceeded, skip
// the + 1 is so the built bot has the chance to do something, it merely being built is not enough
let new_elapsed = elapsed + wait_time + 1;
if new_elapsed >= max_time {
continue;
}
// gather ores with previously available bots
let mut new_inventory = [0; 4];
for idx in 0..bots.len() {
new_inventory[idx] = inventory[idx] + bots[idx] * (wait_time + 1) - costs[idx];
}
// increase bot type for the bot we just built
let mut new_bots = bots;
new_bots[i] += 1;
q.push_back(State {
inventory: new_inventory,
bots: new_bots,
elapsed: new_elapsed,
})
}
let geodes = inventory[3] + bots[3] * (max_time - elapsed);
max_geodes = geodes.max(max_geodes);
}
max_geodes
}

There’s a further optimization you can apply right before pushing to the queue. If we theoretically only built geode bots every turn, and we still wouldn’t beat the current maximum. Don’t push that state the the queue, but skip to the next item.

let remaining_time = max_time - new_elapsed;
if ((remaining_time - 1) * remaining_time) / 2
+ new_inventory[3]
+ remaining_time * new_bots[3]
< max_geodes
{
continue;
}

Final code

day_19.rs
pub fn part_2() -> usize {
let blueprints = parse();
blueprints
.iter()
.take(3)
.map(|blueprint| usize::from(max_geodes(blueprint)))
.product()
}

Final code

I turned the max_geode function into one that works for both part1 and part2 by passing in max_time as a parameter.

day_19.rs
1use std::collections::VecDeque;
2
3struct State {
4 // [ore, clay, obsidian, geode]
5 inventory: [u16; 4],
6 // [ore_bots, clay_bots, obsidian_bots, geode_bots]
7 bots: [u16; 4],
8 // elapsed time in minutes
9 elapsed: u16,
10}
11
12// each cost is [ore_amount, clay_amount, obsidian_amount, geode_amount]
13// [ore_bot_costs, clay_bot_costs, obsidian_bot_costs, geode_bot_costs]
14fn parse() -> Vec<[[u16; 4]; 4]> {
15 let input = std::fs::read_to_string("src/day19.txt").unwrap();
16 let mut blueprints = Vec::new();
17
18 for line in input.lines() {
19 let mut iter = line.split_ascii_whitespace();
20
21 // ore bots cost ore
22 let ore_bot_costs = [iter.nth(6).unwrap().parse().unwrap(), 0, 0, 0];
23 // clay bots cost ore
24 let clay_bot_costs = [iter.nth(5).unwrap().parse().unwrap(), 0, 0, 0];
25 // obsidian bots cost ore and clay
26 let obsidian_bot_costs = [
27 iter.nth(5).unwrap().parse().unwrap(),
28 iter.nth(2).unwrap().parse().unwrap(),
29 0,
30 0,
31 ];
32 // geode bots cost ore and obsidian
33 let geode_bot_costs = [
34 iter.nth(5).unwrap().parse().unwrap(),
35 0,
36 iter.nth(2).unwrap().parse().unwrap(),
37 0,
38 ];
39
40 let blueprint = [
41 ore_bot_costs,
42 clay_bot_costs,
43 obsidian_bot_costs,
44 geode_bot_costs,
45 ];
46 blueprints.push(blueprint);
47 }
48
49 blueprints
50}
51
52fn max_geodes(blueprint: &[[u16; 4]; 4], max_time: u16) -> u16 {
53 // calculate the maximum amount for every type of bot so that the creation of a new bot of any type is never bottlenecked
54 // it doesn't make sense to build more bots than that maximum if the resources a bot type generates are
55 // enough to cover that type (ore, clay, obsidian) cost for any possible bot (per question, you can only build 1 bot per turn)
56 // for geode bots, there is no logical maximum amount
57 // [ore, clay, obsidian, geode]
58 let mut max_robots = [u16::MAX; 4];
59 for i in 0..3 {
60 max_robots[i] = blueprint.iter().map(|cost| cost[i]).max().unwrap();
61 }
62 let mut max_geodes = 0;
63
64 let mut q = VecDeque::new();
65 q.push_back(State {
66 inventory: [0, 0, 0, 0],
67 bots: [1, 0, 0, 0],
68 elapsed: 0,
69 });
70
71 while let Some(State {
72 inventory,
73 bots,
74 elapsed,
75 }) = q.pop_front()
76 {
77 // for every bot cost, run simulation
78 for i in 0..blueprint.len() {
79 // if we already have enough of this bot type, skip
80 if bots[i] == max_robots[i] {
81 continue;
82 }
83
84 let costs = &blueprint[i];
85
86 // Find the limiting resource type for the costs.
87 let wait_time = (0..3)
88 .map(|idx| {
89 match costs[idx] {
90 // state has enough of current resource in inventory to cover that part of the target bot cost. 0 wait time
91 cost if cost <= inventory[idx] => 0,
92 // no target bot type made yet
93 // we can't build it (it takes more than max_time to build it).
94 _ if bots[idx] == 0 => max_time + 1,
95 _ => (costs[idx] - inventory[idx] + bots[idx] - 1) / bots[idx],
96 }
97 })
98 .max()
99 .unwrap();
100
101 // if that choice would cause the time limit be to exceeded, skip
102 // the + 1 is so the built bot has the chance to do something, it merely being built is not enough
103 let new_elapsed = elapsed + wait_time + 1;
104 if new_elapsed >= max_time {
105 continue;
106 }
107
108 // gather ores with previously available bots
109 let mut new_inventory = [0; 4];
110 for idx in 0..bots.len() {
111 new_inventory[idx] = inventory[idx] + bots[idx] * (wait_time + 1) - costs[idx];
112 }
113
114 // increase bot type for the bot we just built
115 let mut new_bots = bots.clone();
116 new_bots[i] += 1;
117
118 // extra optimization:
119 // if we theoretically only built geode bots every turn, and we still don't beat the maximum, skip
120 let remaining_time = max_time - new_elapsed;
121 if ((remaining_time - 1) * remaining_time) / 2
122 + new_inventory[3]
123 + remaining_time * new_bots[3]
124 < max_geodes
125 {
126 continue;
127 }
128
129 q.push_back(State {
130 inventory: new_inventory,
131 bots: new_bots,
132 elapsed: new_elapsed,
133 })
134 }
135
136 let geodes = inventory[3] + bots[3] * (max_time - elapsed);
137 max_geodes = geodes.max(max_geodes);
138 }
139
140 max_geodes
141}
142
143pub fn part_1() -> usize {
144 let blueprints = parse();
145
146 blueprints
147 .iter()
148 .map(|blueprint| max_geodes(blueprint, 24))
149 .enumerate()
150 .map(|(idx, geodes)| (idx + 1) * usize::from(geodes))
151 .sum()
152}
153
154pub fn part_2() -> usize {
155 let blueprints = parse();
156
157 blueprints
158 .iter()
159 .take(3)
160 .map(|blueprint| usize::from(max_geodes(blueprint, 32)))
161 .product()
162}

Series navigation for: Advent of Code 2022

1. Advent of Code 2022 Day 1

Designed and developed by Nicky Meuleman

Built with Gatsby. Hosted on Netlify.