From b013ba7af875288bb2e7a9086ac0c2ddee5d5d6f Mon Sep 17 00:00:00 2001
From: Greg Burri <greg.burri@gmail.com>
Date: Sun, 8 Dec 2024 02:08:48 +0100
Subject: [PATCH] Day 07

---
 src/day06.rs |   2 -
 src/day07.rs | 133 +++++++++++++++++++++++++++++++++++++++++++++++++++
 src/days.rs  |  10 ++++
 src/main.rs  |   4 +-
 4 files changed, 145 insertions(+), 4 deletions(-)
 create mode 100644 src/day07.rs

diff --git a/src/day06.rs b/src/day06.rs
index 579dcc6..a96cf5d 100644
--- a/src/day06.rs
+++ b/src/day06.rs
@@ -155,7 +155,6 @@ mod tests {
     fn test_part1() {
         let (map, guard_pos) = read_map(MAP.as_bytes());
         let n = nb_position_visited_by_guard(&map, guard_pos);
-        println!("n: {}", n);
         assert_eq!(n, 41);
     }
 
@@ -163,7 +162,6 @@ mod tests {
     fn test_part2() {
         let (map, guard_pos) = read_map(MAP.as_bytes());
         let n = nb_possible_obstruction_position(&map, guard_pos);
-        println!("n: {}", n);
         assert_eq!(n, 6);
     }
 
diff --git a/src/day07.rs b/src/day07.rs
new file mode 100644
index 0000000..70ebafa
--- /dev/null
+++ b/src/day07.rs
@@ -0,0 +1,133 @@
+use std::io::BufRead;
+
+use crate::utils;
+
+#[derive(Debug)]
+pub struct Equation {
+    result: i64,
+    operands: Vec<i64>,
+}
+
+pub fn read<R>(reader: R) -> Vec<Equation>
+where
+    R: BufRead,
+{
+    reader
+        .lines()
+        .map(|l| {
+            let l = l.unwrap();
+            let mut result_and_rest = l.split(": ").into_iter();
+            Equation {
+                result: result_and_rest.next().unwrap().parse().unwrap(),
+                operands: utils::split_to_vec(result_and_rest.next().unwrap(), " "),
+            }
+        })
+        .collect()
+}
+
+pub fn sum_valid_equations(equations: &[Equation]) -> i64 {
+    fn is_valid(result: i64, operands: &[i64]) -> bool {
+        let l = operands.len();
+        if l == 1 {
+            return result == operands[0];
+        }
+        let last = operands[l - 1];
+        if result % last == 0 {
+            if is_valid(result / last, &operands[0..l - 1]) {
+                return true;
+            }
+        }
+        let sub = result - last;
+        if sub >= 0 {
+            return is_valid(sub, &operands[0..l - 1]);
+        }
+        false
+    }
+    equations
+        .iter()
+        .filter_map(|eq| {
+            if is_valid(eq.result, &eq.operands) {
+                Some(eq.result)
+            } else {
+                None
+            }
+        })
+        .sum()
+}
+
+fn nb_of_digits(mut v: i64) -> u32 {
+    let mut n = 1;
+    while v >= 10 {
+        v /= 10;
+        n += 1;
+    }
+    n
+}
+
+pub fn sum_valid_equations_with_concat(equations: &[Equation]) -> i64 {
+    fn is_valid(result: i64, operands: &[i64]) -> bool {
+        let l = operands.len();
+        if l == 1 {
+            return result == operands[0];
+        }
+        let last = operands[l - 1];
+        if result % last == 0 {
+            if is_valid(result / last, &operands[0..l - 1]) {
+                return true;
+            }
+        }
+        let sub = result - last;
+        if sub >= 0 {
+            if is_valid(sub, &operands[0..l - 1]) {
+                return true;
+            }
+
+            let p = 10i64.pow(nb_of_digits(last));
+            if sub % p == 0 {
+                if is_valid(sub / p, &operands[0..l - 1]) {
+                    return true;
+                }
+            }
+        }
+        false
+    }
+    equations
+        .iter()
+        .filter_map(|eq| {
+            if is_valid(eq.result, &eq.operands) {
+                Some(eq.result)
+            } else {
+                None
+            }
+        })
+        .sum()
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    static EQUATIONS: &str = "190: 10 19
+3267: 81 40 27
+83: 17 5
+156: 15 6
+7290: 6 8 6 15
+161011: 16 10 13
+192: 17 8 14
+21037: 9 7 18 13
+292: 11 6 16 20";
+
+    #[test]
+    fn test_part1() {
+        let equations = read(EQUATIONS.as_bytes());
+        let sum = sum_valid_equations(&equations);
+        assert_eq!(sum, 3749);
+    }
+
+    #[test]
+    fn test_part2() {
+        let equations = read(EQUATIONS.as_bytes());
+        let sum = sum_valid_equations_with_concat(&equations);
+        assert_eq!(sum, 11387);
+    }
+}
diff --git a/src/days.rs b/src/days.rs
index b977381..3a91a0f 100644
--- a/src/days.rs
+++ b/src/days.rs
@@ -61,3 +61,13 @@ pub fn day06() -> String {
         day06::nb_possible_obstruction_position(&map, guard_pos),
     )
 }
+
+pub fn day07() -> String {
+    let f = fs::File::open("data/day07.input").unwrap();
+    let equations = day07::read(BufReader::new(f));
+    format!(
+        "part1: {}, part2: {}",
+        day07::sum_valid_equations(&equations),
+        day07::sum_valid_equations_with_concat(&equations),
+    )
+}
diff --git a/src/main.rs b/src/main.rs
index 85f283c..1a15e9e 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -9,7 +9,7 @@ mod day03;
 mod day04;
 mod day05;
 mod day06;
-// mod day07;
+mod day07;
 // mod day08;
 // mod day09;
 // mod day10;
@@ -50,7 +50,7 @@ fn main() {
         days::day04,
         days::day05,
         days::day06,
-        // days::day07,
+        days::day07,
         // days::day08,
         // days::day09,
         // days::day10,
-- 
2.45.2