aoc/year2022/
day19.rs

1//! # Not Enough Minerals
2//!
3//! The solution is [branch and bound](https://en.wikipedia.org/wiki/Branch_and_bound) using
4//! a [depth first search](https://en.wikipedia.org/wiki/Depth-first_search) to enumerate every
5//! possible combination combined with heuristics to prune those combinations in order to achieve
6//! a reasonable running time.
7//!
8//! The most important heuristic is:
9//! * Assume ore is infinite.
10//! * Always build a clay robot.
11//! * Check if we can do better than the highest score so far in the remaining time, building
12//!   only geode or obsidian bots.
13//!
14//! As these simplified rules will always score higher than the real rules, we can immediately
15//! prune any branch that can't possibly exceed the current high score.
16//!
17//! The second helpful heuristic is:
18//! * Don't build more bots for a particular mineral than the maximum possible consumption in
19//!   a single turn.
20//!
21//! As we can only build one bot per turn, we will never need to generate more resources than
22//! that bot can use. For example, if ore robots need 2 ore, clay robots 3 ore, obsidian robots
23//! 4 ore and geode robots 5 ore, then the most possible ore robots that we need to build is 5.
24//! Any more would go to waste. The same applies for clay and obsidian.
25//!
26//! The third helpful heuristic is:
27//! * Don't build any robot during the last minute
28//! * Don't build ore or obsidian robots during the last 3 minutes.
29//! * Don't build clay robots during the last 5 minutes.
30//!
31//! Building any robot during the last minute means that it will be ready *after* the time runs
32//! out so it will contribute nothing. The other two rules are corollaries of this rule.
33//!
34//! For example say we build an obsidian robot with 3 minutes left. It will be ready and collect
35//! a resource with two minutes left, which can be spent on a geode robot with 1 minute left,
36//! which is too late.
37//!
38//! Since we only need clay for obsidian robots it doesn't make sense to build clay robots less
39//! than two minutes before the cutoff for obsidian robots.
40//!
41//! The final important optimization is that we don't increment minute by minute. Instead once
42//! we decide to build a robot of a particular type, we "fast forward" in time until there are
43//! enough resources to build that robot. This cuts down on a lot of duplicate intermediate states.
44use crate::util::iter::*;
45use crate::util::parse::*;
46use std::ops::{Add, Sub};
47
48/// Each robot generates 1 mineral of a particular type.
49const ZERO: Mineral = Mineral::from(0, 0, 0, 0);
50const ORE_BOT: Mineral = Mineral::from(1, 0, 0, 0);
51const CLAY_BOT: Mineral = Mineral::from(0, 1, 0, 0);
52const OBSIDIAN_BOT: Mineral = Mineral::from(0, 0, 1, 0);
53const GEODE_BOT: Mineral = Mineral::from(0, 0, 0, 1);
54
55#[derive(Clone, Copy)]
56struct Mineral {
57    ore: u32,
58    clay: u32,
59    obsidian: u32,
60    geode: u32,
61}
62
63impl Mineral {
64    const fn from(ore: u32, clay: u32, obsidian: u32, geode: u32) -> Self {
65        Mineral { ore, clay, obsidian, geode }
66    }
67
68    /// This is used to compare robot costs so we don't need to check geodes.
69    fn less_than_equal(self, rhs: Self) -> bool {
70        self.ore <= rhs.ore && self.clay <= rhs.clay && self.obsidian <= rhs.obsidian
71    }
72}
73
74/// Implement operators so that we can use `+` and `-` notation to add and subtract minerals.
75impl Add for Mineral {
76    type Output = Self;
77
78    fn add(self, rhs: Self) -> Self {
79        Mineral {
80            ore: self.ore + rhs.ore,
81            clay: self.clay + rhs.clay,
82            obsidian: self.obsidian + rhs.obsidian,
83            geode: self.geode + rhs.geode,
84        }
85    }
86}
87
88impl Sub for Mineral {
89    type Output = Self;
90
91    fn sub(self, rhs: Self) -> Self {
92        Mineral {
93            ore: self.ore - rhs.ore,
94            clay: self.clay - rhs.clay,
95            obsidian: self.obsidian - rhs.obsidian,
96            geode: self.geode - rhs.geode,
97        }
98    }
99}
100
101pub struct Blueprint {
102    id: u32,
103    max_ore: u32,
104    max_clay: u32,
105    max_obsidian: u32,
106    ore_cost: Mineral,
107    clay_cost: Mineral,
108    obsidian_cost: Mineral,
109    geode_cost: Mineral,
110}
111
112impl Blueprint {
113    fn from(chunk: [u32; 7]) -> Self {
114        let [id, ore1, ore2, ore3, clay, ore4, obsidian] = chunk;
115        Blueprint {
116            id,
117            max_ore: ore1.max(ore2).max(ore3).max(ore4),
118            max_clay: clay,
119            max_obsidian: obsidian,
120            ore_cost: Mineral::from(ore1, 0, 0, 0),
121            clay_cost: Mineral::from(ore2, 0, 0, 0),
122            obsidian_cost: Mineral::from(ore3, clay, 0, 0),
123            geode_cost: Mineral::from(ore4, 0, obsidian, 0),
124        }
125    }
126}
127
128pub fn parse(input: &str) -> Vec<Blueprint> {
129    input.iter_unsigned().chunk::<7>().map(Blueprint::from).collect()
130}
131
132pub fn part1(input: &[Blueprint]) -> u32 {
133    input.iter().map(|blueprint| blueprint.id * maximize(blueprint, 24)).sum()
134}
135
136pub fn part2(input: &[Blueprint]) -> u32 {
137    input.iter().take(3).map(|blueprint| maximize(blueprint, 32)).product()
138}
139
140fn maximize(blueprint: &Blueprint, time: u32) -> u32 {
141    let mut result = 0;
142    dfs(blueprint, &mut result, time, ORE_BOT, ZERO);
143    result
144}
145
146/// Depth first search over every possible combination pruning branches using heuristics.
147fn dfs(blueprint: &Blueprint, result: &mut u32, time: u32, bots: Mineral, resources: Mineral) {
148    // Extrapolate total geodes from the current state in the remaining time.
149    *result = (*result).max(resources.geode + bots.geode * time);
150
151    // Check if this state can improve on the existing high score.
152    if heuristic(blueprint, *result, time, bots, resources) {
153        if bots.obsidian > 0 && time > 1 {
154            next(blueprint, result, time, bots, resources, GEODE_BOT, blueprint.geode_cost);
155        }
156        if bots.obsidian < blueprint.max_obsidian && bots.clay > 0 && time > 3 {
157            next(blueprint, result, time, bots, resources, OBSIDIAN_BOT, blueprint.obsidian_cost);
158        }
159        if bots.ore < blueprint.max_ore && time > 3 {
160            next(blueprint, result, time, bots, resources, ORE_BOT, blueprint.ore_cost);
161        }
162        if bots.clay < blueprint.max_clay && time > 5 {
163            next(blueprint, result, time, bots, resources, CLAY_BOT, blueprint.clay_cost);
164        }
165    }
166}
167
168/// Simplify the blueprints so that we only attempt to build either geode or obsidian robots,
169/// then check that the estimated maximum possible score is greater than the current high score.
170/// Additionally we always build a clay robot each turn.
171///
172/// Since this will always score higher, we can immediately prune any branch that can't
173/// possibly beat the high score.
174#[inline]
175fn heuristic(
176    blueprint: &Blueprint,
177    result: u32,
178    time: u32,
179    mut bots: Mineral,
180    mut resources: Mineral,
181) -> bool {
182    for _ in 0..time {
183        // Assume ore is infinite.
184        resources.ore = blueprint.max_ore;
185
186        // Only attempt to build geode or obsidian robots.
187        if blueprint.geode_cost.less_than_equal(resources) {
188            resources = resources + bots - blueprint.geode_cost;
189            bots = bots + GEODE_BOT;
190        } else if blueprint.obsidian_cost.less_than_equal(resources) {
191            resources = resources + bots - blueprint.obsidian_cost;
192            bots = bots + OBSIDIAN_BOT;
193        } else {
194            resources = resources + bots;
195        }
196
197        // Always build a clay bot.
198        bots = bots + CLAY_BOT;
199    }
200
201    resources.geode > result
202}
203
204/// "Fast forward" in time until we can build a robot of a particular type. This could possibly
205/// be the next minute if we already have enough resources.
206#[inline]
207fn next(
208    blueprint: &Blueprint,
209    result: &mut u32,
210    time: u32,
211    bots: Mineral,
212    mut resources: Mineral,
213    new_bot: Mineral,
214    cost: Mineral,
215) {
216    for jump in 1..time {
217        if cost.less_than_equal(resources) {
218            dfs(blueprint, result, time - jump, bots + new_bot, resources + bots - cost);
219            break;
220        }
221        resources = resources + bots;
222    }
223}
aoc/year2022/day19.rs

aoc/year2022/
day19.rs
