Optimize day 12 part 1

1 files changed, 79 insertions, 35 deletions

diff --git a/2023/src/bin/day_12.rs b/2023/src/bin/day_12.rs
index 65ffa15..a2e83be 100644
--- a/2023/src/bin/day_12.rs
+++ b/2023/src/bin/day_12.rs
@@ -10,8 +10,11 @@ use std::fs;
 
 fn main() -> Result<(), Box<dyn std::error::Error>> {
     let input = fs::read_to_string("inputs/day_12.txt")?;
-    let parsed = SpringField::parser(&input).unwrap().1;
-    dbg!(&parsed.possibilities_sum());
+    let small = SpringField::parser(&input).unwrap().1;
+    dbg!(&small.possibilities_sum());
+
+    let large = small.expand();
+    dbg!(&large.possibilities_sum());
 
     Ok(())
 }
@@ -39,6 +42,10 @@ impl SpringField {
     fn possibilities_sum(&self) -> usize {
         self.0.iter().map(|r| r.possibilities_count()).sum()
     }
+
+    fn expand(&self) -> SpringField {
+        SpringField(self.0.iter().map(|r| r.expand()).collect())
+    }
 }
 
 impl SpringRow {
@@ -53,26 +60,26 @@ impl SpringRow {
         )(input)
     }
 
-    fn fill_in_springs(&self, bits: usize) -> Vec<Spring> {
-        let mut current_bit_index = 0;
-        self.springs
-            .iter()
-            .map(|maybe_spring| {
-                maybe_spring.unwrap_or_else(|| {
-                    let current_bit = bits & (1 << current_bit_index) != 0;
-                    current_bit_index += 1;
-                    if current_bit {
-                        Spring::Bad
-                    } else {
-                        Spring::Good
-                    }
-                })
-            })
-            .collect()
+    fn expand(&self) -> SpringRow {
+        let mut expanded = SpringRow {
+            springs: Vec::new(),
+            check: Vec::new(),
+        };
+
+        for _ in 0..5 {
+            expanded.springs.append(&mut self.springs.clone());
+            expanded.springs.push(None);
+            expanded.check.append(&mut self.check.clone());
+        }
+
+        // should only have the extra None between, not at the very end.
+        expanded.springs.pop();
+
+        expanded
     }
 
-    fn generate_check(springs: Vec<Spring>) -> Vec<u32> {
-        let mut check = Vec::new();
+    fn validate_check(&self, springs: &[Spring]) -> bool {
+        let mut current_check_index = 0;
         let mut current_count = 0;
         let mut in_bad_lands = false;
 
@@ -80,8 +87,16 @@ impl SpringRow {
             match spring {
                 Spring::Good => {
                     if in_bad_lands {
-                        check.push(current_count);
+                        let valid = self
+                            .check
+                            .get(current_check_index)
+                            .map_or(false, |expected| *expected == current_count);
+                        if !valid {
+                            return false;
+                        }
                         current_count = 0;
+
+                        current_check_index += 1;
                     }
                     in_bad_lands = false;
                 }
@@ -93,24 +108,53 @@ impl SpringRow {
         }
 
         if in_bad_lands {
-            check.push(current_count);
+            let valid = self
+                .check
+                .get(current_check_index)
+                .map_or(false, |expected| *expected == current_count);
+            if !valid {
+                return false;
+            }
+            current_check_index += 1;
         }
-        check
+
+        self.check.len() == current_check_index
     }
 
     fn possibilities_count(&self) -> usize {
-        let unknown_count = self.springs.iter().filter(|s| s.is_none()).count();
-        assert_ne!(unknown_count, 0);
-        let max_possibilities = 2_usize.pow(unknown_count.try_into().unwrap());
-
-        let mut possibilities = 0;
-        for i in 0..max_possibilities {
-            let springs_guess = self.fill_in_springs(i);
-            let generated_check = SpringRow::generate_check(springs_guess);
-            if self.check == generated_check {
-                possibilities += 1;
-            }
-        }
+        let unknown_indexes: Vec<usize> = self
+            .springs
+            .iter()
+            .enumerate()
+            .filter_map(|(i, s)| s.is_none().then_some(i))
+            .collect();
+
+        assert_ne!(unknown_indexes.len(), 0);
+        let max_possibilities = 2_usize.pow(unknown_indexes.len().try_into().unwrap());
+
+        let mut spring_guess: Vec<Spring> = self
+            .springs
+            .iter()
+            .map(|s| s.unwrap_or(Spring::Bad))
+            .collect();
+        let unknown_indexes: Vec<usize> = self
+            .springs
+            .iter()
+            .enumerate()
+            .filter_map(|(i, s)| s.is_none().then_some(i))
+            .collect();
+        let possibilities = (0..max_possibilities)
+            .filter(|i| {
+                for (bit_index, spring_index) in unknown_indexes.iter().enumerate() {
+                    spring_guess[*spring_index] = if i & (1 << bit_index) != 0 {
+                        Spring::Bad
+                    } else {
+                        Spring::Good
+                    };
+                }
+                self.validate_check(&spring_guess)
+            })
+            .count();
 
         possibilities
     }