day19.rs

use std::collections::HashMap;

type Rating = Vec<i16>; // X, M, A, S
#[derive(Debug)]
struct Branch<'a>(&'a str, Option<(usize, u8, i16)>);
type Workflow<'a> = Vec<Branch<'a>>;

fn parse(input: &str) -> (HashMap<&str, Workflow>, Vec<Rating>) {
    let (workflows, ratings) = input.split_once("\n\n").unwrap();
    let workflows = workflows
        .lines()
        .map(|l| {
            let (name, branches) = l.split_once('{').unwrap();
            let branches = branches[..branches.len() - 1]
                .split(',')
                .map(|b| {
                    if let Some((cond, target)) = b.split_once(':') {
                        let c = cond.as_bytes()[0];
                        let r = b"xmas".iter().position(|b| *b == c).unwrap();
                        Branch(
                            target,
                            Some((r, cond.as_bytes()[1], cond[2..].parse().unwrap())),
                        )
                    } else {
                        Branch(b, None)
                    }
                })
                .collect();
            (name, branches)
        })
        .collect();
    let ratings = ratings
        .lines()
        .map(|l| {
            l[1..l.len() - 1]
                .split(',')
                .map(|s| s[2..].parse().unwrap())
                .collect()
        })
        .collect();
    (workflows, ratings)
}

#[aoc(day19, part1)]
fn part1(input: &str) -> i64 {
    let (workflows, ratings) = parse(input);
    ratings
        .into_iter()
        .filter_map(|r| run(&workflows, &r).then(|| r.into_iter().map(i64::from).sum::<i64>()))
        .sum()
}

fn run(workflows: &HashMap<&str, Workflow>, r: &[i16]) -> bool {
    process_rule(
        workflows,
        "in",
        [
            (r[0], r[0] + 1),
            (r[1], r[1] + 1),
            (r[2], r[2] + 1),
            (r[3], r[3] + 1),
        ],
    ) == 1
}

#[aoc(day19, part2)]
fn part2(input: &str) -> i64 {
    process_rule(&parse(input).0, "in", [(1, 4001); 4])
}

fn process_rule(
    workflows: &HashMap<&str, Vec<Branch<'_>>>,
    rule: &str,
    mut possible: [(i16, i16); 4],
) -> i64 {
    match rule {
        "A" => {
            return possible
                .into_iter()
                .map(|(l, h)| i64::from(h - l))
                .product::<i64>()
        }
        "R" => return 0,
        _ => (),
    }
    let mut t = 0;
    for r in &workflows[&rule] {
        let short = |target| t + process_rule(workflows, target, possible);
        match *r {
            Branch(target, None) => return short(target),
            Branch(target, Some((idx, op, limit))) => match (possible[idx], op) {
                ((_, u), b'<') if u <= limit => {
                    return short(target);
                }
                ((l, _), b'>') if l > limit => {
                    return short(target);
                }
                ((l, u), b'<') if l < limit => {
                    possible[idx] = (l, limit);
                    t += process_rule(workflows, target, possible);
                    possible[idx] = (limit, u);
                }
                ((l, u), b'>') if u >= limit => {
                    possible[idx] = (limit + 1, u);
                    t += process_rule(workflows, target, possible);
                    possible[idx] = (l, limit + 1);
                }
                _ => (),
            },
        };
    }
    t
}