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

aoc/year2022/
day19.rs
