497 lines
16 KiB
Rust
497 lines
16 KiB
Rust
use std::collections::HashMap;
|
|
use std::io::BufRead;
|
|
|
|
#[derive(Clone, Eq, PartialEq, Debug, Hash)]
|
|
struct State {
|
|
ch: Option<char>,
|
|
next: Option<Vec<Box<State>>>
|
|
}
|
|
|
|
#[derive(Clone, Eq, PartialEq, Debug, Hash)]
|
|
enum TransitionAction {
|
|
Push(char),
|
|
Pop(char),
|
|
None,
|
|
}
|
|
|
|
#[derive(Debug)]
|
|
enum TransitionError {
|
|
Mismatch,
|
|
EmptyStack,
|
|
}
|
|
|
|
#[derive(Clone, Eq, PartialEq, Debug, Hash)]
|
|
struct Transition {
|
|
next: u32,
|
|
action: TransitionAction
|
|
}
|
|
|
|
impl Transition {
|
|
fn build_none(next: u32) -> Transition {
|
|
Transition {
|
|
next,
|
|
action: TransitionAction::None,
|
|
}
|
|
}
|
|
|
|
fn build_push(next: u32, ch: char) -> Transition {
|
|
Transition {
|
|
next,
|
|
action: TransitionAction::Push(ch),
|
|
}
|
|
}
|
|
|
|
fn build_pop(next: u32, ch: char) -> Transition {
|
|
Transition {
|
|
next,
|
|
action: TransitionAction::Pop(ch),
|
|
}
|
|
}
|
|
|
|
fn execute(&self, stack: &Vec<char>) -> Result<Vec<char>, TransitionError> {
|
|
let mut stack = stack.clone();
|
|
match self.action {
|
|
TransitionAction::None => Ok(stack),
|
|
TransitionAction::Push(ch) => {
|
|
stack.push(ch);
|
|
Ok(stack)
|
|
}
|
|
TransitionAction::Pop(ch) => if let Some(stack_ch) = stack.pop() {
|
|
if stack_ch == ch {
|
|
Ok(stack)
|
|
} else {
|
|
Err(TransitionError::Mismatch)
|
|
}
|
|
} else {
|
|
Err(TransitionError::EmptyStack)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
#[derive(Clone, Eq, PartialEq, Debug)]
|
|
struct Automata {
|
|
transitions: HashMap<(u32, Option<char>), Vec<Transition>>,
|
|
}
|
|
|
|
impl Automata {
|
|
fn from_str(input: &str) -> Automata {
|
|
StateParser::new(input).parse_id(0)
|
|
}
|
|
|
|
fn append(&mut self, automata: Automata) {
|
|
let leaves: Vec<_> = self.leaves();
|
|
|
|
if leaves.len() == 0 {
|
|
self.transitions = automata.transitions;
|
|
} else if leaves.len() == 1 {
|
|
self.insert(&leaves, &automata);
|
|
} else {
|
|
let mut out_state = Automata::new();
|
|
let out_id = self.next_insert_id();
|
|
out_state.transitions.insert((0, None), Vec::new());
|
|
self.insert(&leaves, &out_state);
|
|
self.insert(&[(out_id, None)], &automata);
|
|
}
|
|
}
|
|
|
|
fn leaves(&self) -> Vec<(u32, Option<char>)> {
|
|
self.transitions.iter()
|
|
.filter(|(_state, next)| next.len() == 0).map(|(state, _next)| state)
|
|
.cloned()
|
|
.collect()
|
|
}
|
|
|
|
fn insert(&mut self, leaves: &[(u32, Option<char>)], automata: &Automata) {
|
|
let id = self.next_insert_id();
|
|
for leaf in leaves {
|
|
//println!("{:?} -> id = {}", self, id);
|
|
if let Some(ids) = self.transitions.get_mut(leaf) {
|
|
ids.push(Transition::build_none(id))
|
|
} else {
|
|
self.transitions.insert(leaf.clone(), vec![Transition::build_none(id)]);
|
|
}
|
|
}
|
|
let mut shifted = automata.shift(id);
|
|
self.transitions.extend(shifted.transitions.drain());
|
|
}
|
|
|
|
fn shift(&self, offset: u32) -> Automata {
|
|
let new_transitions = self.transitions.iter()
|
|
.map(|((state_id, ch), next)|
|
|
(
|
|
// key
|
|
(state_id + offset, *ch),
|
|
// value
|
|
next.iter().map(|next_id| Transition {
|
|
next: if next_id.next == u32::MAX { next_id.next } else { next_id.next + offset },
|
|
action: next_id.action.clone()
|
|
}).collect()
|
|
)
|
|
).collect();
|
|
|
|
Automata {
|
|
transitions: new_transitions,
|
|
}
|
|
}
|
|
|
|
fn next_insert_id(&self) -> u32 {
|
|
self.transitions.keys().map(|(id, _)| *id).max().map(|id| id + 1).unwrap_or(0)
|
|
}
|
|
|
|
fn new() -> Automata {
|
|
Automata {
|
|
transitions: HashMap::new(),
|
|
}
|
|
}
|
|
|
|
fn root() -> Automata {
|
|
let mut automata = Automata::new();
|
|
automata.transitions.insert((0, None), Vec::new());
|
|
automata
|
|
}
|
|
|
|
|
|
#[allow(dead_code)]
|
|
fn simplify(&mut self, state: &(u32, Option<char>)) {
|
|
let mut cache = self.compute_transition_cache();
|
|
//println!("{:?}", self);
|
|
//println!("{:?}", cache);
|
|
self.simplify_with_cache(state, &mut cache);
|
|
}
|
|
|
|
|
|
#[allow(dead_code)]
|
|
fn compute_transition_cache(&self) -> HashMap<u32, Vec<Option<char>>> {
|
|
let mut cache: HashMap<u32, Vec<Option<char>>> = HashMap::new();
|
|
for (node, ch) in self.transitions.keys() {
|
|
let chars = cache.entry(*node).or_default();
|
|
chars.push(*ch);
|
|
}
|
|
cache
|
|
}
|
|
|
|
// Does not work with loops so it's disabled
|
|
#[allow(dead_code)]
|
|
fn simplify_with_cache(&mut self, (node, _): &(u32, Option<char>), cache: &mut HashMap<u32, Vec<Option<char>>>) {
|
|
//println!("{:?}", self);
|
|
//println!("current node {}", node);
|
|
let chs: Vec<Option<char>> = cache[&node].iter().cloned().collect();
|
|
for ch in chs {
|
|
//println!("cache {:?}", cache);
|
|
//println!("{:?}", (*node, ch));
|
|
let transitions: Vec<_> = self.transitions[&(*node, ch)].iter().cloned()
|
|
.flat_map(|id|
|
|
cache[&id.next].iter().cloned()
|
|
.map(move |ch| (id.next, ch))
|
|
).collect();
|
|
|
|
if ch.is_some() {
|
|
for transition in transitions {
|
|
if &transition.0 == node {
|
|
continue;
|
|
}
|
|
self.simplify_with_cache(&transition, cache);
|
|
}
|
|
} else {
|
|
cache.get_mut(node).unwrap().clear();
|
|
self.transitions.remove(&(*node, ch));
|
|
for (next_id, next_ch) in transitions {
|
|
if &next_id == node {
|
|
continue;
|
|
}
|
|
let next_next = self.transitions.remove(&(next_id, next_ch)).unwrap();
|
|
cache.remove(&next_id);
|
|
let next = self.transitions.entry((*node, next_ch)).or_default();
|
|
next.extend(next_next);
|
|
cache.get_mut(node).unwrap().push(next_ch);
|
|
self.simplify_with_cache(&(*node, next_ch), cache);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
fn validate(&self, state: u32, s: &str, stack: Vec<char>) -> bool {
|
|
let current_char = s.chars().next();
|
|
let remainder = if current_char.is_some() {
|
|
&s[1..]
|
|
} else {
|
|
s
|
|
};
|
|
//println!("{:?} / {:?} / {:?} / {:?}", state, current_char, s, stack);
|
|
|
|
if let Some(next_states) = self.transitions.get(&(state, current_char)) {
|
|
if next_states.len() == 0 {
|
|
return remainder == "" && stack.is_empty();
|
|
} else {
|
|
//println!("continue {:?}", next_states);
|
|
next_states.iter().any(|next_state| {
|
|
if let Ok(new_stack) = next_state.execute(&stack) {
|
|
self.validate(next_state.next, remainder, new_stack)
|
|
} else {
|
|
false
|
|
}
|
|
})
|
|
}
|
|
} else if let Some(next_states) = self.transitions.get(&(state, None)) {
|
|
if next_states.len() == 0 {
|
|
return s == "" && stack.is_empty();
|
|
} else {
|
|
//println!("skip {:?}", next_states);
|
|
next_states.iter().any(|next_state| {
|
|
if let Ok(new_stack) = next_state.execute(&stack) {
|
|
self.validate(next_state.next, s, new_stack)
|
|
} else {
|
|
false
|
|
}
|
|
})
|
|
}
|
|
}else {
|
|
false
|
|
}
|
|
|
|
}
|
|
}
|
|
|
|
struct StateParser {
|
|
rules: HashMap<u32, String>,
|
|
cache: HashMap<u32, Automata>,
|
|
}
|
|
|
|
impl StateParser {
|
|
fn new(input: &str) -> StateParser {
|
|
let rules = input.lines().map(|l| {
|
|
let splited: Vec<_> = l.split(": ").collect();
|
|
(splited[0].parse().unwrap(), String::from(splited[1]))
|
|
}).collect();
|
|
StateParser {
|
|
rules,
|
|
cache: HashMap::new(),
|
|
}
|
|
}
|
|
|
|
fn parse_id(&mut self, id: u32) -> Automata {
|
|
if self.cache.contains_key(&id) {
|
|
self.cache[&id].clone()
|
|
} else {
|
|
let rule = self.rules[&id].clone();
|
|
let state = self.parse_str(id, &rule);
|
|
self.cache.insert(id, state.clone());
|
|
state
|
|
}
|
|
}
|
|
|
|
fn parse_str(&mut self, id: u32, s: &str) -> Automata {
|
|
//println!("{} {}", id, s);
|
|
//println!("{}", s);
|
|
if s.starts_with("\"") {
|
|
let mut transitions = HashMap::new();
|
|
transitions.insert((0, Some(s.chars().nth(1).unwrap())), Vec::new());
|
|
//println!("{:?}", transitions);
|
|
Automata {
|
|
transitions,
|
|
}
|
|
} else {
|
|
let choices: Vec<_> = s.split(" | ").collect();
|
|
if choices.len() == 1 {
|
|
let chain: Vec<_> = choices[0].split(' ').map(|id| id.parse::<u32>().unwrap()).collect();
|
|
let mut automata = Automata::new();
|
|
//println!("LOOOP, {:?}", chain);
|
|
|
|
if chain.len() == 3 && chain[1] == id {
|
|
// loop me boi again, formally
|
|
// S -> aSb
|
|
for (index, next_id) in chain.iter().enumerate().step_by(2) {
|
|
let mut sub_automata = Automata::root();
|
|
let mut sub_content = self.parse_id(*next_id);
|
|
//println!("SUB CONTENT {:?}\n", sub_content);
|
|
//println!("SUB LOOOP {:?}\n", sub_automata);
|
|
|
|
sub_content.append(Automata::root());
|
|
let out_id = sub_content.next_insert_id();
|
|
//println!("SUB CONTENT {:?}\n", sub_content);
|
|
for leaf in sub_content.leaves() {
|
|
sub_content.transitions.get_mut(&leaf).unwrap().push(if index == 0 {
|
|
Transition::build_push(0, 'x')
|
|
} else {
|
|
Transition::build_pop(0, 'x')
|
|
});
|
|
sub_content.transitions.get_mut(&leaf).unwrap().push(Transition::build_none(out_id));
|
|
}
|
|
|
|
sub_content.transitions.insert((out_id, None), Vec::new());
|
|
sub_automata.insert(&[(0, None)], &sub_content);
|
|
|
|
sub_automata.transitions.get_mut(&(0, None)).unwrap()[0].action = if index == 0 {
|
|
TransitionAction::Push('x')
|
|
} else {
|
|
TransitionAction::Pop('x')
|
|
};
|
|
//println!("SUB LOOOP {:?}\n", sub_automata);
|
|
//println!("SUB LOOOP EXPENDED AUTOMATA BEFORE {:?}\n\n", automata);
|
|
automata.append(sub_automata);
|
|
//println!("SUB LOOOP EXPENDED AUTOMATA {:?}\n\n", automata);
|
|
}
|
|
} else {
|
|
for next_id in &chain {
|
|
//println!("chain, {:?}", automata);
|
|
|
|
// loop me boi
|
|
// S -> aS
|
|
if &id == next_id {
|
|
for state in automata.leaves() {
|
|
automata.transitions.get_mut(&state).unwrap().push(Transition::build_none(u32::MAX));
|
|
}
|
|
} else {
|
|
let item = self.parse_id(*next_id);
|
|
automata.append(item);
|
|
}
|
|
}
|
|
}
|
|
automata
|
|
} else {
|
|
let it = choices.iter().map(|&choice| self.parse_str(id, &choice));
|
|
let mut automata = Automata::root();
|
|
for item in it {
|
|
automata.insert(&[(0, None)], &item)
|
|
}
|
|
for state in automata.transitions.keys().cloned().collect::<Vec<_>>() {
|
|
for next in automata.transitions.get_mut(&state).unwrap().iter_mut() {
|
|
if next.next == u32::MAX {
|
|
next.next = 0;
|
|
}
|
|
}
|
|
}
|
|
// broken with loops and stuff
|
|
//automata.simplify(&(0, None));
|
|
automata
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
pub fn part1<F: BufRead> (mut input: F) {
|
|
let mut buffer = String::new();
|
|
input.read_to_string(&mut buffer).unwrap();
|
|
let input_parts: Vec<&str> = buffer.split("\n\n").collect();
|
|
let automata = Automata::from_str(input_parts[0]);
|
|
println!("parsed");
|
|
let valid_count = input_parts[1].lines().filter(|line| automata.validate(0, line, Vec::new())).count();
|
|
println!("{}", valid_count);
|
|
}
|
|
|
|
|
|
pub fn part2<F: BufRead> (mut input: F) {
|
|
let mut buffer = String::new();
|
|
input.read_to_string(&mut buffer).unwrap();
|
|
let input_parts: Vec<&str> = buffer.split("\n\n").collect();
|
|
let mut parser = StateParser::new(input_parts[0]);
|
|
parser.rules.insert(8, "42 | 42 8".into());
|
|
parser.rules.insert(11, "42 31 | 42 11 31".into());
|
|
let automata = parser.parse_id(0);
|
|
println!("parsed");
|
|
let valid_count = input_parts[1].lines().filter(|line| automata.validate(0, line, Vec::new())).count();
|
|
println!("{}", valid_count);
|
|
}
|
|
|
|
|
|
|
|
#[cfg(test)]
|
|
mod test {
|
|
use super::*;
|
|
|
|
#[test]
|
|
pub fn test_parse_chain() {
|
|
let input = r#"0: 1 3 | 2
|
|
3: 1 | 2
|
|
1: "a"
|
|
2: "b""#;
|
|
let automata = Automata::from_str(input);
|
|
println!("{:?}", automata);
|
|
}
|
|
|
|
#[test]
|
|
pub fn test_parse_loop() {
|
|
let input = r#"0: 1 | 1 0
|
|
1: "a""#;
|
|
let automata = Automata::from_str(input);
|
|
println!("{:?}", automata);
|
|
}
|
|
|
|
|
|
#[test]
|
|
pub fn test_parse_loop_formal() {
|
|
let input = r#"0: 1 2 | 1 0 2
|
|
1: "a"
|
|
2: "b""#;
|
|
let automata = Automata::from_str(input);
|
|
println!("{:?}", automata);
|
|
}
|
|
#[test]
|
|
pub fn test_loop_formal() {
|
|
let input = r#"0: 1 2 | 1 0 2
|
|
1: "a"
|
|
2: "b""#;
|
|
|
|
let test_cases = &[
|
|
("aab", false),
|
|
("abb", false),
|
|
("aaabbb", true),
|
|
("ab", true),
|
|
];
|
|
let automata = Automata::from_str(input);
|
|
//println!("{:?}", automata);
|
|
for (input, expected) in test_cases {
|
|
println!("{}", input);
|
|
assert_eq!(*expected, automata.validate(0, input, Vec::new()));
|
|
}
|
|
}
|
|
|
|
|
|
#[test]
|
|
pub fn test_validate() {
|
|
let input = r#"0: 4 1 5
|
|
1: 2 3 | 3 2
|
|
2: 4 4 | 5 5
|
|
3: 4 5 | 5 4
|
|
4: "a"
|
|
5: "b""#;
|
|
|
|
//println!("{:?}", StateParser::new(input).parse_id(0))
|
|
let test_cases = &[
|
|
("ababbb", true),
|
|
("abbbab", true),
|
|
("aaabbb", false),
|
|
("bababa", false),
|
|
("aaaabbb", false),
|
|
];
|
|
let automata = Automata::from_str(input);
|
|
//println!("{:?}", automata);
|
|
for (input, expected) in test_cases {
|
|
println!("{}", input);
|
|
assert_eq!(*expected, automata.validate(0, input, Vec::new()));
|
|
}
|
|
}
|
|
|
|
#[test]
|
|
pub fn test_loop() {
|
|
let input = r#"0: 1 3
|
|
1: 2 | 2 1
|
|
2: "a"
|
|
3: "b""#;
|
|
let test_cases = &[
|
|
("ab", true),
|
|
("aab", true),
|
|
("aaaab", true),
|
|
];
|
|
let automata = Automata::from_str(input);
|
|
println!("{:?}", automata);
|
|
for (input, expected) in test_cases {
|
|
println!("{}", input);
|
|
assert_eq!(*expected, automata.validate(0, input, Vec::new()));
|
|
}
|
|
}
|
|
}
|