From 488b35ff0ce9ac05cdc0852dd0026614dc23f4d6 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Wed, 20 Dec 2023 10:20:37 +0200 Subject: Day 19 --- 2023/src/bin/day_19.rs | 297 +++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 290 insertions(+), 7 deletions(-) (limited to '2023/src') diff --git a/2023/src/bin/day_19.rs b/2023/src/bin/day_19.rs index fd25a5d..8a7dabd 100644 --- a/2023/src/bin/day_19.rs +++ b/2023/src/bin/day_19.rs @@ -1,10 +1,19 @@ -use nom::IResult; -use std::{collections::BTreeMap, fs}; +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{alpha1, line_ending, u32 as nom_u32}, + combinator::{map, value}, + multi::separated_list1, + sequence::{pair, preceded, terminated, tuple}, + IResult, +}; +use std::{collections::BTreeMap, fs, ops::Range}; fn main() -> Result<(), Box> { let input = fs::read_to_string("inputs/day_19.txt")?; let parsed = PartSortingMess::parser(&input).unwrap().1; - dbg!(&parsed); + dbg!(&parsed.accepted_part_ratings()); + dbg!(&parsed.count_distinct_combinations()); Ok(()) } @@ -18,7 +27,7 @@ struct PartSortingMess { #[derive(Debug)] struct Workflow { id: String, - conditions: WorkflowStep, + conditions: Vec, if_none_match: WorkflowOutcome, } @@ -29,7 +38,7 @@ struct WorkflowStep { result: WorkflowOutcome, } -#[derive(Debug)] +#[derive(Debug, Clone, PartialEq, Eq)] enum PartField { X, M, @@ -43,7 +52,7 @@ enum WorkflowCondition { GreaterThan(u32), } -#[derive(Debug)] +#[derive(Debug, Clone, PartialEq, Eq)] enum WorkflowOutcome { Accept, Reject, @@ -58,8 +67,282 @@ struct Part { s: u32, } +#[derive(Debug, Clone)] +struct PartRange { + x: Range, + m: Range, + a: Range, + s: Range, +} + impl PartSortingMess { fn parser(input: &str) -> IResult<&str, Self> { - todo!() + map( + tuple(( + separated_list1(line_ending, Workflow::parser), + line_ending, + line_ending, + separated_list1(line_ending, Part::parser), + )), + |(workflows, _, _, parts)| PartSortingMess { + workflows: workflows + .into_iter() + .map(|workflow| (workflow.id.clone(), workflow)) + .collect(), + parts, + }, + )(input) + } + + fn accepted_part_ratings(&self) -> u32 { + let mut rating_sum = 0; + + for part in &self.parts { + let mut outcome = WorkflowOutcome::Defer("in".into()); + while let Some(workflow_id) = outcome.next_workflow_id() { + let workflow = self.workflows.get(&workflow_id).unwrap(); + outcome = workflow.process(part); + } + + if outcome == WorkflowOutcome::Accept { + rating_sum += part.rating(); + } + } + + rating_sum + } + + fn count_distinct_combinations(&self) -> u64 { + self.count_combinations_for_workflow( + "in", + &PartRange { + x: 1..4001, + m: 1..4001, + a: 1..4001, + s: 1..4001, + }, + ) + + // potential workflow optimizations to make the stack not so deep + // - eliminate conditions in a workflow where everything has the same outcome + // - inline workflows with a single outcome + // - eliminate unreachable branches like a<10, a<5 + } + + fn count_combinations_for_workflow(&self, workflow_id: &str, part_range: &PartRange) -> u64 { + if part_range.combinations() == 0 { + 0 + } else { + let mut combinations = 0; + + let workflow = self.workflows.get(workflow_id).unwrap(); + let mut remaining_range = part_range.clone(); + for condition in &workflow.conditions { + let matched_range: PartRange; + (matched_range, remaining_range) = + remaining_range.partition(&condition.field, &condition.condition); + combinations += match &condition.result { + WorkflowOutcome::Accept => matched_range.combinations(), + WorkflowOutcome::Reject => 0, + WorkflowOutcome::Defer(next_workflow_id) => { + self.count_combinations_for_workflow(&next_workflow_id, &matched_range) + } + }; + } + combinations += match &workflow.if_none_match { + WorkflowOutcome::Accept => remaining_range.combinations(), + WorkflowOutcome::Reject => 0, + WorkflowOutcome::Defer(next_workflow_id) => { + self.count_combinations_for_workflow(&next_workflow_id, &remaining_range) + } + }; + + combinations + } + } +} + +impl Workflow { + fn parser(input: &str) -> IResult<&str, Self> { + map( + pair( + alpha1, + preceded( + tag("{"), + terminated( + pair( + separated_list1(tag(","), WorkflowStep::parser), + preceded(tag(","), WorkflowOutcome::parser), + ), + tag("}"), + ), + ), + ), + |(id, (conditions, if_none_match)): (&str, _)| Workflow { + id: id.to_owned(), + conditions, + if_none_match, + }, + )(input) + } + + fn process(&self, part: &Part) -> WorkflowOutcome { + for condition in &self.conditions { + let val = part.get(&condition.field); + if condition.condition.matches(val) { + return condition.result.clone(); + } + } + self.if_none_match.clone() + } +} + +impl WorkflowStep { + fn parser(input: &str) -> IResult<&str, Self> { + map( + tuple(( + PartField::parser, + WorkflowCondition::parser, + preceded(tag(":"), WorkflowOutcome::parser), + )), + |(field, condition, result)| WorkflowStep { + field, + condition, + result, + }, + )(input) + } +} + +impl PartField { + fn parser(input: &str) -> IResult<&str, Self> { + alt(( + value(PartField::X, tag("x")), + value(PartField::M, tag("m")), + value(PartField::A, tag("a")), + value(PartField::S, tag("s")), + ))(input) + } +} + +impl WorkflowCondition { + fn parser(input: &str) -> IResult<&str, Self> { + alt(( + map(preceded(tag("<"), nom_u32), WorkflowCondition::LessThan), + map(preceded(tag(">"), nom_u32), WorkflowCondition::GreaterThan), + ))(input) + } + + fn matches(&self, val: u32) -> bool { + match self { + WorkflowCondition::LessThan(me) => val < *me, + WorkflowCondition::GreaterThan(me) => val > *me, + } + } + + fn partition(&self, val: &Range) -> (Range, Range) { + match self { + WorkflowCondition::LessThan(me) => (val.start..*me, *me..val.end), + WorkflowCondition::GreaterThan(me) => (*me + 1..val.end, val.start..*me + 1), + } + } +} + +impl WorkflowOutcome { + fn parser(input: &str) -> IResult<&str, Self> { + alt(( + value(WorkflowOutcome::Accept, tag("A")), + value(WorkflowOutcome::Reject, tag("R")), + map(alpha1, |id: &str| WorkflowOutcome::Defer(id.to_owned())), + ))(input) + } + + fn next_workflow_id(&self) -> Option { + match self { + WorkflowOutcome::Accept | WorkflowOutcome::Reject => None, + WorkflowOutcome::Defer(id) => Some(id.clone()), + } + } +} + +impl Part { + fn parser(input: &str) -> IResult<&str, Self> { + map( + tuple(( + tag("{x="), + nom_u32, + tag(",m="), + nom_u32, + tag(",a="), + nom_u32, + tag(",s="), + nom_u32, + tag("}"), + )), + |(_, x, _, m, _, a, _, s, _)| Part { x, m, a, s }, + )(input) + } + + fn rating(&self) -> u32 { + self.x + self.m + self.a + self.s + } + + fn get(&self, field: &PartField) -> u32 { + match field { + PartField::X => self.x, + PartField::M => self.m, + PartField::A => self.a, + PartField::S => self.s, + } + } +} + +impl PartRange { + fn combinations(&self) -> u64 { + if self.x.is_empty() || self.m.is_empty() || self.a.is_empty() || self.s.is_empty() { + 0 + } else { + (self.x.end - self.x.start) as u64 + * (self.m.end - self.m.start) as u64 + * (self.a.end - self.a.start) as u64 + * (self.s.end - self.s.start) as u64 + } + } + + fn partition( + &self, + field: &PartField, + condition: &WorkflowCondition, + ) -> (PartRange, PartRange) { + let (matched_range, unmatched_range) = match field { + PartField::X => condition.partition(&self.x), + PartField::M => condition.partition(&self.m), + PartField::A => condition.partition(&self.a), + PartField::S => condition.partition(&self.s), + }; + + let mut matched_part_range = self.clone(); + let mut unmatched_part_range = self.clone(); + + match field { + PartField::X => { + matched_part_range.x = matched_range; + unmatched_part_range.x = unmatched_range; + } + PartField::M => { + matched_part_range.m = matched_range; + unmatched_part_range.m = unmatched_range; + } + PartField::A => { + matched_part_range.a = matched_range; + unmatched_part_range.a = unmatched_range; + } + PartField::S => { + matched_part_range.s = matched_range; + unmatched_part_range.s = unmatched_range; + } + }; + + (matched_part_range, unmatched_part_range) } } -- cgit v1.2.3