19

1 files changed, 127 insertions, 0 deletions

diff --git a/19/src/main.rs b/19/src/main.rs
new file mode 100644
index 0000000..5bbdcc6
--- /dev/null
+++ b/19/src/main.rs
@@ -0,0 +1,127 @@
+use advent_lib::prelude::*;
+
+use std::collections::BTreeMap;
+//use std::convert::TryFrom;
+
+#[derive(Clone,Debug)]
+enum Rule {
+  Alternatives(Vec<Vec<i64>>),
+  Character(char),
+}
+
+
+fn main() -> Result<()> {
+  let mut args = std::env::args();
+  if args.len() != 2 {
+    eprintln!("Usage: advent input");
+  }
+  let _ = args.next();
+  let filename = args.next().unwrap();
+
+  let input = advent_lib::read_lines_file(&filename)?;
+  let input = advent_lib::group_lines_by_blanks(input);
+
+  let mut rules: BTreeMap<i64,Rule> = BTreeMap::new();
+  for line in &input[0] {
+    let colon_point = line.find(':').unwrap();
+    let (rule_number, rest) = line.split_at(colon_point);
+    let rule_number = rule_number.parse::<i64>().unwrap();
+    let (_, rest) = rest.split_at(2);
+    let words: Vec<&str> = rest.split(' ').collect();
+
+    let mut chars = words[0].chars();
+    if words.len() == 1 && chars.next() == Some('"') {
+      let c = chars.next().unwrap();
+
+      rules.insert(rule_number, Rule::Character(c));
+    } else {
+      let alternatives_inputs = words.split(|word| *word == "|");
+
+      let mut alternatives: Vec<Vec<i64>> = Vec::new();
+      for alternative_words in alternatives_inputs {
+        let mut alternative: Vec<i64> = Vec::new();
+        for word in alternative_words {
+          alternative.push(word.parse::<i64>().unwrap());
+        }
+        alternatives.push(alternative);
+      }
+
+      rules.insert(rule_number, Rule::Alternatives(alternatives));
+    }
+  }
+
+  let mut match_count = 0;
+  for line in &input[1] {
+    if is_match(&rules, 0, line) {
+      match_count += 1;
+    }
+  }
+
+  println!("{:?}", match_count);
+
+  rules.insert(8, Rule::Alternatives(vec![vec![42], vec![42, 8]]));
+  rules.insert(11, Rule::Alternatives(vec![vec![42, 31], vec![42, 11, 31]]));
+
+  let mut match_count = 0;
+  for line in &input[1] {
+    if is_match(&rules, 0, line) {
+      match_count += 1;
+    }
+  }
+
+  println!("{:?}", match_count);
+
+  Ok(())
+}
+
+
+fn is_match(rules: &BTreeMap<i64,Rule>, root_rule: i64, input: &str) -> bool {
+  let match_results = is_match_helper(rules, root_rule, input);
+  for rest in match_results {
+    if rest.len() == 0 {
+      return true;
+    }
+  }
+  false
+}
+
+fn is_match_helper<'a>(rules: &BTreeMap<i64,Rule>, root_rule: i64, input: &'a str)
+  -> Vec<&'a str>
+{
+  let mut results = Vec::new();
+
+  match rules.get(&root_rule).unwrap() {
+    Rule::Alternatives(alternatives) => {
+      for alternative in alternatives {
+        let mut possible_rests = Vec::new();
+        possible_rests.push(input);
+
+        for sub_rule in alternative {
+          let mut new_possible_rests = Vec::new();
+
+          for rest in possible_rests {
+            let sub_matches = is_match_helper(rules, *sub_rule, rest);
+            for new_rest in sub_matches {
+              new_possible_rests.push(new_rest);
+            }
+          }
+
+          possible_rests = new_possible_rests;
+        }
+
+        for rest in possible_rests {
+          results.push(rest);
+        }
+      }
+    },
+    Rule::Character(character) => {
+      if input.len() >= 1 && input.chars().next() == Some(*character) {
+        let (_, rest) = input.split_at(1);
+        results.push(rest);
+      }
+    },
+  }
+
+  results
+}
+