From d00ec51b82a48654e1bcd1fe2d521bec4a466556 Mon Sep 17 00:00:00 2001
From: Greg Burri <greg.burri@gmail.com>
Date: Wed, 11 Dec 2024 18:18:31 +0100
Subject: [PATCH] Day 11

---
 Cargo.toml   |  2 ++
 src/day07.rs | 11 +---------
 src/day11.rs | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/days.rs  | 12 +++++++++++
 src/main.rs  |  4 ++--
 src/utils.rs | 17 ++++++++++++++-
 6 files changed, 94 insertions(+), 13 deletions(-)
 create mode 100644 src/day11.rs

diff --git a/Cargo.toml b/Cargo.toml
index 18a05b2..5d2d9af 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -12,6 +12,8 @@ advent_of_code_common = { path = "advent_of_code_common" }
 itertools = "0.13"
 regex = "1"
 nalgebra = "0.33"
+num = "0.4"
+rustc-hash = "2.1"
 
 [profile.release]
 opt-level = 3
diff --git a/src/day07.rs b/src/day07.rs
index d1a90d2..0ed8919 100644
--- a/src/day07.rs
+++ b/src/day07.rs
@@ -52,15 +52,6 @@ pub fn sum_valid_equations(equations: &[Equation]) -> i64 {
         .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();
@@ -79,7 +70,7 @@ pub fn sum_valid_equations_with_concat(equations: &[Equation]) -> i64 {
                 return true;
             }
 
-            let p = 10i64.pow(nb_of_digits(last));
+            let p = 10i64.pow(utils::nb_of_digits(last));
             if sub % p == 0 {
                 if is_valid(sub / p, &operands[0..l - 1]) {
                     return true;
diff --git a/src/day11.rs b/src/day11.rs
new file mode 100644
index 0000000..c9c39d7
--- /dev/null
+++ b/src/day11.rs
@@ -0,0 +1,61 @@
+use std::io::BufRead;
+
+use rustc_hash::FxHashMap;
+
+use crate::utils;
+
+type Stones = FxHashMap<u64, u64>;
+
+pub fn read(reader: &mut dyn BufRead) -> Stones {
+    Stones::from_iter(
+        utils::split_to_vec(&std::io::read_to_string(reader).unwrap(), " ")
+            .into_iter()
+            .map(|s| (s, 1)),
+    )
+}
+
+fn add_or_set(map: &mut FxHashMap<u64, u64>, k: u64, n: u64) {
+    map.entry(k).and_modify(|v| *v += n).or_insert(n);
+}
+
+pub fn blink(stones: FxHashMap<u64, u64>, i: u32) -> FxHashMap<u64, u64> {
+    if i == 0 {
+        stones
+    } else {
+        let mut next_stones = FxHashMap::<u64, u64>::default();
+        for (stone, n) in stones {
+            if stone == 0 {
+                add_or_set(&mut next_stones, 1, n);
+            } else {
+                let nb_digits = utils::nb_of_digits(stone);
+                if nb_digits % 2 == 0 {
+                    let base = 10u64.pow(nb_digits / 2);
+                    let left = stone / base;
+                    let right = stone - left * base;
+                    add_or_set(&mut next_stones, left, n);
+                    add_or_set(&mut next_stones, right, n);
+                } else {
+                    add_or_set(&mut next_stones, stone * 2024, n);
+                }
+            }
+        }
+
+        blink(next_stones, i - 1)
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    static STONES: &str = "125 17";
+
+    #[test]
+    fn test_part1_and_part2() {
+        let stones = read(&mut STONES.as_bytes());
+        let stones_after_6 = blink(stones.clone(), 6);
+        let stones_after_25 = blink(stones, 25);
+        assert_eq!(stones_after_6.values().sum::<u64>(), 22);
+        assert_eq!(stones_after_25.values().sum::<u64>(), 55312);
+    }
+}
diff --git a/src/days.rs b/src/days.rs
index 2ab38a7..40049bb 100644
--- a/src/days.rs
+++ b/src/days.rs
@@ -93,3 +93,15 @@ pub fn day10(reader: &mut dyn BufRead) -> String {
         day10::score(&map, &start_positions, true),
     )
 }
+
+pub fn day11(reader: &mut dyn BufRead) -> String {
+    let stones = day11::read(reader);
+    let stones_25 = day11::blink(stones, 25);
+    let nb_stones_25 = stones_25.values().sum::<u64>();
+    let stones_75 = day11::blink(stones_25, 50);
+    format!(
+        "part1: {}, part2: {}",
+        nb_stones_25,
+        stones_75.values().sum::<u64>()
+    )
+}
diff --git a/src/main.rs b/src/main.rs
index 7258db4..56d74f2 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -12,7 +12,7 @@ mod day07;
 mod day08;
 mod day09;
 mod day10;
-// mod day11;
+mod day11;
 // mod day12;
 // mod day13;
 // mod day14;
@@ -43,7 +43,7 @@ fn main() {
         days::day08,
         days::day09,
         days::day10,
-        // days::day11,
+        days::day11,
         // days::day12,
         // days::day13,
         // days::day14,
diff --git a/src/utils.rs b/src/utils.rs
index 135bd36..a2a1d8d 100644
--- a/src/utils.rs
+++ b/src/utils.rs
@@ -1,4 +1,6 @@
-use std::{fmt::Debug, str::FromStr};
+use std::{cmp, fmt::Debug, str::FromStr};
+
+use num;
 
 pub fn split_to_vec<T>(str: &str, pat: &str) -> Vec<T>
 where
@@ -7,3 +9,16 @@ where
 {
     str.split(pat).map(|v| v.parse::<T>().unwrap()).collect()
 }
+
+pub fn nb_of_digits<T>(mut v: T) -> u32
+where
+    T: cmp::PartialOrd<T> + std::ops::DivAssign<T> + num::FromPrimitive + Copy,
+{
+    let ten = T::from_u32(10).unwrap();
+    let mut n = 1;
+    while v >= ten {
+        v /= ten;
+        n += 1;
+    }
+    n
+}
-- 
2.45.2