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//! We use a vector to store which pots are occupied and which are empty in each generation.
7//! When calculating the next step, we truncate the bit vector on the left and right.
8//! This makes it easier to compare generations in part two.
9//!
10//! The trick for part two is that the plants will eventually stabilize into a stable pattern
11//! (similar to a [glider](https://en.wikipedia.org/wiki/Glider_(Conway%27s_Game_of_Life)))
12//! that moves by the same amount each generation. Once two subsequent generations are the same,
13//! except for the starting position, we extrapolate 50 billion generations into the future.
14use std::iter::repeat_n;
15use std::mem::swap;
16
17type Input = (i64, i64);
18
19struct Pots {
20    /// Vector representing the pots. 1 means there is a plant in the pot, 0 means there isn't.
21    state: Vec<u8>,
22    /// A copy of the vector `state` before [`Self::step`] was called.
23    prev_state: Vec<u8>,
24    /// The id of the pot at the beginning of the bit vector `state`.
25    pos: i64,
26}
27
28impl Pots {
29    /// Parses the initial state into a bit vector.
30    fn from(initial_state: &[u8]) -> Self {
31        let state: Vec<_> = initial_state.iter().map(|&b| u8::from(b == b'#')).collect();
32        Self { state, prev_state: Vec::new(), pos: 0 }
33    }
34
35    /// Applies the given rules to the pots and updates [`Self::state`]. A copy of the state before
36    /// this method was called is left in [`Self::prev_state`].
37    fn step(&mut self, rules: &[u8; 32]) {
38        // Prepare new state.
39        swap(&mut self.state, &mut self.prev_state);
40        self.state.clear();
41
42        let start = self.prev_state.iter().position(|&b| b == 1).unwrap();
43        let end = self.prev_state.iter().rposition(|&b| b == 1).unwrap();
44        let mut mask = 0;
45
46        // Apply rules and build up new state.
47        // Pad zeros onto the end to make handling next state easier.
48        for b in self.prev_state[start..=end].iter().copied().chain(repeat_n(0, 4)) {
49            mask = ((mask << 1) | b as usize) & 0b11111;
50            self.state.push(rules[mask]);
51        }
52
53        // Update start position.
54        self.pos += start as i64 - 2;
55    }
56
57    /// Returns the sum of the numbers of all pots containing plants.
58    fn sum(&self) -> i64 {
59        self.state.iter().enumerate().map(|(i, &s)| (self.pos + i as i64) * s as i64).sum()
60    }
61}
62
63pub fn parse(input: &str) -> Input {
64    // Parse initial state.
65    let (prefix, suffix) = input.split_once("\n\n").unwrap();
66    let mut pots = Pots::from(&prefix.as_bytes()[15..]);
67
68    // Parse rules into a table with all possible 2⁵=32 patterns.
69    let mut rules = [0; 32];
70    for line in suffix.lines().map(str::as_bytes) {
71        if line[9] == b'#' {
72            let binary = (0..5).fold(0, |acc, i| (acc << 1) | usize::from(line[i] == b'#'));
73            rules[binary] = 1;
74        }
75    }
76
77    // Part one - Simulate the first 20 steps.
78    for _ in 0..20 {
79        pots.step(&rules);
80    }
81    let part_one = pots.sum();
82
83    // Part two - Only simulate until the generation repeats.
84    for steps in 20.. {
85        let prev_pos = pots.pos;
86        pots.step(&rules);
87        if pots.state == pots.prev_state {
88            // Generation has repeated - extrapolate to 50 billion steps.
89            pots.pos += (pots.pos - prev_pos) * (50_000_000_000 - steps - 1);
90            break;
91        }
92    }
93
94    let part_two = pots.sum();
95    (part_one, part_two)
96}
97
98pub fn part1(input: &Input) -> i64 {
99    input.0
100}
101
102pub fn part2(input: &Input) -> i64 {
103    input.1
104}
aoc/year2018/day12.rs

aoc/year2018/
day12.rs
