day19.rs

use std::fs;
use std::io;
use std::str::FromStr;

#[derive(Debug, Clone)]
enum Pattern {
    Char {
        c: u8,
    },
    And {
        left: Box<Pattern>,
        right: Box<Pattern>,
    },
    Or {
        left: Box<Pattern>,
        right: Box<Pattern>,
    },
}

impl Pattern {
    fn matches_at(&self, s: &[u8], at: usize) -> Option<usize> {
        match self {
            Pattern::Char { c } => match at < s.len() {
                true => match s[at] == *c {
                    true => Some(at + 1),
                    _ => None,
                },
                _ => None,
            },
            Pattern::And { left, right } => left
                .matches_at(s, at)
                .and_then(|next_at| right.matches_at(s, next_at)),
            Pattern::Or { left, right } => {
                left.matches_at(s, at).or_else(|| right.matches_at(s, at))
            }
        }
    }

    fn matches(&self, s: &str) -> bool {
        let bytes = s.as_bytes();
        self.matches_at(s.as_bytes(), 0) == Some(bytes.len())
    }
}

struct PatternParser {
    patterns: Vec<String>,
}

impl PatternParser {
    fn parse_tokens(&mut self, tokens: Vec<String>) -> Option<Pattern> {
        if tokens.len() == 1 {
            let bytes = tokens[0].as_bytes();
            match bytes[0] {
                b'"' => Some(Pattern::Char { c: bytes[1] }),
                _ => self.parse_at(usize::from_str(&tokens[0]).ok()?),
            }
        } else {
            let mut or = tokens.splitn(2, |s| s == "|");
            match (or.next(), or.next()) {
                (Some(left), Some(right)) => {
                    let left_pat = self.parse_tokens(left.to_vec())?;
                    let right_pat = self.parse_tokens(right.to_vec())?;

                    Some(Pattern::Or {
                        left: Box::new(left_pat),
                        right: Box::new(right_pat),
                    })
                }
                _ => tokens
                    .into_iter()
                    .filter_map(|token| self.parse_tokens([token].to_vec()))
                    .fold(None, |left, right| {
                        left.map(|left| Pattern::And {
                            left: Box::new(left),
                            right: Box::new(right.clone()),
                        })
                        .or(Some(right.clone()))
                    }),
            }
        }
    }

    fn parse_at(&mut self, at: usize) -> Option<Pattern> {
        let tokens: Vec<String> = self
            .patterns
            .get(at)?
            .split_ascii_whitespace()
            .map(|s| s.to_string())
            .collect();

        self.parse_tokens(tokens)
    }

    fn parse(input: &str) -> Option<Pattern> {
        let patterns: Vec<String> = {
            let mut patterns: Vec<(usize, String)> = input
                .lines()
                .map(|line| line.trim())
                .filter_map(|line| {
                    let mut split = line.split(": ");
                    match (split.next(), split.next()) {
                        (Some(index), Some(pattern)) => usize::from_str(index)
                            .ok()
                            .map(|index| (index, pattern.to_string())),
                        _ => None,
                    }
                })
                .collect();

            patterns.sort_by_key(|(index, _)| *index);

            patterns.into_iter().map(|(_, pattern)| pattern).collect()
        };

        let mut parser = PatternParser { patterns: patterns };

        parser.parse_at(0)
    }
}

#[test]
fn test_pattern_match_triple() {
    assert_eq!(
        true,
        PatternParser::parse(
            "
    0: 1
    1: \"a\"
    "
        )
        .unwrap()
        .matches("a")
    );

    assert_eq!(
        true,
        PatternParser::parse(
            "
    0: 1 1
    1: \"a\"
    "
        )
        .unwrap()
        .matches("aa")
    );

    assert_eq!(
        true,
        PatternParser::parse(
            "
    0: 1 1 1
    1: \"a\"
    "
        )
        .unwrap()
        .matches("aaa")
    );

    let a_or_aa = PatternParser::parse(
        "
    0: 1 1 | 1
    1: \"a\"
    ",
    )
    .unwrap();

    assert_eq!(true, a_or_aa.matches("a"));
    assert_eq!(true, a_or_aa.matches("aa"));

    let a_or_aa_or_aaa = PatternParser::parse(
        "
    0: 1 1 1 | 1 1 | 1
    1: \"a\"
    ",
    )
    .unwrap();

    assert_eq!(true, a_or_aa_or_aaa.matches("a"));
    assert_eq!(true, a_or_aa_or_aaa.matches("aa"));
    assert_eq!(true, a_or_aa_or_aaa.matches("aaa"));
}

#[test]
fn test_pattern_match() {
    let pattern = PatternParser::parse(
        "
        0: 4 1 5
        1: 2 3 | 3 2
        2: 4 4 | 5 5
        3: 4 5 | 5 4
        4: \"a\"
        5: \"b\"
            ",
    )
    .unwrap();

    assert_eq!(true, pattern.matches("ababbb"));
    assert_eq!(true, pattern.matches("abbbab"));
    assert_eq!(false, pattern.matches("bababa"));
    assert_eq!(false, pattern.matches("aaabbb"));
    assert_eq!(false, pattern.matches("aaaabbb"));

    assert_eq!(
        true,
        PatternParser::parse(
            "
    0: 1 2
    1: \"a\"
    2: \"b\"
    "
        )
        .unwrap()
        .matches("ab")
    );

    let ab_or_bb = PatternParser::parse(
        "
    0: 3 | 4
    3: 1 2
    4: 2 2
    1: \"a\"
    2: \"b\"
    ",
    )
    .unwrap();

    assert_eq!(true, ab_or_bb.matches("bb"));

    assert_eq!(
        true,
        PatternParser::parse(
            "
    0: 3 | 4
    3: 1 2
    4: 2 2
    1: \"a\"
    2: \"b\"
    "
        )
        .unwrap()
        .matches("ab")
    );
}

#[allow(dead_code)]
pub fn solve_p1(input: &str) -> io::Result<usize> {
    let content = fs::read_to_string(input)?;
    let pattern = PatternParser::parse(&content).unwrap();
    Ok(content
        .lines()
        .filter(|line| pattern.matches(&line))
        .count())
}
/// replace 11 with
/// 11: 42 42 42 42 31 31 31 31 | 42 42 42 42 31 31 31 | 42 42 42 31 31 31 | 42 42 42 42 31 31 | 42 42 42 31 31 | 42 42 31 31 | 42 42 42 42 42 31 | 42 42 42 42 31 | 42 42 42 31 | 42 42 31 | 42 31
#[allow(dead_code)]
pub fn solve_p2(input: &str) -> io::Result<usize> {
    solve_p1(input)
}