day 19

4 files changed, 363 insertions, 0 deletions

diff --git a/benches/2022.rs b/benches/2022.rs
index 68b4da4..6fc9bf7 100644
--- a/benches/2022.rs
+++ b/benches/2022.rs
@@ -37,6 +37,8 @@ mod day16;
 mod day17;
 #[path = "../src/bin/2022/day18.rs"]
 mod day18;
+#[path = "../src/bin/2022/day19.rs"]
+mod day19;
 // NEXT MOD
 
 day!(2022, 1, day1);
@@ -57,6 +59,7 @@ day!(2022, 15, day15);
 day!(2022, 16, day16);
 day!(2022, 17, day17);
 day!(2022, 18, day18);
+day!(2022, 19, day19);
 // NEXT DAY
 
 fn bench_2022(c: &mut criterion::Criterion) {
@@ -80,6 +83,7 @@ fn bench_2022(c: &mut criterion::Criterion) {
             day_combined!(2022, 16, day16);
             day_combined!(2022, 17, day17);
             day_combined!(2022, 18, day18);
+            day_combined!(2022, 19, day19);
             // NEXT DAY COMBINED
         })
     });
@@ -106,5 +110,6 @@ criterion::criterion_main!(
     bench_2022day16,
     bench_2022day17,
     bench_2022day18,
+    bench_2022day19,
     // NEXT GROUP
 );
diff --git a/data/2022/19.txt b/data/2022/19.txt
new file mode 100644
index 0000000..5c80431
--- /dev/null
+++ b/data/2022/19.txt
@@ -0,0 +1,30 @@
+Blueprint 1: 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 9 obsidian.
+Blueprint 2: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 19 clay. Each geode robot costs 3 ore and 19 obsidian.
+Blueprint 3: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 14 clay. Each geode robot costs 4 ore and 19 obsidian.
+Blueprint 4: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 3 ore and 8 obsidian.
+Blueprint 5: 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 6: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 7 clay. Each geode robot costs 3 ore and 20 obsidian.
+Blueprint 7: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 19 clay. Each geode robot costs 2 ore and 18 obsidian.
+Blueprint 8: 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 9: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 19 clay. Each geode robot costs 3 ore and 8 obsidian.
+Blueprint 10: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 14 clay. Each geode robot costs 4 ore and 11 obsidian.
+Blueprint 11: Each ore robot costs 2 ore. Each clay robot costs 2 ore. Each obsidian robot costs 2 ore and 15 clay. Each geode robot costs 2 ore and 7 obsidian.
+Blueprint 12: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 19 clay. Each geode robot costs 4 ore and 8 obsidian.
+Blueprint 13: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 16 clay. Each geode robot costs 2 ore and 9 obsidian.
+Blueprint 14: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 15 clay. Each geode robot costs 3 ore and 16 obsidian.
+Blueprint 15: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 20 clay. Each geode robot costs 2 ore and 9 obsidian.
+Blueprint 16: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 3 ore and 19 obsidian.
+Blueprint 17: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 9 clay. Each geode robot costs 3 ore and 15 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 2 ore and 20 obsidian.
+Blueprint 19: 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 20: 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 3 ore and 14 obsidian.
+Blueprint 21: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 19 clay. Each geode robot costs 4 ore and 11 obsidian.
+Blueprint 22: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 20 clay. Each geode robot costs 4 ore and 7 obsidian.
+Blueprint 23: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 9 clay. Each geode robot costs 2 ore and 20 obsidian.
+Blueprint 24: Each ore robot costs 2 ore. Each clay robot costs 2 ore. Each obsidian robot costs 2 ore and 17 clay. Each geode robot costs 2 ore and 10 obsidian.
+Blueprint 25: 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 3 ore and 13 obsidian.
+Blueprint 26: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 14 clay. Each geode robot costs 4 ore and 10 obsidian.
+Blueprint 27: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 20 clay. Each geode robot costs 2 ore and 12 obsidian.
+Blueprint 28: Each ore robot costs 3 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 29: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 5 clay. Each geode robot costs 4 ore and 11 obsidian.
+Blueprint 30: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 20 clay. Each geode robot costs 2 ore and 17 obsidian.
diff --git a/src/bin/2022/day19.rs b/src/bin/2022/day19.rs
new file mode 100644
index 0000000..f23fe2d
--- /dev/null
+++ b/src/bin/2022/day19.rs
@@ -0,0 +1,326 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use std::hash::{Hash, Hasher};
+
+use advent_of_code::prelude::*;
+use ahash::AHasher;
+
+#[derive(Clone, Hash)]
+pub struct Resources {
+    ore: u64,
+    clay: u64,
+    obsidian: u64,
+    geode: u64,
+}
+
+impl Resources {
+    pub fn new(ore: u64, clay: u64, obsidian: u64) -> Self {
+        Self {
+            ore,
+            clay,
+            obsidian,
+            geode: 0,
+        }
+    }
+
+    fn can_build(&self, blueprint: &Resources) -> Option<Self> {
+        let Some(ore) = self.ore.checked_sub(blueprint.ore)
+        else { return None };
+        let Some(clay) = self.clay.checked_sub(blueprint.clay)
+        else { return None };
+        let Some(obsidian) = self.obsidian.checked_sub(blueprint.obsidian)
+        else { return None };
+        let Some(geode) = self.geode.checked_sub(blueprint.geode)
+        else { return None };
+        Some(Self {
+            ore,
+            clay,
+            obsidian,
+            geode,
+        })
+    }
+}
+
+#[derive(Clone, Hash)]
+struct Pack {
+    resources: Resources,
+
+    ore_robots: u64,
+    clay_robots: u64,
+    obsidian_robots: u64,
+    geode_robots: u64,
+}
+
+impl Pack {
+    fn gather(&mut self) {
+        self.resources.ore += self.ore_robots;
+        self.resources.clay += self.clay_robots;
+        self.resources.obsidian += self.obsidian_robots;
+        self.resources.geode += self.geode_robots;
+    }
+
+    fn build_ore_robot(&self, blueprint: &Blueprint) -> Option<Self> {
+        self.resources.can_build(&blueprint.ore).map(|resources| {
+            let mut pack = self.clone();
+            pack.resources = resources;
+            pack
+        })
+    }
+
+    fn build_clay_robot(&self, blueprint: &Blueprint) -> Option<Self> {
+        self.resources.can_build(&blueprint.clay).map(|resources| {
+            let mut pack = self.clone();
+            pack.resources = resources;
+            pack
+        })
+    }
+
+    fn build_obsidian_robot(&self, blueprint: &Blueprint) -> Option<Self> {
+        self.resources
+            .can_build(&blueprint.obsidian)
+            .map(|resources| {
+                let mut pack = self.clone();
+                pack.resources = resources;
+                pack
+            })
+    }
+
+    fn build_geode_robot(&self, blueprint: &Blueprint) -> Option<Self> {
+        self.resources.can_build(&blueprint.geode).map(|resources| {
+            let mut pack = self.clone();
+            pack.resources = resources;
+            pack
+        })
+    }
+}
+
+impl Default for Pack {
+    fn default() -> Self {
+        Self {
+            resources: Resources {
+                ore: 0,
+                clay: 0,
+                obsidian: 0,
+                geode: 0,
+            },
+
+            ore_robots: 1,
+            clay_robots: 0,
+            obsidian_robots: 0,
+            geode_robots: 0,
+        }
+    }
+}
+
+pub struct Blueprint {
+    ore: Resources,
+    clay: Resources,
+    obsidian: Resources,
+    geode: Resources,
+}
+
+impl Blueprint {
+    fn max_geodes(&self, max_time: u64) -> u64 {
+        let mut memo = HashMap::new();
+        self.max_geodes_rec_memoized(
+            &mut memo,
+            Pack::default(),
+            0,
+            max_time,
+            false,
+            false,
+            false,
+        )
+    }
+
+    #[allow(clippy::too_many_arguments)]
+    fn max_geodes_rec_memoized(
+        &self,
+        memo: &mut HashMap<u64, u64>,
+        pack: Pack,
+        time: u64,
+        max_time: u64,
+        skipped_ore: bool,
+        skipped_clay: bool,
+        skipped_obsidian: bool,
+    ) -> u64 {
+        let mut hasher = AHasher::default();
+        pack.hash(&mut hasher);
+        time.hash(&mut hasher);
+        let hash = hasher.finish();
+        if let Some(max) = memo.get(&hash) {
+            return *max;
+        }
+        let max = self.max_geodes_rec(
+            memo,
+            pack,
+            time,
+            max_time,
+            skipped_ore,
+            skipped_clay,
+            skipped_obsidian,
+        );
+        memo.insert(hash, max);
+        max
+    }
+
+    #[allow(clippy::too_many_arguments)]
+    fn max_geodes_rec(
+        &self,
+        memo: &mut HashMap<u64, u64>,
+        mut pack: Pack,
+        time: u64,
+        max_time: u64,
+        skipped_ore: bool,
+        skipped_clay: bool,
+        skipped_obsidian: bool,
+    ) -> u64 {
+        if time >= max_time {
+            return pack.resources.geode;
+        }
+
+        if let Some(mut pack) = pack.build_geode_robot(self) {
+            pack.gather();
+            pack.geode_robots += 1;
+            return self.max_geodes_rec_memoized(
+                memo,
+                pack,
+                time + 1,
+                max_time,
+                false,
+                false,
+                false,
+            );
+        }
+
+        let mut max = 0;
+
+        let mut can_build_ore = false;
+        let mut can_build_clay = false;
+        let mut can_build_obsidian = false;
+        if skipped_ore {
+            can_build_ore = true;
+        } else if let Some(mut pack) = pack.build_ore_robot(self) {
+            pack.gather();
+            pack.ore_robots += 1;
+            let next = self.max_geodes_rec_memoized(
+                memo,
+                pack,
+                time + 1,
+                max_time,
+                false,
+                false,
+                false,
+            );
+            if next > max {
+                max = next;
+            }
+            can_build_ore = true;
+        }
+        if skipped_clay {
+            can_build_clay = true;
+        } else if let Some(mut pack) = pack.build_clay_robot(self) {
+            pack.gather();
+            pack.clay_robots += 1;
+            let next = self.max_geodes_rec_memoized(
+                memo,
+                pack,
+                time + 1,
+                max_time,
+                false,
+                false,
+                false,
+            );
+            if next > max {
+                max = next;
+            }
+            can_build_clay = true;
+        }
+        if skipped_obsidian {
+            can_build_obsidian = true;
+        } else if let Some(mut pack) = pack.build_obsidian_robot(self) {
+            pack.gather();
+            pack.obsidian_robots += 1;
+            let next = self.max_geodes_rec_memoized(
+                memo,
+                pack,
+                time + 1,
+                max_time,
+                false,
+                false,
+                false,
+            );
+            if next > max {
+                max = next;
+            }
+            can_build_obsidian = true;
+        }
+
+        pack.gather();
+        let next = self.max_geodes_rec_memoized(
+            memo,
+            pack,
+            time + 1,
+            max_time,
+            can_build_ore,
+            can_build_clay,
+            can_build_obsidian,
+        );
+        if next > max {
+            max = next;
+        }
+
+        max
+    }
+}
+
+impl std::str::FromStr for Blueprint {
+    type Err = Error;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        let cap = regex_captures!(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.", s).unwrap();
+        let ore = cap[1].parse()?;
+        let clay = cap[2].parse()?;
+        let obsidian_ore = cap[3].parse()?;
+        let obsidian_clay = cap[4].parse()?;
+        let geode_ore = cap[5].parse()?;
+        let geode_obsidian = cap[6].parse()?;
+        Ok(Blueprint {
+            ore: Resources::new(ore, 0, 0),
+            clay: Resources::new(clay, 0, 0),
+            obsidian: Resources::new(obsidian_ore, obsidian_clay, 0),
+            geode: Resources::new(geode_ore, 0, geode_obsidian),
+        })
+    }
+}
+
+pub fn parse(fh: File) -> Result<impl Iterator<Item = Blueprint>> {
+    Ok(parse::raw_lines(fh).map(|s| s.parse().unwrap()))
+}
+
+pub fn part1(blueprints: impl Iterator<Item = Blueprint>) -> Result<u64> {
+    let mut total = 0;
+    for (i, blueprint) in blueprints.enumerate() {
+        total += blueprint.max_geodes(24) * (i as u64 + 1);
+    }
+    Ok(total)
+}
+
+pub fn part2(mut blueprints: impl Iterator<Item = Blueprint>) -> Result<u64> {
+    Ok(blueprints.by_ref().next().unwrap().max_geodes(32)
+        * blueprints.by_ref().next().unwrap().max_geodes(32)
+        * blueprints.by_ref().next().unwrap().max_geodes(32))
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2022, 19).unwrap()).unwrap()).unwrap(),
+        1147
+    );
+    assert_eq!(
+        part2(parse(parse::data(2022, 19).unwrap()).unwrap()).unwrap(),
+        3080
+    );
+}
diff --git a/src/bin/2022/main.rs b/src/bin/2022/main.rs
index 6c02180..2aa8500 100644
--- a/src/bin/2022/main.rs
+++ b/src/bin/2022/main.rs
@@ -29,6 +29,7 @@ mod day15;
 mod day16;
 mod day17;
 mod day18;
+mod day19;
 // NEXT MOD
 
 #[paw::main]
@@ -53,6 +54,7 @@ fn main(opt: Opt) -> Result<()> {
         16 => advent_of_code::day!(2022, opt.day, opt.puzzle, day16),
         17 => advent_of_code::day!(2022, opt.day, opt.puzzle, day17),
         18 => advent_of_code::day!(2022, opt.day, opt.puzzle, day18),
+        19 => advent_of_code::day!(2022, opt.day, opt.puzzle, day19),
         // NEXT PART
         _ => panic!("unknown day {}", opt.day),
     }