Day 12 part 1

1 files changed, 116 insertions, 8 deletions

diff --git a/2023/src/bin/day_12.rs b/2023/src/bin/day_12.rs
index b3a610b..65ffa15 100644
--- a/2023/src/bin/day_12.rs
+++ b/2023/src/bin/day_12.rs
@@ -1,19 +1,127 @@
-use nom::IResult;
+use nom::{
+    branch::alt,
+    character::complete::{char, line_ending, space1, u32},
+    combinator::{map, value},
+    multi::{many1, separated_list1},
+    sequence::separated_pair,
+    IResult,
+};
 use std::fs;
 
 fn main() -> Result<(), Box<dyn std::error::Error>> {
-    let input = fs::read_to_string("inputs/day_2.txt")?;
-    let parsed = Example::parser(&input).unwrap().1;
-    dbg!(&parsed);
+    let input = fs::read_to_string("inputs/day_12.txt")?;
+    let parsed = SpringField::parser(&input).unwrap().1;
+    dbg!(&parsed.possibilities_sum());
 
     Ok(())
 }
 
 #[derive(Debug)]
-struct Example;
+struct SpringField(Vec<SpringRow>);
 
-impl Example {
-    fn parser(_input: &str) -> IResult<&str, Self> {
-        todo!()
+#[derive(Debug)]
+struct SpringRow {
+    springs: Vec<Option<Spring>>,
+    check: Vec<u32>,
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+enum Spring {
+    Good,
+    Bad,
+}
+
+impl SpringField {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(separated_list1(line_ending, SpringRow::parser), SpringField)(input)
+    }
+
+    fn possibilities_sum(&self) -> usize {
+        self.0.iter().map(|r| r.possibilities_count()).sum()
+    }
+}
+
+impl SpringRow {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(
+            separated_pair(
+                many1(Spring::parser),
+                space1,
+                separated_list1(char(','), u32),
+            ),
+            |(springs, check)| SpringRow { springs, check },
+        )(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 generate_check(springs: Vec<Spring>) -> Vec<u32> {
+        let mut check = Vec::new();
+        let mut current_count = 0;
+        let mut in_bad_lands = false;
+
+        for spring in springs {
+            match spring {
+                Spring::Good => {
+                    if in_bad_lands {
+                        check.push(current_count);
+                        current_count = 0;
+                    }
+                    in_bad_lands = false;
+                }
+                Spring::Bad => {
+                    current_count += 1;
+                    in_bad_lands = true;
+                }
+            }
+        }
+
+        if in_bad_lands {
+            check.push(current_count);
+        }
+        check
+    }
+
+    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;
+            }
+        }
+
+        possibilities
+    }
+}
+
+impl Spring {
+    fn parser(input: &str) -> IResult<&str, Option<Self>> {
+        alt((
+            value(Some(Spring::Good), char('.')),
+            value(Some(Spring::Bad), char('#')),
+            value(None, char('?')),
+        ))(input)
     }
 }