Day 11: Cellula automata

1 files changed, 84 insertions, 0 deletions

diff --git a/src/bin/day_12.rs b/src/bin/day_12.rs
index 6c40cce..65a966d 100644
--- a/src/bin/day_12.rs
+++ b/src/bin/day_12.rs
@@ -4,15 +4,99 @@ use advent_of_code_2018::*;
 use std::error::Error;
 use std::path::PathBuf;
 
+use std::str::FromStr;
+
 // cargo watch -cs "cargo run --release --bin day_12"
 
+use std::collections::HashSet;
+
+#[derive(Debug)]
+struct Rule {
+    input: [bool; 5],
+    output: bool
+}
+
+impl FromStr for Rule {
+    type Err = Box<Error>;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        //##..# => #
+        let mut input = [false; 5];
+        let mut iter = s.chars().filter(|c| *c == '#' || *c == '.');
+        for (i, c) in iter.by_ref().take(5).enumerate() {
+            if c == '#' {
+                input[i] = true;
+            }
+        }
+        Ok(Rule {
+            input,
+            output: iter.next() == Some('#')
+        })
+    }
+}
+
+impl Rule {
+    fn matches(&self, state: &HashSet<i64>, index: i64) -> bool {
+        self.input.iter().enumerate().all(|(i, expected)| {
+            let pot_index = index - 2 + i as i64;
+            *expected == state.contains(&pot_index)
+        })
+    }
+}
+
 fn main() -> Result<(), Box<Error>> {
     let input = read_file(&PathBuf::from("inputs/12.txt"))?;
 
     println!("Input: {:?}", input);
 
+    let mut initial_state: HashSet<i64> = HashSet::new();
+    for (i, c) in input[0].chars().filter(|c| *c == '#' || *c == '.').enumerate() {
+        if c == '#' {
+            initial_state.insert(i as i64);
+        }
+    }
+    let rules = input.iter().skip(1).map(|line| line.parse()).collect::<Result<Vec<Rule>, Box<Error>>>()?;
+
+    debug!(initial_state);
+    debug!(rules);
 
+    let part1_time = 20;
+    let part2_time = 50000000000;
 
+    let part1_final_state = iterate_states(&initial_state, &rules, part1_time);
+    let sum_of_part1_pot_numbers: i64 = part1_final_state.iter().sum();
+    debug!(sum_of_part1_pot_numbers);
 
+    let part2_final_state = iterate_states(&initial_state, &rules, part2_time);
+    let sum_of_part2_pot_numbers: i64 = part2_final_state.iter().sum();
+    debug!(sum_of_part2_pot_numbers);
+    
     Ok(())
 }
+
+fn iterate_states(initial_state: &HashSet<i64>, rules: &[Rule], time: i64) -> HashSet<i64> {
+    let mut current_state = initial_state.clone();
+    for current_time in 0..time {        
+        let mut new_state = HashSet::new();
+        let min = current_state.iter().min().cloned().unwrap_or(-1) - 2;
+        let max = current_state.iter().max().cloned().unwrap_or(-1) + 2;
+
+        for i in min..max+1 {
+            if rules.iter().find(|r| r.matches(&current_state, i)).expect("No matching rule").output {
+                new_state.insert(i as i64);
+            }
+        }
+
+        if current_state.iter().map(|v| v + 1).collect::<HashSet<i64>>() == new_state {
+            // Iterations are just shifting 1 to the right at this
+            // point. Found by inspecting a debugging log of the
+            // generations.
+
+            let remaining_iterations = time-current_time;
+            return current_state.iter().map(|v| v + remaining_iterations).collect::<HashSet<i64>>();
+        }
+        
+        current_state = new_state;
+    }
+    current_state
+}