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

aoc/year2018/
day12.rs
