Skip to content

Instantly share code, notes, and snippets.

@whiter4bbit

whiter4bbit/day19.rs

Last active December 19, 2020 18:49
Show Gist options
  • Save whiter4bbit/590abb1bb6f7a8ea89f12f96c61e88f3 to your computer and use it in GitHub Desktop.
Save whiter4bbit/590abb1bb6f7a8ea89f12f96c61e88f3 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment