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
|
use std::collections::HashMap;
static DAY: u8 = 11;
fn main() {
let input = advent::read_lines(DAY);
println!("{DAY}a: {}", blink_stones(&input[0], 25));
println!("{DAY}b: {}", blink_stones(&input[0], 75));
}
fn next_stones(number: u64) -> Vec<u64> {
/* rule 1 */
if number == 0 {
return [1].to_vec();
}
/* rule 2 */
let number_str = number.to_string();
if number_str.len() % 2 == 0 {
let left = number_str.chars().take(number_str.len() / 2).collect::<String>();
let right = number_str.chars().skip(number_str.len() / 2).collect::<String>();
let left = left.parse::<u64>().unwrap();
let right = right.parse::<u64>().unwrap();
return [left, right].to_vec();
}
/* rule 3 */
[2024 * number].to_vec()
}
fn count_stones(number: u64, rounds: u32, cache: &mut HashMap<(u64, u32), u64>) -> u64 {
if let Some(n) = cache.get(&(number, rounds)) {
return *n;
}
if rounds == 0 {
return 1;
}
let mut count = 0;
for n in next_stones(number) {
count += count_stones(n, rounds - 1, cache);
cache.insert((number, rounds), count);
}
count
}
fn blink_stones(input: &str, rounds: u32) -> u64 {
let mut cache = HashMap::new();
input.split(" ")
.map(|val| val.parse::<u64>().unwrap())
.map(|val| count_stones(val, rounds, &mut cache))
.sum()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test() {
let input = "125 17";
assert_eq!(blink_stones(input, 25), 55312);
}
}
|
