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 only
12//!   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 a
19//!   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 are 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 std::ops::{Add, Sub};
45
46use crate::util::iter::*;
47use crate::util::parse::*;
48
49/// Each robot generates 1 mineral of a particular type.
50const ZERO: Mineral = Mineral::from(0, 0, 0, 0);
51const ORE_BOT: Mineral = Mineral::from(1, 0, 0, 0);
52const CLAY_BOT: Mineral = Mineral::from(0, 1, 0, 0);
53const OBSIDIAN_BOT: Mineral = Mineral::from(0, 0, 1, 0);
54const GEODE_BOT: Mineral = Mineral::from(0, 0, 0, 1);
55
56#[derive(Clone, Copy)]
57struct Mineral {
58    ore: u32,
59    clay: u32,
60    obsidian: u32,
61    geode: u32,
62}
63
64impl Mineral {
65    const fn from(ore: u32, clay: u32, obsidian: u32, geode: u32) -> Self {
66        Self { ore, clay, obsidian, geode }
67    }
68
69    /// This is used to compare robot costs so we don't need to check geodes.
70    fn less_than_equal(self, rhs: Self) -> bool {
71        self.ore <= rhs.ore && self.clay <= rhs.clay && self.obsidian <= rhs.obsidian
72    }
73}
74
75/// Implement operators so that we can use `+` and `-` notation to add and subtract minerals.
76impl Add for Mineral {
77    type Output = Self;
78
79    fn add(self, rhs: Self) -> Self {
80        Self {
81            ore: self.ore + rhs.ore,
82            clay: self.clay + rhs.clay,
83            obsidian: self.obsidian + rhs.obsidian,
84            geode: self.geode + rhs.geode,
85        }
86    }
87}
88
89impl Sub for Mineral {
90    type Output = Self;
91
92    fn sub(self, rhs: Self) -> Self {
93        Self {
94            ore: self.ore - rhs.ore,
95            clay: self.clay - rhs.clay,
96            obsidian: self.obsidian - rhs.obsidian,
97            geode: self.geode - rhs.geode,
98        }
99    }
100}
101
102pub struct Blueprint {
103    id: u32,
104    max_ore: u32,
105    max_clay: u32,
106    max_obsidian: u32,
107    ore_cost: Mineral,
108    clay_cost: Mineral,
109    obsidian_cost: Mineral,
110    geode_cost: Mineral,
111}
112
113impl Blueprint {
114    fn from(chunk: [u32; 7]) -> Self {
115        let [id, ore1, ore2, ore3, clay, ore4, obsidian] = chunk;
116        Self {
117            id,
118            max_ore: ore1.max(ore2).max(ore3).max(ore4),
119            max_clay: clay,
120            max_obsidian: obsidian,
121            ore_cost: Mineral::from(ore1, 0, 0, 0),
122            clay_cost: Mineral::from(ore2, 0, 0, 0),
123            obsidian_cost: Mineral::from(ore3, clay, 0, 0),
124            geode_cost: Mineral::from(ore4, 0, obsidian, 0),
125        }
126    }
127}
128
129pub fn parse(input: &str) -> Vec<Blueprint> {
130    input.iter_unsigned().chunk::<7>().map(Blueprint::from).collect()
131}
132
133pub fn part1(input: &[Blueprint]) -> u32 {
134    input.iter().map(|blueprint| blueprint.id * maximize(blueprint, 24)).sum()
135}
136
137pub fn part2(input: &[Blueprint]) -> u32 {
138    input.iter().take(3).map(|blueprint| maximize(blueprint, 32)).product()
139}
140
141fn maximize(blueprint: &Blueprint, time: u32) -> u32 {
142    let mut result = 0;
143    dfs(blueprint, &mut result, time, ORE_BOT, ZERO);
144    result
145}
146
147/// Depth-first search over every possible combination pruning branches using heuristics.
148fn dfs(blueprint: &Blueprint, result: &mut u32, time: u32, bots: Mineral, resources: Mineral) {
149    // Extrapolate total geodes from the current state in the remaining time.
150    *result = (*result).max(resources.geode + bots.geode * time);
151
152    // Check if this state can improve on the existing high score.
153    if heuristic(blueprint, *result, time, bots, resources) {
154        if bots.obsidian > 0 && time > 1 {
155            next(blueprint, result, time, bots, resources, GEODE_BOT, blueprint.geode_cost);
156        }
157        if bots.obsidian < blueprint.max_obsidian && bots.clay > 0 && time > 3 {
158            next(blueprint, result, time, bots, resources, OBSIDIAN_BOT, blueprint.obsidian_cost);
159        }
160        if bots.ore < blueprint.max_ore && time > 3 {
161            next(blueprint, result, time, bots, resources, ORE_BOT, blueprint.ore_cost);
162        }
163        if bots.clay < blueprint.max_clay && time > 5 {
164            next(blueprint, result, time, bots, resources, CLAY_BOT, blueprint.clay_cost);
165        }
166    }
167}
168
169/// Simplify the blueprints so that we only attempt to build either geode or obsidian robots,
170/// then check that the estimated maximum possible score is greater than the current high score.
171/// Additionally, we always build a clay robot each turn.
172///
173/// Since this will always score higher, we can immediately prune any branch that can't
174/// possibly beat the high score.
175#[inline]
176fn heuristic(
177    blueprint: &Blueprint,
178    result: u32,
179    time: u32,
180    mut bots: Mineral,
181    mut resources: Mineral,
182) -> bool {
183    for _ in 0..time {
184        // Assume ore is infinite.
185        resources.ore = blueprint.max_ore;
186
187        // Only attempt to build geode or obsidian robots.
188        if blueprint.geode_cost.less_than_equal(resources) {
189            resources = resources + bots - blueprint.geode_cost;
190            bots = bots + GEODE_BOT;
191        } else if blueprint.obsidian_cost.less_than_equal(resources) {
192            resources = resources + bots - blueprint.obsidian_cost;
193            bots = bots + OBSIDIAN_BOT;
194        } else {
195            resources = resources + bots;
196        }
197
198        // Always build a clay bot.
199        bots = bots + CLAY_BOT;
200    }
201
202    resources.geode > result
203}
204
205/// "Fast forward" in time until we can build a robot of a particular type. This could possibly
206/// be the next minute if we already have enough resources.
207#[inline]
208fn next(
209    blueprint: &Blueprint,
210    result: &mut u32,
211    time: u32,
212    bots: Mineral,
213    mut resources: Mineral,
214    new_bot: Mineral,
215    cost: Mineral,
216) {
217    for jump in 1..time {
218        if cost.less_than_equal(resources) {
219            dfs(blueprint, result, time - jump, bots + new_bot, resources + bots - cost);
220            break;
221        }
222        resources = resources + bots;
223    }
224}
aoc/year2022/day19.rs

aoc/year2022/
day19.rs
