commit ef5c772e61c4fbc8bbb78f75c93706abc4e59438
parent e236f7961d87c049f365f270043b3ddf993a9904
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri, 4 Jul 2025 22:50:41 +0200
Day 19 part 1 2022
Diffstat:
4 files changed, 219 insertions(+), 0 deletions(-)
diff --git a/2022/19/a.rs b/2022/19/a.rs
@@ -0,0 +1,18 @@
+use std::collections::HashMap;
+mod common;
+use common::*;
+
+fn main() {
+ const MINUTES: i32 = 24;
+ let mut mem = HashMap::<(Status, i32), i32>::new();
+ let mut i = 1;
+ let mut sum = 0;
+ for bp in read_blueprints_from_stdin() {
+ let mg = most_geodes(&bp, Status::new(), MINUTES, &mut mem);
+ println!("{i}: {mg}");
+ sum += i * mg;
+ mem.clear();
+ i += 1;
+ }
+ println!("{sum}");
+}
diff --git a/2022/19/common.rs b/2022/19/common.rs
@@ -0,0 +1,169 @@
+// This works for part 1, but it is too slow for part 2.
+// May be I am doing something wrong with caching?
+
+use std::cmp::{max, Ordering};
+use std::ops::{AddAssign, SubAssign};
+use std::collections::HashMap;
+
+#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
+pub struct Stock {
+ pub ore: i32,
+ pub cla: i32,
+ pub obs: i32,
+ pub geo: i32
+}
+
+impl Stock {
+ pub fn all_lower(&self, other: &Self) -> bool {
+ self.ore <= other.ore && self.cla <= other.cla &&
+ self.obs <= other.obs && self.geo <= other.geo
+ }
+}
+
+impl PartialOrd for Stock {
+ fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+ if self == other { return Some(Ordering::Equal); }
+ if self.all_lower(other) { return Some(Ordering::Less); }
+ if other.all_lower(self) { return Some(Ordering::Greater); }
+ None
+ }
+}
+
+impl AddAssign<&Stock> for Stock {
+ fn add_assign(&mut self, other: &Self) {
+ self.ore += other.ore;
+ self.cla += other.cla;
+ self.obs += other.obs;
+ self.geo += other.geo;
+ }
+}
+
+impl SubAssign<&Stock> for Stock {
+ fn sub_assign(&mut self, other: &Self) {
+ self.ore -= other.ore;
+ self.cla -= other.cla;
+ self.obs -= other.obs;
+ self.geo -= other.geo;
+ }
+}
+
+#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
+pub struct Status {
+ pub bots: Stock,
+ pub resources: Stock
+}
+
+impl Status {
+ pub fn new() -> Status {
+ Status {
+ bots: Stock { ore: 1, cla: 0, obs: 0, geo: 0 },
+ resources: Stock { ore: 0, cla: 0, obs: 0, geo: 0 }
+ }
+ }
+}
+
+#[derive(Debug, Clone, Hash)]
+pub struct Blueprint {
+ ore_bot_cost: Stock,
+ cla_bot_cost: Stock,
+ obs_bot_cost: Stock,
+ geo_bot_cost: Stock
+}
+
+impl Blueprint {
+ fn parse_one_resource(line: &str, i: &mut usize) -> i32 {
+ *i = line[*i..].find("costs ").unwrap() + 6 + *i;
+ let j = line[*i..].find(' ').unwrap() + *i;
+ line[*i..j].parse::<i32>().unwrap()
+ }
+
+ fn parse_two_resources(line: &str, i: &mut usize) -> (i32, i32) {
+ *i = line[*i..].find("costs ").unwrap() + 6 + *i;
+ let j = line[*i..].find(' ').unwrap() + *i;
+ let a = line[*i..j].parse::<i32>().unwrap();
+
+ *i = line[*i..].find("and ").unwrap() + 4 + *i;
+ let j = line[*i..].find(' ').unwrap() + *i;
+ let b = line[*i..j].parse::<i32>().unwrap();
+
+ (a, b)
+ }
+
+ pub fn from_line(line: &str) -> Blueprint {
+ let mut i = 0;
+
+ let ore = Blueprint::parse_one_resource(&line, &mut i);
+ let ore_bot_cost = Stock { ore, cla: 0, obs: 0, geo: 0 };
+
+ let ore = Blueprint::parse_one_resource(&line, &mut i);
+ let cla_bot_cost = Stock { ore, cla: 0, obs: 0, geo: 0 };
+
+ let (ore, cla) = Blueprint::parse_two_resources(&line, &mut i);
+ let obs_bot_cost = Stock { ore, cla, obs: 0, geo: 0 };
+
+ let (ore, obs) = Blueprint::parse_two_resources(&line, &mut i);
+ let geo_bot_cost = Stock { ore, cla: 0, obs, geo: 0 };
+
+ Blueprint { ore_bot_cost, cla_bot_cost, obs_bot_cost, geo_bot_cost }
+ }
+}
+
+pub fn read_blueprints_from_stdin() -> Vec<Blueprint> {
+ let mut v = vec![];
+ let mut line = String::new();
+ while std::io::stdin().read_line(&mut line).unwrap() > 0 {
+ v.push(Blueprint::from_line(&line));
+ line.clear();
+ }
+ v
+}
+
+pub fn most_geodes(
+ bp: &Blueprint,
+ s: Status,
+ m: i32,
+ mem: &mut HashMap<(Status, i32), i32>
+) -> i32 {
+ if let Some(r) = mem.get(&(s, m)) { return *r; }
+ if m == 0 { return s.resources.geo; }
+
+ let mut new_status = s;
+ new_status.resources += &new_status.bots;
+
+ let mut result = most_geodes(bp, new_status, m-1, mem);
+
+ if m > 4 && s.resources >= bp.ore_bot_cost {
+ new_status.resources -= &bp.ore_bot_cost;
+ new_status.bots.ore += 1;
+ result = max(result, most_geodes(bp, new_status, m-1, mem));
+ new_status.bots.ore -= 1;
+ new_status.resources += &bp.ore_bot_cost;
+ }
+
+ if m > 3 && s.resources >= bp.cla_bot_cost {
+ new_status.resources -= &bp.cla_bot_cost;
+ new_status.bots.cla += 1;
+ result = max(result, most_geodes(bp, new_status, m-1, mem));
+ new_status.bots.cla -= 1;
+ new_status.resources += &bp.cla_bot_cost;
+ }
+
+ if m > 2 && s.resources >= bp.obs_bot_cost {
+ new_status.resources -= &bp.obs_bot_cost;
+ new_status.bots.obs += 1;
+ result = max(result, most_geodes(bp, new_status, m-1, mem));
+ new_status.bots.obs -= 1;
+ new_status.resources += &bp.obs_bot_cost;
+ }
+
+ if m > 1 && s.resources >= bp.geo_bot_cost {
+ new_status.resources -= &bp.geo_bot_cost;
+ new_status.bots.geo += 1;
+ result = max(result, most_geodes(bp, new_status, m-1, mem));
+ new_status.bots.geo -= 1;
+ new_status.resources += &bp.geo_bot_cost;
+ }
+
+ mem.insert((s, m), result);
+ result
+}
diff --git a/2022/19/input b/2022/19/input
@@ -0,0 +1,30 @@
+Blueprint 1: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 12 clay. Each geode robot costs 4 ore and 19 obsidian.
+Blueprint 2: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 11 clay. Each geode robot costs 4 ore and 12 obsidian.
+Blueprint 3: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 18 clay. Each geode robot costs 2 ore and 11 obsidian.
+Blueprint 4: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 15 clay. Each geode robot costs 4 ore and 20 obsidian.
+Blueprint 5: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 16 clay. Each geode robot costs 4 ore and 17 obsidian.
+Blueprint 6: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 19 clay. Each geode robot costs 2 ore and 12 obsidian.
+Blueprint 7: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 9 clay. Each geode robot costs 2 ore and 10 obsidian.
+Blueprint 8: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 5 clay. Each geode robot costs 3 ore and 7 obsidian.
+Blueprint 9: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 11 clay. Each geode robot costs 4 ore and 8 obsidian.
+Blueprint 10: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 16 clay. Each geode robot costs 2 ore and 15 obsidian.
+Blueprint 11: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 20 clay. Each geode robot costs 2 ore and 19 obsidian.
+Blueprint 12: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 16 clay. Each geode robot costs 3 ore and 20 obsidian.
+Blueprint 13: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 20 clay. Each geode robot costs 3 ore and 14 obsidian.
+Blueprint 14: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 4 ore and 20 clay. Each geode robot costs 2 ore and 15 obsidian.
+Blueprint 15: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 4 ore and 15 clay. Each geode robot costs 3 ore and 12 obsidian.
+Blueprint 16: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 17 clay. Each geode robot costs 3 ore and 19 obsidian.
+Blueprint 17: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 4 ore and 9 obsidian.
+Blueprint 18: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 6 clay. Each geode robot costs 3 ore and 16 obsidian.
+Blueprint 19: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 6 clay. Each geode robot costs 2 ore and 14 obsidian.
+Blueprint 20: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 4 ore and 11 clay. Each geode robot costs 3 ore and 15 obsidian.
+Blueprint 21: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 18 clay. Each geode robot costs 4 ore and 19 obsidian.
+Blueprint 22: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 15 clay. Each geode robot costs 2 ore and 20 obsidian.
+Blueprint 23: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 5 clay. Each geode robot costs 2 ore and 10 obsidian.
+Blueprint 24: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 10 clay. Each geode robot costs 2 ore and 14 obsidian.
+Blueprint 25: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 7 clay. Each geode robot costs 4 ore and 13 obsidian.
+Blueprint 26: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 20 clay. Each geode robot costs 2 ore and 20 obsidian.
+Blueprint 27: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 18 clay. Each geode robot costs 2 ore and 19 obsidian.
+Blueprint 28: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 10 clay. Each geode robot costs 2 ore and 7 obsidian.
+Blueprint 29: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 15 clay. Each geode robot costs 3 ore and 7 obsidian.
+Blueprint 30: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 20 clay. Each geode robot costs 4 ore and 18 obsidian.
diff --git a/2022/19/test b/2022/19/test
@@ -0,0 +1,2 @@
+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.
