Improve day12 and solve day12.2

1 files changed, 85 insertions, 49 deletions

diff --git a/day12/src/main.rs b/day12/src/main.rs
index 6b421e4..001c6f9 100644
--- a/day12/src/main.rs
+++ b/day12/src/main.rs
@@ -5,29 +5,26 @@ use std::fs::File;
 use std::process;
 use std::collections::HashMap;
 
-type State = Vec<(i64, char)>;
+type State = HashMap<i64, char>;
 type RuleKey = (char, char, char, char, char);
 type Rules = HashMap<RuleKey, char>;
 
-static ITERATIONS: usize = 20;
+static ITERATIONS: usize = 150;
 
-fn parse_initial_state(line: &String) -> State {
+fn parse_initial_state(line: &String) -> (State, i64, i64) {
   let initial: Vec<char> = line[15..].chars().collect();
-  let mut slice: State = Vec::new();
-  for i in -(ITERATIONS as i64) - 2..0 {
-    slice.push((i, '.'));
-  }
-  for (i, ch) in initial.iter().enumerate() {
-    slice.push((i as i64, *ch));
-  }
-  for i in initial.len()..initial.len() + ITERATIONS + 2 {
-    slice.push((i as i64, '.'));
-  }
-  for (i, _) in &slice {
-    print!("{} ", i);
+  let mut state: State = State::new();
+
+  for (i, &ch) in initial.iter().enumerate() {
+    state.insert(i as i64, ch);
   }
-  print!("\n");
-  slice
+
+  let c = initial.len() as i64;
+  state.insert(-1, '.');
+  state.insert(-2, '.');
+  state.insert(c, '.');
+  state.insert(c + 1, '.');
+  (state, 0, c + 1)
 }
 
 fn parse_rule(rules: &mut Rules, line: &String) {
@@ -38,6 +35,36 @@ fn parse_rule(rules: &mut Rules, line: &String) {
   rules.insert(rule_key, res);
 }
 
+fn eval_rules(state: &State, rules: &Rules, i: i64) -> char {
+  let prev2 = if state.contains_key(&(i - 2)) { state[&(i - 2)] } else { '.' };
+  let prev1 = if state.contains_key(&(i - 1)) { state[&(i - 1)] } else { '.' };
+  let cur = if state.contains_key(&i) { state[&i] } else { '.' };
+  let next1 = if state.contains_key(&(i + 1)) { state[&(i + 1)] } else { '.' };
+  let next2 = if state.contains_key(&(i + 2)) { state[&(i + 2)] } else { '.' };
+
+  rules[&(prev2, prev1, cur, next1, next2)]
+}
+
+fn draw_state(state: &State, iteration: usize) {
+  let mut keys: Vec<i64> = state.keys().map(|&k| k).collect();
+  keys.sort();
+  print!("{}: ", iteration);
+  for k in &keys {
+    print!("{} ", state[k]);
+  }
+  print!("\n");
+}
+
+fn sum_state(state: &State) -> i64 {
+  let mut total = 0;
+  for (i, &ch) in state {
+    if ch == '#' {
+      total += i;
+    }
+  }
+  total
+}
+
 fn main() {
   let args: Vec<String> = env::args().collect();
   if args.len() != 2 {
@@ -59,53 +86,62 @@ fn main() {
     .map(|line| line.expect("Could not parse line."))
     .collect();
 
-  let mut initial_state: State = Vec::new();
+  let mut initial_state: State = State::new();
+  let (mut i1, mut i2): (i64, i64) = (0, 0);
   let mut rules: Rules = HashMap::new();
   for (i, line) in lines.iter().enumerate() {
     match i {
-      0 => { initial_state = parse_initial_state(&line); }
+      0 => {
+        let tuple = parse_initial_state(&line);
+        initial_state = tuple.0;
+        i1 = tuple.1;
+        i2 = tuple.2;
+      }
       1 => { }
       _ => { parse_rule(&mut rules, &line); }
     }
   }
   assert_ne!(initial_state.len(), 0);
 
-  let state_len = initial_state.len();
-  let mut states: Vec<State> = vec![initial_state];
+  let mut prev_state = initial_state;
+  let mut prev_sum = 0;
+  // draw_state(&prev_state, 0);
   for iteration in 0..ITERATIONS {
-    let mut new_state: State = vec![(-999, '.'); state_len];
-    {
-      let prev_state = &states[states.len() - 1];
-      for (i, _) in prev_state.iter().enumerate() {
-        if i < 2 || i >= state_len - 2 { continue; }
-        let rule_key = (prev_state[i-2].1, prev_state[i-1].1, prev_state[i].1, prev_state[i+1].1, prev_state[i+2].1);
-        let value = rules[&rule_key];
-        new_state[i] = (prev_state[i].0, value);
-      }
+    let mut new_state = prev_state.clone();
+    if prev_state[&(i1 + 1)] == '#' {
+      new_state.insert(i1 - 1, '.');
+      new_state.insert(i1 - 2, '.');
+      i1 -= 2;
     }
-    if iteration % 1000 == 0 {
-      println!("Iteration: {}", iteration);
+    if prev_state[&(i2 - 1)] == '#' {
+      new_state.insert(i2 + 1, '.');
+      new_state.insert(i2 + 2, '.');
+      i2 += 2;
     }
-    states.push(new_state);
-  }
 
-  for (i, state) in states.iter().enumerate() {
-    print!("{}: ", i);
-    for tupl in state {
-      let ch = tupl.1;
-      print!("{}", ch);
+    let keys: Vec<i64> = new_state.keys().map(|&k| k).collect();
+    for key in keys {
+      let val = eval_rules(&prev_state, &rules, key);
+      new_state.insert(key, val);
     }
-    print!("\n");
-  }
 
-  let mut total = 0;
-  let last_i = states.len() - 1;
-  let last_state = &states[last_i];
-  for (_, &tupl) in last_state.iter().enumerate() {
-    let (i, ch) = tupl;
-    if ch == '#' {
-      total += i;
-    }
+    // if iteration % 1000 == 0 {
+    //   println!("Iteration: {}", iteration);
+    // }
+    let sum = sum_state(&new_state);
+    let diff = sum - prev_sum;
+    println!("It: {}, sum: {}, diff: {}", iteration + 1, sum, diff);
+    prev_sum = sum;
+
+    // draw_state(&new_state, iteration);
+    prev_state = new_state;
   }
+
+  let last_state = prev_state;
+  let total = sum_state(&last_state);
   println!("Result: {}", total);
+
+  let iters2 = 50000000000u64;
+  let result2 = 9152 + (iters2 - 140) * 52;
+  println!("Result 2: {}", result2);
 }