day19.rs

use std::collections::hash_map::*;

fn solve(crule: &RuleCont, rules: &HashMap<usize, Rule>, s: &str, offs: usize) -> (usize, bool)
{
    let mut moffs = offs;
    match crule
    {
        RuleCont::Seq(irules) => {
            let mut valid = true;
            let remoffs = moffs;
            if let (RuleCont::Num(42), Some(RuleCont::Num(8))) = (irules.get(0).unwrap(), irules.get(1))
            {
                let (newpos, isvalid1) = solve(&RuleCont::Num(42), rules, s, moffs);
                let (_, isvalid) = solve(&RuleCont::Num(11), rules, s, newpos);
                if isvalid && isvalid1
                {
                    return (newpos, true)
                }
            }
            for rule in irules
            {
                let (newoffs, isvalid) = solve(&rule, rules, s, moffs);
                moffs = newoffs;
                if !isvalid
                {
                    moffs = remoffs;
                    valid = false;
                    break;
                }
            }
            return (moffs, valid);
        }
        RuleCont::Either(vs) => {
            let mut valid = false;
            for rule in vs
            {
                
                let (newoffs, isvalid) = solve(&rule, rules, s, moffs);
                if isvalid
                {
                    moffs = newoffs;
                    valid = true;
                    break;
                }
            }
            return (moffs, valid)
        }
        RuleCont::Char(i) => {
            let v = s.chars().nth(moffs);
            if let Some(chr) = v
            {
                if chr == *i
                {
                    return (moffs+1, true);
                }
            }
            return (moffs, false);
        }
        RuleCont::Num(i) => {
            return solve(&rules.get(i).unwrap().rule, rules, s, moffs)
        }
    }
}

fn matches(parsed: &HashMap<usize, Rule>, input: &str) -> bool
{
    let solved = solve(&parsed.get(&0).unwrap().rule, &parsed, input, 0); 
    solved.1 && solved.0 == input.len()
}

pub fn solve_day19()
{
    let input = std::fs::read_to_string("./day19.txt").expect("Please put your ./day19.txt near your executable");
    let split = input.split("\n\n").collect::<Vec<&str>>();
    let lexed = lex(split.get(0).unwrap()).unwrap();
    let inputs = split.get(1).unwrap().split("\n");
    let mut parsed = parse(&lexed).unwrap();

    let v = std::time::SystemTime::now();
    let mut hm = HashMap::new();
    for i in parsed
    {
        hm.insert(i.label, i);
    }
    let mut valid = 0;
    for inp in inputs
    {
        if inp == "" {continue}
        let is_valid = matches(&hm, inp);
        valid += if is_valid {1} else {0};
    }
    println!("{:?}ms {}", (std::time::SystemTime::now() - v.elapsed().unwrap()).elapsed().unwrap().as_millis(), valid);
}



#[derive(Debug)]
enum Token 
{
    Num(usize),
    Alt,
    Colon,
    Next,
    Str(String)
}

#[derive(Debug)]
enum RuleCont
{
    Seq(Vec<RuleCont>),
    Either(Vec<RuleCont>),
    Char(char),
    Num(usize)
}

#[derive(Debug)]
struct Rule
{
    label: usize,
    rule: RuleCont
}

fn parse(input: &[Token]) -> Result<Vec<Rule>, String>
{
    let mut res = vec![];   
    let mut pos = 0;
    while pos < input.len()
    {
        let (rule, newpos) = parse_rule(input, pos)?;
        res.push(rule);
        pos = newpos;
    }

    Ok(res)
}

fn parse_rule(input: &[Token], pos: usize) -> Result<(Rule, usize), String>
{
    let mut mpos = pos;
    let label;
    if let Some(Token::Num(num)) = input.get(mpos)
    {
        label = num;
    }
    else
    {
        return Err(format!("Expected num got {:?} pos {}", input.get(mpos), mpos));
    }
    mpos += 2;
    
    let (rule, newpos) = parse_tl(input, mpos)?;
    Ok((Rule {label: *label, rule}, newpos+1))
}

fn parse_tl(input: &[Token], pos: usize) -> Result<(RuleCont, usize), String>
{
    let mut mpos = pos;
    let mut res = vec![];
    loop
    {
        let (rules, newpos) = parse_seq(input, mpos)?;
        mpos = newpos;
        res.push(rules);
        if let Some(Token::Alt) = input.get(mpos) {
            mpos += 1;
        } else {break};
    }
    return Ok((RuleCont::Either(res), mpos))
}

fn parse_seq(input: &[Token], pos: usize) -> Result<(RuleCont, usize), String>
{
    let mut mpos = pos;
    let mut res = vec![];
    loop {
        match input.get(mpos)
        {
            Some(x) => match x {
                Token::Str(s) => {
                    res.push(RuleCont::Char(s.chars().nth(0).unwrap()))
                }
                Token::Num(v) => {
                    res.push(RuleCont::Num(*v))
                } 
                _ => {
                    return Ok((RuleCont::Seq(res), mpos));
                }
            }
            _ => return Ok((RuleCont::Seq(res), mpos))
        }
        mpos += 1;
    }
}

fn lex(input: &str) -> Result<Vec<Token>, String>
{
    let mut pos = 0;
    let mut res = vec![];
    while pos < input.len()
    {
        match input.get(pos..pos+1)
        {
            Some(x) => match x {
                "|" => {
                    res.push(Token::Alt)
                }
                ":" => {
                    res.push(Token::Colon)
                }
                "\n" => {
                    res.push(Token::Next)
                }
                " " | "\t" => {
                }
                "\"" => {
                    pos += 1;
                    let mut stret = String::from("");
                    'r: loop 
                    {
                        match input.get(pos..pos+1)
                        {
                            None | Some("\"") => break 'r,
                            Some(x) => {
                                stret += x;
                            }
                        }
                        pos += 1;
                    }
                    pos += 1;
                    res.push(Token::Str(stret));
                    continue;
                }
                "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" => {
                    let mut stret = String::from("");
                    'r: loop 
                    {
                        match input.get(pos..pos+1)
                        {
                            Some(x) => match x {
                                "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" => {
                                    stret += x;
                                }
                                _ => break 'r
                            },
                            _ => break 'r
                        }
                        pos += 1;
                    }
                    res.push(Token::Num(stret.parse().unwrap()));
                    continue;
                }
                y => {
                    return Err(format!("Unknown symbol {} at {}", y, pos));
                }
            },
            None => {
                return Err(format!("Unexpected EOF at position {}", pos));
            }
        }
        pos += 1;
    }
    Ok(res)
}