AoC2020/src/bin/day19.rs

use std::collections::HashMap;
use std::error::Error;
use std::fs::File;
use std::io::{self, BufRead};
use std::vec::Vec;

#[derive(PartialEq, Clone, Debug)]
enum Rule {
    Terminal(char),
    NoneTerminal(Vec<Vec<u32>>),
}

fn read_rule(rule: &str) -> (u32, Rule) {
    let mut parts = rule.split(':');

    let num: u32 = parts
        .nth(0)
        .expect("Missing rule Number")
        .trim()
        .parse()
        .expect("Unable to parse rule numer");

    let rest = parts.nth(0).expect("Missing actual rule").trim();

    if rest.starts_with('"') {
        (
            num,
            Rule::Terminal(rest.chars().nth(1).expect("Rule char not found")),
        )
    } else {
        let options: Vec<Vec<u32>> = rest
            .split('|')
            .map(|o| {
                o.trim()
                    .split(' ')
                    .map(|r| r.parse().expect("Unable to parse sub rule numer"))
                    .collect()
            })
            .collect();
        (num, Rule::NoneTerminal(options))
    }
}

fn match_rule<'a>(input: &'a str, rule_num: u32, rules: &HashMap<u32, Rule>) -> (bool, &'a str) {
    let rule = &rules[&rule_num];

    match rule {
        Rule::Terminal(a) => {
            if let Some(b) = input.chars().nth(0) {
                if *a == b {
                    return (true, &input[1..]);
                } else {
                    return (false, "");
                }
            } else {
                return (false, "");
            }
        }
        Rule::NoneTerminal(opts) => {
            for seq in opts {
                let mut rest = input;
                let mut valid = true;
                for r in seq {
                    let (ok, tail) = match_rule(rest, *r, &rules);

                    if !ok {
                        valid = false;
                        break;
                    }
                    rest = tail;

                    // Weird HACK
                    if valid && rest == "" {
                        if *r == 11 {
                            valid = true;
                            break;
                        }
                    }
                }

                if valid {
                    return (true, rest);
                }
            }
            return (false, "");
        }
    };
}

fn main() -> Result<(), Box<dyn Error>> {
    let file = File::open("inputs/day19.txt")?;
    let mut lines = io::BufReader::new(file).lines().map(|l| l.unwrap());

    let mut rules: HashMap<u32, Rule> = HashMap::new();

    while let Some(line) = lines.next() {
        if line == "" {
            break;
        }
        let (num, rule) = read_rule(&line);
        rules.insert(num, rule);
    }

    let mut input_lines: Vec<String> = Vec::new();
    while let Some(line) = lines.next() {
        if line == "" {
            break;
        }
        input_lines.push(line);
    }

    let count1 = input_lines
        .iter()
        .map(|l| {
            if (true, "") == match_rule(l, 0, &rules) {
                1
            } else {
                0
            }
        })
        .fold(0, |x, y| x + y);

    println!("Answer1: {}", count1);

    rules.insert(8, Rule::NoneTerminal(vec![vec![42], vec![42, 8]]));
    rules.insert(11, Rule::NoneTerminal(vec![vec![42, 31], vec![42, 11, 31]]));

    let count2 = input_lines
        .iter()
        .map(|l| {
            if (true, "") == match_rule(l, 0, &rules) {
                1
            } else {
                0
            }
        })
        .fold(0, |x, y| x + y);

    println!("Answer2: {}", count2);

    Ok(())
}

#[cfg(test)]
mod tests {
    use crate::*;

    #[test]
    fn test_read() {
        assert_eq!(read_rule("5 : \"a\""), (5, Rule::Terminal('a')));
        assert_eq!(
            read_rule("3 : 2 4 | 1 2 3 | 5 7"),
            (
                3,
                Rule::NoneTerminal(vec![vec![2, 4], vec![1, 2, 3], vec![5, 7]])
            )
        );
    }

    #[test]
    fn test_example() {
        let rule_str = r#"0: 4 1 5
                    1: 2 3 | 3 2
                    2: 4 4 | 5 5
                    3: 4 5 | 5 4
                    4: "a"
                    5: "b""#;
        let rules: HashMap<u32, Rule> = rule_str.lines().map(|l| read_rule(l)).collect();

        let inputs = r#"
            ababbb
            bababa
            abbbab
            aaabbb
            aaaabbb
        "#;

        let in_lines = inputs.lines().map(|l| l.trim());
        let mut count = 0;
        for line in in_lines {
            let (matched, rest) = match_rule(line, 0, &rules);
            if matched && rest == "" {
                println!("Matched: {}", line);
                count += 1;
            } else {
                println!("Not matched: {} {:?} {:?}", matched, line, rest);
            }
        }

        assert_eq!(count, 2);
    }

    #[test]
    fn test_loops() {
        let rule_str = r#"42: 9 14 | 10 1
                            9: 14 27 | 1 26
                            10: 23 14 | 28 1
                            1: "a"
                            11: 42 31
                            5: 1 14 | 15 1
                            19: 14 1 | 14 14
                            12: 24 14 | 19 1
                            16: 15 1 | 14 14
                            31: 14 17 | 1 13
                            6: 14 14 | 1 14
                            2: 1 24 | 14 4
                            0: 8 11
                            13: 14 3 | 1 12
                            15: 1 | 14
                            17: 14 2 | 1 7
                            23: 25 1 | 22 14
                            28: 16 1
                            4: 1 1
                            20: 14 14 | 1 15
                            3: 5 14 | 16 1
                            27: 1 6 | 14 18
                            14: "b"
                            21: 14 1 | 1 14
                            25: 1 1 | 1 14
                            22: 14 14
                            8: 42
                            26: 14 22 | 1 20
                            18: 15 15
                            7: 14 5 | 1 21
                            24: 14 1"#;
        let mut rules: HashMap<u32, Rule> = rule_str.lines().map(|l| read_rule(l)).collect();
        rules.insert(8, Rule::NoneTerminal(vec![vec![42], vec![42, 8]]));
        rules.insert(11, Rule::NoneTerminal(vec![vec![42, 31], vec![42, 11, 31]]));

        let inputs = r#"
            abbbbbabbbaaaababbaabbbbabababbbabbbbbbabaaaa
            bbabbbbaabaabba
            babbbbaabbbbbabbbbbbaabaaabaaa
            aaabbbbbbaaaabaababaabababbabaaabbababababaaa
            bbbbbbbaaaabbbbaaabbabaaa
            bbbababbbbaaaaaaaabbababaaababaabab
            ababaaaaaabaaab
            ababaaaaabbbaba
            baabbaaaabbaaaababbaababb
            abbbbabbbbaaaababbbbbbaaaababb
            aaaaabbaabaaaaababaa
            aaaabbaaaabbaaa
            aaaabbaabbaaaaaaabbbabbbaaabbaabaaa
            babaaabbbaaabaababbaabababaaab
            aabbbbbaabbbaaaaaabbbbbababaaaaabbaaabba
        "#;

        let in_lines = inputs.lines().map(|l| l.trim());
        let mut count = 0;
        for line in in_lines {
            let (matched, rest) = match_rule(line, 0, &rules);
            if matched && rest == "" {
                println!("Matched: {}", line);
                count += 1;
            } else {
                println!("Not matched: {} {:?} {:?}", matched, line, rest);
            }
        }

        assert_eq!(count, 12);
    }
}