1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
| use std::cmp::max;
use itertools::Itertools;
use rayon::prelude::*;
use regex::Regex;
use crate::Material::{Clay, Geode, Obsidian, Ore};
pub type RecipePart = (u32, Material);
#[derive(Copy, Clone, Debug)]
pub enum Material {
Ore = 0,
Clay = 1,
Obsidian = 2,
Geode = 3,
}
#[derive(Clone, Debug)]
pub struct Blueprint {
id: u32,
robot_recipes: [Vec<RecipePart>; 4],
}
#[derive(Copy, Clone)]
pub struct SearchState {
time_remaining: u32,
robots: [u32; 4],
materials: [u32; 4],
}
impl SearchState {
fn can_build_robot(&self, robot_type: usize, blueprint: &Blueprint, max_materials: &[u32]) -> bool {
let recipe = &blueprint.robot_recipes[robot_type];
let maxed_out = self.robots[robot_type] >= max_materials[robot_type];
!maxed_out && recipe.iter().all(|&(amount, material)| self.materials[material as usize] >= amount)
}
fn build_robot(&mut self, robot_type: usize, blueprint: &Blueprint) {
self.robots[robot_type] += 1;
for &(amount, material) in &blueprint.robot_recipes[robot_type] {
self.materials[material as usize] -= amount;
}
}
fn un_build_robot(&mut self, robot_type: usize, blueprint: &Blueprint) {
self.robots[robot_type] -= 1;
for &(amount, material) in &blueprint.robot_recipes[robot_type] {
self.materials[material as usize] += amount;
}
}
}
type Input = Vec<Blueprint>;
fn get_blueprint_score(blueprint: &Blueprint, time_remaining: u32) -> u32 {
let state = SearchState { time_remaining, robots: [1,0,0,0], materials: [0,0,0,0] };
let max_materials = get_max_materials(blueprint);
run_for_blueprint(&state, blueprint, &max_materials, None, 0)
}
fn run_for_blueprint(
state: &SearchState,
blueprint: &Blueprint,
max_materials: &[u32],
prev_skipped: Option<&Vec<usize>>,
best_so_far: u32
) -> u32 {
if state.time_remaining == 1 {
return state.materials[3] + state.robots[3];
}
if optimistic_best(state, Geode) < best_so_far {
return 0;
}
let min_obsidian = max_materials[2];
if optimistic_best(state, Obsidian) < min_obsidian {
return state.materials[3] + state.robots[3] * state.time_remaining;
}
let mut new_state = *state;
new_state.time_remaining -= 1;
(0..4).for_each(|i| new_state.materials[i] += new_state.robots[i]);
if state.can_build_robot(Geode as usize, blueprint, max_materials) {
new_state.build_robot(Geode as usize, blueprint);
return run_for_blueprint(&new_state, blueprint, max_materials, None, best_so_far);
}
let robots_available = (0..3).filter(|i| state.can_build_robot(*i, blueprint, max_materials)).collect_vec();
let mut best = best_so_far;
for &robot_type in &robots_available {
if prev_skipped.map(|ls| ls.contains(&robot_type)).unwrap_or(false) {
continue;
}
new_state.build_robot(robot_type, blueprint);
let score = run_for_blueprint(&new_state, blueprint, max_materials, None, best);
best = max(score, best);
new_state.un_build_robot(robot_type, blueprint);
}
let score = run_for_blueprint(&new_state, blueprint, max_materials, Some(&robots_available), best);
best = max(score, best);
best
}
fn optimistic_best(state: &SearchState, material: Material) -> u32 {
let mat = material as usize;
let i = state.time_remaining;
state.materials[mat] + state.robots[mat] * i + i * (i-1) / 2
}
fn get_max_materials(blueprint: &Blueprint) -> [u32; 4] {
let mut maxes = [0, 0, 0, u32::MAX];
for recipe in &blueprint.robot_recipes {
for &(amount, material) in recipe {
let i = material as usize;
maxes[i] = max(maxes[i], amount);
}
};
maxes
}
fn parse(input: &str) -> Input {
input.lines().filter_map(|line| {
let regex = Regex::new(r"Blueprint (\d+): Each ore robot costs (\d+) ore. Each clay robot costs (\d+) ore. Each obsidian robot costs (\d+) ore and (\d+) clay. Each geode robot costs (\d+) ore and (\d+) obsidian.").unwrap();
let c = regex.captures(line)?;
let mut captures = c.iter().skip(1);
let id = captures.next()??.as_str().parse().unwrap();
let ore_robot_ore_cost = captures.next()??.as_str().parse().unwrap();
let clay_robot_ore_cost = captures.next()??.as_str().parse().unwrap();
let obsidian_robot_ore_cost = captures.next()??.as_str().parse().unwrap();
let obsidian_robot_clay_cost = captures.next()??.as_str().parse().unwrap();
let geode_robot_ore_cost = captures.next()??.as_str().parse().unwrap();
let geode_robot_obsidian_cost = captures.next()??.as_str().parse().unwrap();
let ore_robot: Vec<(u32, Material)> = vec![(ore_robot_ore_cost, Ore)];
let clay_robot: Vec<(u32, Material)> = vec![(clay_robot_ore_cost, Ore)];
let obsidian_robot: Vec<(u32, Material)> = vec![(obsidian_robot_ore_cost, Ore), (obsidian_robot_clay_cost, Clay)];
let geode_robot: Vec<(u32, Material)> = vec![(geode_robot_ore_cost, Ore), (geode_robot_obsidian_cost, Obsidian)];
Some(Blueprint {
id,
robot_recipes: [ore_robot, clay_robot, obsidian_robot, geode_robot],
})
}).collect_vec()
}
pub fn part_one(input: Input) -> Option<u32> {
Some(
input.par_iter()
.map(|bp| (bp.id * get_blueprint_score(bp, 24)))
.sum::<u32>()
)
}
pub fn part_two(input: Input) -> Option<u32> {
Some(
input.par_iter()
.take(3)
.map(|bp| get_blueprint_score(bp, 32))
.product::<u32>()
)
}
|