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

aoc/year2018/
day12.rs
