advent_of_code_2024/
day_11.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
//! This is my solution for [Advent of Code - Day 11: _Plutonian Pebbles_](https://adventofcode.com/2024/day/11)
//!
//! [`parse_input`] turns the text into numbers.
//!
//! [`count_after_blinks`] solves both parts, calling [`count_for_stone`] recursively. This is cached as there are a
//! lot of repeat small numbers at each depth. [`blink`] handles a single blink.

use cached::proc_macro::cached;
use std::fs;

/// The entry point for running the solutions with the 'real' puzzle input.
///
/// - The puzzle input is expected to be at `<project_root>/res/day-11-input`
/// - It is expected this will be called by [`super::main()`] when the user elects to run day 11.
pub fn run() {
    let contents = fs::read_to_string("res/day-11-input.txt").expect("Failed to read file");
    let stones = parse_input(&contents);

    println!(
        "After 25 blinks there are {} stones",
        count_after_blinks(&stones, 25)
    );

    println!(
        "After 75 blinks there are {} stones",
        count_after_blinks(&stones, 75)
    );
}

/// Turn the space separated number strings into `u64`s
fn parse_input(input: &String) -> Vec<u64> {
    input
        .trim()
        .split(" ")
        .map(|num| num.parse().unwrap())
        .collect()
}

/// This was originally written to work on the whole array of stones, but that wasn't convenient for caching. It is
/// left as is for convenience of using existing tests.
fn blink(stones: &Vec<u64>) -> Vec<u64> {
    stones
        .into_iter()
        .flat_map(|&stone| {
            if stone == 0 {
                return vec![1];
            }

            // Even number of digits, split in two
            let digits = stone.ilog(10) + 1;
            if digits % 2 == 0 {
                let midpoint = 10u64.pow(digits / 2);
                return vec![stone / midpoint, stone % midpoint];
            }

            vec![stone * 2024]
        })
        .collect()
}

/// Recursive function to calculate the expansion of a single stone. There are many repeats, especially for small
/// numbers, so this is cached to allow the program to run quickly.
#[cached]
fn count_for_stone(stone: u64, iterations: u8) -> usize {
    if iterations == 0 {
        return 1;
    }

    let result = blink(&vec![stone])
        .iter()
        .map(|&next_stone| count_for_stone(next_stone, iterations - 1))
        .sum();

    result
}

/// Solves both parts. Delegates to [`count_for_stone`] for each stone in the list.
fn count_after_blinks(stones: &Vec<u64>, number_of_blinks: u8) -> usize {
    stones
        .iter()
        .map(|&stone| count_for_stone(stone, number_of_blinks))
        .sum()
}

#[cfg(test)]
mod tests {
    use crate::day_11::*;
    
    #[test]
    fn can_parse_input() {
        assert_eq!(
            parse_input(&"0 1 10 99 999\n".to_string()),
            vec![0, 1, 10, 99, 999]
        )
    }

    #[test]
    fn can_step_stones() {
        assert_eq!(
            blink(&vec![0, 1, 10, 99, 999]),
            vec![1, 2024, 1, 0, 9, 9, 2021976]
        );
        assert_eq!(blink(&vec![125, 17]), vec![253000, 1, 7]);
        assert_eq!(blink(&vec![253000, 1, 7]), vec![253, 0, 2024, 14168]);
        assert_eq!(
            blink(&vec![253, 0, 2024, 14168]),
            vec![512072, 1, 20, 24, 28676032]
        );
        assert_eq!(
            blink(&vec![512072, 1, 20, 24, 28676032]),
            vec![512, 72, 2024, 2, 0, 2, 4, 2867, 6032]
        );
        assert_eq!(
            blink(&vec![512, 72, 2024, 2, 0, 2, 4, 2867, 6032]),
            vec![1036288, 7, 2, 20, 24, 4048, 1, 4048, 8096, 28, 67, 60, 32]
        );
        assert_eq!(
            blink(&vec![
                1036288, 7, 2, 20, 24, 4048, 1, 4048, 8096, 28, 67, 60, 32
            ]),
            vec![
                2097446912, 14168, 4048, 2, 0, 2, 4, 40, 48, 2024, 40, 48, 80, 96, 2, 8, 6, 7, 6,
                0, 3, 2
            ]
        );
    }

    #[test]
    fn can_count_stones_after_n_blinks() {
        assert_eq!(count_after_blinks(&vec![125, 17], 6), 22);

        assert_eq!(count_after_blinks(&vec![125, 17], 25), 55312);
    }
}