Last active
December 19, 2020 19:09
-
-
Save whiter4bbit/a635a3140932cf2cc92c2ba00c448828 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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>, | |
cache: Vec<Option<Pattern>>, | |
} | |
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> { | |
match self.cache.get(at) { | |
Some(Some(pattern)) => Some(pattern.clone()), | |
Some(None) => { | |
let tokens: Vec<String> = self | |
.patterns | |
.get(at)? | |
.split_ascii_whitespace() | |
.map(|s| s.to_string()) | |
.collect(); | |
self.cache[at] = self.parse_tokens(tokens); | |
self.cache[at].clone() | |
} | |
_ => None, | |
} | |
} | |
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 cache: Vec<Option<Pattern>> = (0..patterns.len()).into_iter().map(|_| None).collect(); | |
PatternParser { | |
patterns: patterns, | |
cache: cache, | |
} | |
.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) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment