-
Notifications
You must be signed in to change notification settings - Fork 15
/
day12.rs
87 lines (70 loc) · 2.55 KB
/
day12.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
//! # Subterranean Sustainability
//!
//! The problem is a one dimensional version of
//! [Conway's Game of Life](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life).
//!
//! The trick for part two is that the plants will eventually stabilize into a repeating pattern
//! that expands by the same amount each generation. Once 2 deltas between 3 subsequent
//! generations are the same we extrapolate 50 billion generations into the future.
use std::iter::repeat;
pub struct Input {
rules: Vec<usize>,
state: Tunnel,
}
#[derive(Clone)]
pub struct Tunnel {
plants: Vec<usize>,
start: i64,
sum: i64,
}
pub fn parse(input: &str) -> Input {
let lines: Vec<_> = input.lines().map(str::as_bytes).collect();
// Convert ASCII characters to `1` for a plant and `0` for an empty pot.
let plants: Vec<_> = lines[0][15..].iter().map(|b| (b & 1) as usize).collect();
// 5 plants gives 2⁵ = 32 possible combinations to consider.
let mut rules = vec![0; 32];
// Convert each pattern into an index for fast lookup. For example `..#.#` becomes 5.
for line in &lines[2..] {
let binary = line.iter().fold(0, |acc, b| (acc << 1) | (b & 1) as usize);
rules[binary >> 5] = binary & 1;
}
Input { rules, state: Tunnel { plants, start: 0, sum: 0 } }
}
pub fn part1(input: &Input) -> i64 {
let mut current = input.state.clone();
for _ in 0..20 {
current = step(&input.rules, ¤t);
}
current.sum
}
pub fn part2(input: &Input) -> i64 {
let mut current = input.state.clone();
let mut delta = 0;
let mut generations = 0;
loop {
let next = step(&input.rules, ¤t);
let next_delta = next.sum - current.sum;
// Two identical deltas indicates that the pattern has stabilized.
if delta == next_delta {
break current.sum + delta * (50_000_000_000 - generations);
}
current = next;
delta = next_delta;
generations += 1;
}
}
fn step(rules: &[usize], tunnel: &Tunnel) -> Tunnel {
let mut index = 0;
let mut sum = 0;
let mut position = tunnel.start - 2;
let mut plants = Vec::with_capacity(1_000);
// Add four extra empty pots to the end to make checking the last pattern easier.
for plant in tunnel.plants.iter().chain(repeat(&0).take(4)) {
index = ((index << 1) | plant) & 0b11111;
sum += position * rules[index] as i64;
position += 1;
plants.push(rules[index]);
}
// Tunnel expands by 2 pots at each end.
Tunnel { plants, start: tunnel.start - 2, sum }
}