From ace26471a062eb99ff4fd16620cc6ad7b31ac115 Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Mon, 19 Dec 2022 02:04:39 -0500 Subject: day 19 --- benches/2022.rs | 5 + data/2022/19.txt | 30 +++++ src/bin/2022/day19.rs | 326 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/bin/2022/main.rs | 2 + 4 files changed, 363 insertions(+) create mode 100644 data/2022/19.txt create mode 100644 src/bin/2022/day19.rs 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 { + 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.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.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.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.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, + 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, + 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 { + 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> { + Ok(parse::raw_lines(fh).map(|s| s.parse().unwrap())) +} + +pub fn part1(blueprints: impl Iterator) -> Result { + 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) -> Result { + 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), } -- cgit v1.2.3-54-g00ecf