From 28122a7897219423d70ddd73c7dec0d68cfdec1b Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Tue, 19 Dec 2023 02:03:48 -0500 Subject: day 19 --- src/bin/2023/day19.rs | 429 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/bin/2023/main.rs | 2 + 2 files changed, 431 insertions(+) create mode 100644 src/bin/2023/day19.rs (limited to 'src/bin') diff --git a/src/bin/2023/day19.rs b/src/bin/2023/day19.rs new file mode 100644 index 0000000..87fdda0 --- /dev/null +++ b/src/bin/2023/day19.rs @@ -0,0 +1,429 @@ +#![allow(dead_code)] +#![allow(unused_variables)] + +use advent_of_code::prelude::*; + +#[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)] +pub enum Category { + X, + M, + A, + S, +} + +impl std::str::FromStr for Category { + type Err = anyhow::Error; + + fn from_str(s: &str) -> std::result::Result { + Ok(match s { + "x" => Self::X, + "m" => Self::M, + "a" => Self::A, + "s" => Self::S, + _ => bail!("unknown category {s}"), + }) + } +} + +#[derive(Debug, Clone, PartialEq, Eq)] +pub enum Target { + Accept, + Reject, + Workflow(String), +} + +impl std::str::FromStr for Target { + type Err = anyhow::Error; + + fn from_str(s: &str) -> std::result::Result { + Ok(match s { + "R" => Self::Reject, + "A" => Self::Accept, + workflow => Self::Workflow(workflow.to_string()), + }) + } +} + +#[derive(Clone, Debug)] +pub struct CategoryRanges { + x: std::ops::RangeInclusive, + m: std::ops::RangeInclusive, + a: std::ops::RangeInclusive, + s: std::ops::RangeInclusive, +} + +impl CategoryRanges { + fn new( + x: std::ops::RangeInclusive, + m: std::ops::RangeInclusive, + a: std::ops::RangeInclusive, + s: std::ops::RangeInclusive, + ) -> Self { + Self { x, m, a, s } + } + + fn is_empty(&self) -> bool { + self.x.is_empty() + || self.m.is_empty() + || self.a.is_empty() + || self.s.is_empty() + } + + fn size(&self) -> i64 { + (self.x.end() - self.x.start() + 1) + * (self.m.end() - self.m.start() + 1) + * (self.a.end() - self.a.start() + 1) + * (self.s.end() - self.s.start() + 1) + } + + fn with_x(self, x: std::ops::RangeInclusive) -> Self { + Self { + x, + m: self.m, + a: self.a, + s: self.s, + } + } + + fn with_m(self, m: std::ops::RangeInclusive) -> Self { + Self { + x: self.x, + m, + a: self.a, + s: self.s, + } + } + + fn with_a(self, a: std::ops::RangeInclusive) -> Self { + Self { + x: self.x, + m: self.m, + a, + s: self.s, + } + } + + fn with_s(self, s: std::ops::RangeInclusive) -> Self { + Self { + x: self.x, + m: self.m, + a: self.a, + s, + } + } +} + +#[derive(Debug)] +pub struct Conditional { + category: Category, + less: bool, + val: i64, +} + +#[derive(Debug)] +pub struct Rule { + conditional: Option, + target: Target, +} + +impl Rule { + fn split( + &self, + range: CategoryRanges, + ) -> (Option, Option<(Target, CategoryRanges)>) { + let Some(conditional) = &self.conditional else { + return (None, Some((self.target.clone(), range))); + }; + match conditional.category { + Category::X => { + let (remaining, matched) = if conditional.less { + ( + range + .clone() + .with_x(conditional.val..=*range.x.end()), + range + .clone() + .with_x(*range.x.start()..=(conditional.val - 1)), + ) + } else { + ( + range + .clone() + .with_x(*range.x.start()..=conditional.val), + range + .clone() + .with_x((conditional.val + 1)..=*range.x.end()), + ) + }; + ( + if remaining.is_empty() { + None + } else { + Some(remaining) + }, + if matched.is_empty() { + None + } else { + Some((self.target.clone(), matched)) + }, + ) + } + Category::M => { + let (remaining, matched) = if conditional.less { + ( + range + .clone() + .with_m(conditional.val..=*range.m.end()), + range + .clone() + .with_m(*range.m.start()..=(conditional.val - 1)), + ) + } else { + ( + range + .clone() + .with_m(*range.m.start()..=conditional.val), + range + .clone() + .with_m((conditional.val + 1)..=*range.m.end()), + ) + }; + ( + if remaining.is_empty() { + None + } else { + Some(remaining) + }, + if matched.is_empty() { + None + } else { + Some((self.target.clone(), matched)) + }, + ) + } + Category::A => { + let (remaining, matched) = if conditional.less { + ( + range + .clone() + .with_a(conditional.val..=*range.a.end()), + range + .clone() + .with_a(*range.a.start()..=(conditional.val - 1)), + ) + } else { + ( + range + .clone() + .with_a(*range.a.start()..=conditional.val), + range + .clone() + .with_a((conditional.val + 1)..=*range.a.end()), + ) + }; + ( + if remaining.is_empty() { + None + } else { + Some(remaining) + }, + if matched.is_empty() { + None + } else { + Some((self.target.clone(), matched)) + }, + ) + } + Category::S => { + let (remaining, matched) = if conditional.less { + ( + range + .clone() + .with_s(conditional.val..=*range.s.end()), + range + .clone() + .with_s(*range.s.start()..=(conditional.val - 1)), + ) + } else { + ( + range + .clone() + .with_s(*range.s.start()..=conditional.val), + range + .clone() + .with_s((conditional.val + 1)..=*range.s.end()), + ) + }; + ( + if remaining.is_empty() { + None + } else { + Some(remaining) + }, + if matched.is_empty() { + None + } else { + Some((self.target.clone(), matched)) + }, + ) + } + } + } +} + +#[derive(Debug)] +pub struct Workflows(HashMap>); + +impl Workflows { + fn accept(&self, part: &Part) -> bool { + let mut workflow = "in"; + loop { + for rule in &self.0[workflow] { + if let Some(conditional) = &rule.conditional { + let left = part.0[&conditional.category]; + let right = conditional.val; + if conditional.less { + if left >= right { + continue; + } + } else if left <= right { + continue; + } + } + match &rule.target { + Target::Accept => return true, + Target::Reject => return false, + Target::Workflow(new_workflow) => workflow = new_workflow, + } + break; + } + } + } +} + +#[derive(Debug)] +pub struct Part(HashMap); + +impl Part { + fn value(&self) -> i64 { + self.0.values().sum() + } +} + +pub fn parse(fh: File) -> Result<(Workflows, Vec)> { + let mut lines = parse::raw_lines(fh); + let workflows = parse::chunk(&mut lines) + .map(|line| { + let cap = regex_captures!(r"(\w+)\{(.*)\}", &line).unwrap(); + let workflow = cap[1].to_string(); + let rules = cap[2] + .split(',') + .map(|rule| { + if rule.contains(':') { + let cap = + regex_captures!(r"(\w+)(<|>)(\d+):(\w+)", &rule) + .unwrap(); + let category = cap[1].parse().unwrap(); + let less = &cap[2] == "<"; + let val = cap[3].parse().unwrap(); + let target = cap[4].parse().unwrap(); + + Rule { + conditional: Some(Conditional { + category, + less, + val, + }), + target, + } + } else { + Rule { + conditional: None, + target: rule.parse().unwrap(), + } + } + }) + .collect(); + (workflow, rules) + }) + .collect(); + let parts = parse::chunk(&mut lines) + .map(|line| { + let line = &line[1..(line.len() - 1)]; + Part( + line.split(',') + .map(|category| { + let mut parts = category.split('='); + let category = parts.next().unwrap().parse().unwrap(); + let value = parts.next().unwrap().parse().unwrap(); + (category, value) + }) + .collect(), + ) + }) + .collect(); + Ok((Workflows(workflows), parts)) +} + +pub fn part1((workflows, parts): (Workflows, Vec)) -> Result { + Ok(parts + .into_iter() + .filter_map(|part| workflows.accept(&part).then(|| part.value())) + .sum()) +} + +pub fn part2((workflows, _): (Workflows, Vec)) -> Result { + let mut ranges = vec![( + Target::Workflow("in".to_string()), + CategoryRanges::new(1..=4000, 1..=4000, 1..=4000, 1..=4000), + )]; + loop { + let mut new_ranges = vec![]; + let mut done = true; + for (workflow, range) in &ranges { + let mut range = range.clone(); + let Target::Workflow(workflow) = workflow else { + new_ranges.push((workflow.clone(), range)); + continue; + }; + for rule in &workflows.0[workflow.as_str()] { + let (old_range, new_range) = rule.split(range); + if let Some(new_range) = new_range { + new_ranges.push(new_range); + done = false; + } + if let Some(old_range) = old_range { + range = old_range; + } else { + break; + } + } + } + ranges = new_ranges; + if done { + break; + } + } + Ok(ranges + .into_iter() + .filter_map(|(target, range)| { + if target == Target::Accept { + Some(range.size()) + } else { + None + } + }) + .sum()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2023, 19).unwrap()).unwrap()).unwrap(), + 449531 + ); + assert_eq!( + part2(parse(parse::data(2023, 19).unwrap()).unwrap()).unwrap(), + 122756210763577 + ); +} diff --git a/src/bin/2023/main.rs b/src/bin/2023/main.rs index b9eb819..1afb78e 100644 --- a/src/bin/2023/main.rs +++ b/src/bin/2023/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!(2023, opt.day, opt.puzzle, day16), 17 => advent_of_code::day!(2023, opt.day, opt.puzzle, day17), 18 => advent_of_code::day!(2023, opt.day, opt.puzzle, day18), + 19 => advent_of_code::day!(2023, opt.day, opt.puzzle, day19), // NEXT PART _ => panic!("unknown day {}", opt.day), } -- cgit v1.2.3-54-g00ecf