aoc/year2018/
day12.rs

1//! # Subterranean Sustainability
2//!
3//! The problem is a one dimensional version of
4//! [Conway's Game of Life](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life).
5//!
6//! The trick for part two is that the plants will eventually stabilize into a repeating pattern
7//! that expands by the same amount each generation. Once 2 deltas between 3 subsequent
8//! generations are the same we extrapolate 50 billion generations into the future.
9use std::iter::repeat_n;
10
11pub struct Input {
12    rules: Vec<usize>,
13    state: Tunnel,
14}
15
16#[derive(Clone)]
17pub struct Tunnel {
18    plants: Vec<usize>,
19    start: i64,
20    sum: i64,
21}
22
23pub fn parse(input: &str) -> Input {
24    let lines: Vec<_> = input.lines().map(str::as_bytes).collect();
25    // Convert ASCII characters to `1` for a plant and `0` for an empty pot.
26    let plants: Vec<_> = lines[0][15..].iter().map(|b| (b & 1) as usize).collect();
27    // 5 plants gives 2⁵ = 32 possible combinations to consider.
28    let mut rules = vec![0; 32];
29
30    // Convert each pattern into an index for fast lookup. For example `..#.#` becomes 5.
31    for line in &lines[2..] {
32        let binary = line.iter().fold(0, |acc, b| (acc << 1) | (b & 1) as usize);
33        rules[binary >> 5] = binary & 1;
34    }
35
36    Input { rules, state: Tunnel { plants, start: 0, sum: 0 } }
37}
38
39pub fn part1(input: &Input) -> i64 {
40    let mut current = input.state.clone();
41
42    for _ in 0..20 {
43        current = step(&input.rules, &current);
44    }
45
46    current.sum
47}
48
49pub fn part2(input: &Input) -> i64 {
50    let mut current = input.state.clone();
51    let mut delta = 0;
52    let mut generations = 0;
53
54    loop {
55        let next = step(&input.rules, &current);
56        let next_delta = next.sum - current.sum;
57
58        // Two identical deltas indicates that the pattern has stabilized.
59        if delta == next_delta {
60            break current.sum + delta * (50_000_000_000 - generations);
61        }
62
63        current = next;
64        delta = next_delta;
65        generations += 1;
66    }
67}
68
69fn step(rules: &[usize], tunnel: &Tunnel) -> Tunnel {
70    let mut index = 0;
71    let mut sum = 0;
72    let mut position = tunnel.start - 2;
73    let mut plants = Vec::with_capacity(1_000);
74
75    // Add four extra empty pots to the end to make checking the last pattern easier.
76    for plant in tunnel.plants.iter().copied().chain(repeat_n(0, 4)) {
77        index = ((index << 1) | plant) & 0b11111;
78
79        sum += position * rules[index] as i64;
80        position += 1;
81
82        plants.push(rules[index]);
83    }
84
85    // Tunnel expands by 2 pots at each end.
86    Tunnel { plants, start: tunnel.start - 2, sum }
87}
aoc/year2018/day12.rs

aoc/year2018/
day12.rs
