444 lines
11 KiB
Rust
444 lines
11 KiB
Rust
use std::{
|
|
collections::{HashMap, VecDeque},
|
|
ops::Range,
|
|
};
|
|
|
|
use itertools::Itertools;
|
|
use regex::Regex;
|
|
|
|
pub fn run() {
|
|
let input = include_str!("../input/day19.txt");
|
|
// let input = 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}
|
|
// "#;
|
|
|
|
// let input = r#"
|
|
// in{a>2000:A,R}
|
|
|
|
// {x=0,m=0,a=0,s=0}
|
|
// "#;
|
|
|
|
let (workflows, parts) = parse(input);
|
|
|
|
let accepted_sum: usize = parts
|
|
.iter()
|
|
.filter(|p| run_part(&workflows, p) == WorkflowResult::Accept)
|
|
.map(|p| p.sum() as usize)
|
|
.sum();
|
|
dbg!(accepted_sum);
|
|
|
|
dbg!(run_ranges(&workflows, PartRange::full()));
|
|
}
|
|
|
|
fn parse(s: &str) -> (HashMap<&str, Workflow<'_>>, Vec<Part>) {
|
|
let (workflows, parts) = s.trim().split_once("\n\n").unwrap();
|
|
let mut workflows_map = HashMap::new();
|
|
for l in workflows.lines() {
|
|
let l = l.trim();
|
|
let brace = l.find("{").unwrap();
|
|
let name = l.get(..brace).unwrap();
|
|
let workflow = l.get((brace + 1)..(l.len() - 1)).unwrap().into();
|
|
workflows_map.insert(name, workflow);
|
|
}
|
|
(
|
|
workflows_map,
|
|
parts.lines().map(|l| l.trim().into()).collect(),
|
|
)
|
|
}
|
|
|
|
fn run_part<'a>(workflows: &'a HashMap<&'a str, Workflow<'a>>, part: &Part) -> WorkflowResult<'a> {
|
|
let mut cur = "in";
|
|
loop {
|
|
let workflow = &workflows[cur];
|
|
let result = workflow.run(part);
|
|
match result {
|
|
WorkflowResult::Workflow(s) => cur = s,
|
|
_ => return result,
|
|
}
|
|
}
|
|
}
|
|
|
|
fn run_ranges<'a>(workflows: &'a HashMap<&'a str, Workflow<'a>>, range: PartRange) -> usize {
|
|
let mut ranges_to_process = VecDeque::from([(range, "in")]);
|
|
let mut accepted = vec![];
|
|
while let Some((r, id)) = ranges_to_process.pop_front() {
|
|
let results = workflows[id].partition_range(r);
|
|
for (range, result) in results {
|
|
match result {
|
|
WorkflowResult::Accept => accepted.push(range),
|
|
WorkflowResult::Reject => (),
|
|
WorkflowResult::Workflow(id) => ranges_to_process.push_back((range, id)),
|
|
}
|
|
}
|
|
}
|
|
accepted.into_iter().map(|r| r.product()).sum()
|
|
}
|
|
|
|
#[derive(Debug, Clone)]
|
|
struct Workflow<'a> {
|
|
rules: Vec<Rule<'a>>,
|
|
otherwise: WorkflowResult<'a>,
|
|
}
|
|
|
|
impl<'a> From<&'a str> for Workflow<'a> {
|
|
fn from(value: &'a str) -> Self {
|
|
let mut rules = vec![];
|
|
let mut otherwise = None;
|
|
let mut parts = value.split(",").peekable();
|
|
while let Some(s) = parts.next() {
|
|
if parts.peek().is_none() {
|
|
otherwise = Some(WorkflowResult::from(s));
|
|
} else {
|
|
rules.push(Rule::from(s));
|
|
}
|
|
}
|
|
Self {
|
|
rules,
|
|
otherwise: otherwise.unwrap(),
|
|
}
|
|
}
|
|
}
|
|
|
|
#[derive(Debug, Clone)]
|
|
struct Rule<'a> {
|
|
prop: Prop,
|
|
op: Op,
|
|
rhs: u32,
|
|
result: WorkflowResult<'a>,
|
|
}
|
|
|
|
impl<'a> From<&'a str> for Rule<'a> {
|
|
fn from(value: &'a str) -> Self {
|
|
let re = Regex::new("^([xmas])([<>])(\\d+):(\\w+)$").unwrap();
|
|
let captures = re.captures(value).unwrap();
|
|
Self {
|
|
prop: captures.get(1).unwrap().as_str().into(),
|
|
op: captures.get(2).unwrap().as_str().into(),
|
|
rhs: captures.get(3).unwrap().as_str().parse().unwrap(),
|
|
result: captures.get(4).unwrap().as_str().into(),
|
|
}
|
|
}
|
|
}
|
|
|
|
#[derive(Debug, Clone, Copy)]
|
|
enum Prop {
|
|
X,
|
|
M,
|
|
A,
|
|
S,
|
|
}
|
|
|
|
impl From<&str> for Prop {
|
|
fn from(value: &str) -> Self {
|
|
match value {
|
|
"x" => Self::X,
|
|
"m" => Self::M,
|
|
"a" => Self::A,
|
|
"s" => Self::S,
|
|
_ => panic!("invalid prop {}", value),
|
|
}
|
|
}
|
|
}
|
|
|
|
#[derive(Debug, Clone, Copy)]
|
|
enum Op {
|
|
LessThan,
|
|
GreaterThan,
|
|
}
|
|
|
|
impl From<&str> for Op {
|
|
fn from(value: &str) -> Self {
|
|
match value {
|
|
"<" => Op::LessThan,
|
|
">" => Op::GreaterThan,
|
|
_ => panic!("invalid op {}", value),
|
|
}
|
|
}
|
|
}
|
|
|
|
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
|
|
enum WorkflowResult<'a> {
|
|
Accept,
|
|
Reject,
|
|
Workflow(&'a str),
|
|
}
|
|
|
|
impl<'a> From<&'a str> for WorkflowResult<'a> {
|
|
fn from(value: &'a str) -> Self {
|
|
match value {
|
|
"A" => Self::Accept,
|
|
"R" => Self::Reject,
|
|
_ => Self::Workflow(value),
|
|
}
|
|
}
|
|
}
|
|
|
|
#[derive(Debug, Clone, Copy, Default)]
|
|
struct Part {
|
|
x: u32,
|
|
m: u32,
|
|
a: u32,
|
|
s: u32,
|
|
}
|
|
|
|
impl From<&str> for Part {
|
|
fn from(value: &str) -> Self {
|
|
let values = value
|
|
.strip_prefix("{")
|
|
.unwrap()
|
|
.strip_suffix("}")
|
|
.unwrap()
|
|
.split(",");
|
|
let mut part: Part = Default::default();
|
|
for s in values {
|
|
let field = match s.get(0..1) {
|
|
Some("x") => &mut part.x,
|
|
Some("m") => &mut part.m,
|
|
Some("a") => &mut part.a,
|
|
Some("s") => &mut part.s,
|
|
s => panic!("invalid field {:?}", s),
|
|
};
|
|
*field = s.get(2..).unwrap().parse().unwrap();
|
|
}
|
|
part
|
|
}
|
|
}
|
|
|
|
impl Part {
|
|
fn sum(&self) -> u32 {
|
|
self.x + self.m + self.a + self.s
|
|
}
|
|
|
|
fn get(&self, prop: Prop) -> u32 {
|
|
match prop {
|
|
Prop::X => self.x,
|
|
Prop::M => self.m,
|
|
Prop::A => self.a,
|
|
Prop::S => self.s,
|
|
}
|
|
}
|
|
}
|
|
|
|
impl<'a> Rule<'a> {
|
|
fn test(&self, part: &Part) -> bool {
|
|
let lhs = part.get(self.prop);
|
|
match self.op {
|
|
Op::LessThan => lhs < self.rhs,
|
|
Op::GreaterThan => lhs > self.rhs,
|
|
}
|
|
}
|
|
}
|
|
|
|
impl<'a> Workflow<'a> {
|
|
fn run(&self, part: &Part) -> WorkflowResult<'_> {
|
|
for rule in self.rules.iter() {
|
|
if rule.test(part) {
|
|
return rule.result;
|
|
}
|
|
}
|
|
self.otherwise
|
|
}
|
|
}
|
|
|
|
#[derive(Debug, Clone, PartialEq, Eq)]
|
|
struct PartRange {
|
|
x: Range<u32>,
|
|
m: Range<u32>,
|
|
a: Range<u32>,
|
|
s: Range<u32>,
|
|
}
|
|
|
|
impl PartRange {
|
|
fn full() -> Self {
|
|
Self {
|
|
x: 1..4001,
|
|
m: 1..4001,
|
|
a: 1..4001,
|
|
s: 1..4001,
|
|
}
|
|
}
|
|
|
|
fn prop(&self, prop: Prop) -> &Range<u32> {
|
|
match prop {
|
|
Prop::X => &self.x,
|
|
Prop::M => &self.m,
|
|
Prop::A => &self.a,
|
|
Prop::S => &self.s,
|
|
}
|
|
}
|
|
|
|
fn with(&self, prop: Prop, range: Range<u32>) -> Self {
|
|
let mut copy = self.clone();
|
|
match prop {
|
|
Prop::X => copy.x = range,
|
|
Prop::M => copy.m = range,
|
|
Prop::A => copy.a = range,
|
|
Prop::S => copy.s = range,
|
|
}
|
|
copy
|
|
}
|
|
|
|
fn product(&self) -> usize {
|
|
self.x.len() * self.m.len() * self.a.len() * self.s.len()
|
|
}
|
|
}
|
|
|
|
impl<'a> Rule<'a> {
|
|
fn partition_range(&self, range: PartRange) -> Partition {
|
|
let prop_range = range.prop(self.prop);
|
|
match self.op {
|
|
Op::LessThan => {
|
|
if self.rhs > prop_range.end {
|
|
Partition::matched(range)
|
|
} else if self.rhs < prop_range.start {
|
|
Partition::failed(range)
|
|
} else {
|
|
let matched = range.with(self.prop, prop_range.start..self.rhs);
|
|
let failed = range.with(self.prop, self.rhs..prop_range.end);
|
|
Partition::both(matched, failed)
|
|
}
|
|
}
|
|
Op::GreaterThan => {
|
|
if self.rhs < prop_range.start {
|
|
Partition::matched(range)
|
|
} else if self.rhs > prop_range.end {
|
|
Partition::failed(range)
|
|
} else {
|
|
let matched = range.with(self.prop, (self.rhs + 1)..prop_range.end);
|
|
let failed = range.with(self.prop, prop_range.start..(self.rhs + 1));
|
|
Partition::both(matched, failed)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
#[derive(Debug, Clone, PartialEq, Eq)]
|
|
struct Partition {
|
|
matched: Option<PartRange>,
|
|
failed: Option<PartRange>,
|
|
}
|
|
|
|
impl Partition {
|
|
fn both(matched: PartRange, failed: PartRange) -> Self {
|
|
Self {
|
|
matched: Some(matched),
|
|
failed: Some(failed),
|
|
}
|
|
}
|
|
|
|
fn matched(matched: PartRange) -> Self {
|
|
Self {
|
|
matched: Some(matched),
|
|
failed: None,
|
|
}
|
|
}
|
|
|
|
fn failed(failed: PartRange) -> Self {
|
|
Self {
|
|
matched: None,
|
|
failed: Some(failed),
|
|
}
|
|
}
|
|
}
|
|
|
|
impl<'a> Workflow<'a> {
|
|
fn partition_range(&self, range: PartRange) -> Vec<(PartRange, WorkflowResult)> {
|
|
let mut results = vec![];
|
|
let mut cur = Some(range);
|
|
for rule in self.rules.iter() {
|
|
let partitioned = rule.partition_range(cur.unwrap());
|
|
if let Some(matched) = partitioned.matched {
|
|
results.push((matched, rule.result));
|
|
}
|
|
if let Some(failed) = partitioned.failed {
|
|
cur = Some(failed);
|
|
} else {
|
|
cur = None;
|
|
break;
|
|
}
|
|
}
|
|
if let Some(r) = cur {
|
|
results.push((r, self.otherwise));
|
|
}
|
|
results
|
|
}
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod tests {
|
|
use super::*;
|
|
|
|
#[test]
|
|
fn test_rule_partition() {
|
|
let rule = Rule {
|
|
prop: Prop::X,
|
|
op: Op::LessThan,
|
|
rhs: 2000,
|
|
result: WorkflowResult::Accept,
|
|
};
|
|
let range = PartRange::full();
|
|
assert_eq!(
|
|
rule.partition_range(range.clone()),
|
|
Partition::both(
|
|
range.with(Prop::X, 1..2000),
|
|
range.with(Prop::X, 2000..4001)
|
|
)
|
|
);
|
|
}
|
|
|
|
#[test]
|
|
fn test_workflow_partition() {
|
|
let workflow: Workflow = "a<2006:qkq,m>2090:A,rfg".into();
|
|
let results = workflow.partition_range(PartRange::full());
|
|
assert_eq!(
|
|
results,
|
|
vec![
|
|
(
|
|
PartRange {
|
|
x: 1..4001,
|
|
m: 1..4001,
|
|
a: 1..2006,
|
|
s: 1..4001,
|
|
},
|
|
WorkflowResult::Workflow("qkq")
|
|
),
|
|
(
|
|
PartRange {
|
|
x: 1..4001,
|
|
m: 2090..4001,
|
|
a: 2006..4001,
|
|
s: 1..4001,
|
|
},
|
|
WorkflowResult::Accept
|
|
),
|
|
(
|
|
PartRange {
|
|
x: 1..4001,
|
|
m: 1..2090,
|
|
a: 2006..4001,
|
|
s: 1..4001,
|
|
},
|
|
WorkflowResult::Workflow("rfg")
|
|
)
|
|
]
|
|
);
|
|
}
|
|
}
|