diff options
Diffstat (limited to 'src/day_19.rs')
-rw-r--r-- | src/day_19.rs | 230 |
1 files changed, 230 insertions, 0 deletions
diff --git a/src/day_19.rs b/src/day_19.rs new file mode 100644 index 0000000..db42655 --- /dev/null +++ b/src/day_19.rs @@ -0,0 +1,230 @@ +use std::{cmp::Ordering, collections::HashMap, ops::ControlFlow, str::FromStr}; + +use crate::{Problem, Solution}; + +pub struct Day19; + +impl Problem for Day19 { + const DAY: u8 = 19; + + const INPUT: &'static str = include_str!("../input/day_19.txt"); +} + +impl Solution for Day19 { + type Answer1 = usize; + + type Answer2 = usize; + + fn part_1(input: &str) -> anyhow::Result<Self::Answer1> { + let (workflows, parts) = input.split_once("\n\n").unwrap(); + let workflows = workflows + .lines() + .map(parse_workflow) + .try_collect::<HashMap<[char; 3], Workflow>>() + .unwrap(); + + let parts = parts + .lines() + .map(parse_part) + .try_collect::<Vec<[usize; 4]>>()?; + + let mut next = ['i', 'n', ' ']; + let mut sum = 0; + + for part in parts { + while let Some(workflow) = workflows.get(&next) { + if let ControlFlow::Continue(n) = workflow.process_part(&part) { + next = n + } else { + sum += part.iter().sum::<usize>() + } + } + } + + Ok(sum) + } + + fn part_2(input: &str) -> anyhow::Result<Self::Answer2> { + todo!() + } +} + +fn parse_workflow(s: &str) -> anyhow::Result<([char; 3], Workflow)> { + let (name, rules) = s + .split_once('{') + .ok_or_else(|| anyhow::format_err!("Failed to parse workflow: {s}"))?; + + let mut iter = name.chars(); + + let name = [ + iter.next().unwrap(), + iter.next().unwrap_or(' '), + iter.next().unwrap_or(' '), + ]; + + Ok((name, rules.trim_end_matches('}').parse()?)) +} + +fn parse_part(s: &str) -> anyhow::Result<[usize; 4]> { + s.strip_prefix('{') + .and_then(|s| s.strip_suffix('}')) + .ok_or(anyhow::format_err!("Invalid part format: {s}"))? + .split(',') + .map(|s| s.trim_start_matches(['x', 'm', 'a', 's', '=']).parse()) + .try_collect::<Vec<usize>>()? + .try_into() + .map_err(|_| anyhow::format_err!("Failed to parse part: {s}")) +} + +fn parse_output(s: &str) -> anyhow::Result<Output> { + Ok(match s { + "A" => ControlFlow::Break(true), + "R" => ControlFlow::Break(false), + w if (2..=3).contains(&w.len()) => { + let mut iter = w.chars(); + + ControlFlow::Continue([ + iter.next().unwrap(), + iter.next().unwrap_or(' '), + iter.next().unwrap_or(' '), + ]) + } + e => Err(anyhow::format_err!("Invalid output value: {e}"))?, + }) +} + +type Part = [usize; 4]; +type Label = [char; 3]; +type Output = ControlFlow<bool, Label>; + +struct Workflow { + rules: Vec<Rule>, + last: ControlFlow<bool, Label>, +} + +impl Workflow { + fn process_part(&self, part: &Part) -> ControlFlow<bool, Label> { + self.rules + .iter() + .find_map(|r| r.process_part(part)) + .unwrap_or(self.last) + } +} + +impl FromStr for Workflow { + type Err = anyhow::Error; + + fn from_str(s: &str) -> Result<Self, Self::Err> { + let mut iter = s.split(','); + + let last = iter + .next_back() + .ok_or_else(|| anyhow::format_err!("Workflow contains no rules: {s}")) + .and_then(parse_output)?; + + let rules = iter.map(|s| s.parse()).try_collect::<Vec<Rule>>()?; + + Ok(Self { rules, last }) + } +} + +struct Rule { + field: u8, + cmp: Ordering, + value: usize, + output: ControlFlow<bool, Label>, +} + +impl Rule { + fn process_part(&self, part: &[usize; 4]) -> Option<ControlFlow<bool, Label>> { + (self.value.cmp(&part[self.field as usize]) == self.cmp).then_some(self.output) + } +} + +impl FromStr for Rule { + type Err = anyhow::Error; + + fn from_str(s: &str) -> Result<Self, Self::Err> { + let (cond, output) = s + .split_once(':') + .ok_or_else(|| anyhow::format_err!("Failed to parse rule: {s}"))?; + + let mut iter = cond.chars(); + + let field = match iter.next() { + Some('x') => 0, + Some('m') => 1, + Some('a') => 2, + Some('s') => 3, + f => anyhow::bail!("Failed to parse rule field: {f:?}"), + }; + + let cmp = match iter.next() { + Some('<') => Ordering::Less, + Some('=') => Ordering::Equal, + Some('>') => Ordering::Greater, + c => Err(anyhow::format_err!("Failed to parse comparison: {c:?}"))?, + }; + + let value = iter.collect::<String>().parse()?; + + Ok(Self { + field, + cmp, + value, + output: parse_output(output)?, + }) + } +} + +#[repr(u8)] +enum Catagory { + X, + M, + A, + S, +} + +impl FromStr for Catagory { + type Err = anyhow::Error; + + fn from_str(s: &str) -> Result<Self, Self::Err> { + Ok(match s { + "x" => Self::X, + "m" => Self::M, + "a" => Self::A, + "s" => Self::S, + s => anyhow::bail!("Failed to parse field: {s}"), + }) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + const INPUT: &str = indoc::indoc! {r#" + px{a<2006:qkq,m>2090:A,rfg} + pv{a>1716:R,A} + lnx{m>1548:A,A} + rfg{s<537:gd,x>2440:R,A} + qs{s>3448:A,lnx} + qkq{x<1416:A,crn} + crn{x>2662:A,R} + in{s<1351:px,qqz} + qqz{s>2770:qs,m<1801:hdj,R} + gd{a>3333:R,R} + hdj{m>838:A,pv} + + {x=787,m=2655,a=1222,s=2876} + {x=1679,m=44,a=2067,s=496} + {x=2036,m=264,a=79,s=2244} + {x=2461,m=1339,a=466,s=291} + {x=2127,m=1623,a=2188,s=1013} + "#}; + + #[test] + fn test_part_1() -> anyhow::Result<()> { + Ok(assert_eq!(19114, Day19::part_1(INPUT)?)) + } +} |