year2018/
day12.rs

1use utils::prelude::*;
2
3/// Simulating 1D cellular automata.
4#[derive(Clone, Debug)]
5pub struct Day12 {
6    initial: State,
7    rules: u32,
8}
9
10#[derive(Copy, Clone, Debug)]
11struct State {
12    pots: [u64; WIDTH],
13    start: i64,
14    len: usize,
15    sum: i64,
16}
17
18const WIDTH: usize = 4;
19const PART1_GENERATIONS: i64 = 20;
20const PART2_GENERATIONS: i64 = 50_000_000_000;
21
22impl Day12 {
23    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
24        let cell = parser::byte_map!(
25            b'#' => true,
26            b'.' => false,
27        );
28
29        let (initial, rules) = cell
30            .repeat_arrayvec::<100, _>(parser::noop(), 1)
31            .with_prefix("initial state: ")
32            .with_suffix(parser::eol().then(parser::eol()))
33            .then(
34                cell.repeat_n::<5, _>(parser::noop())
35                    .with_suffix(" => ")
36                    .then(cell)
37                    .repeat_arrayvec::<32, _>(parser::eol(), 1),
38            )
39            .parse_complete(input)?;
40
41        let mut pots = [0; WIDTH];
42        let mut sum = 0;
43        for (i, &b) in initial.iter().enumerate() {
44            pots[i / 64] |= (b as u64) << (i % 64);
45            sum += i64::from(b) * i as i64;
46        }
47
48        let mut rules_mask = 0;
49        for &(lhs, rhs) in rules.iter() {
50            let index = lhs
51                .iter()
52                .enumerate()
53                .fold(0, |acc, (i, &b)| acc | (b as u32) << i);
54            rules_mask |= (rhs as u32) << index;
55        }
56
57        Ok(Self {
58            initial: State {
59                pots,
60                start: 0,
61                len: initial.len(),
62                sum,
63            },
64            rules: rules_mask,
65        })
66    }
67
68    #[must_use]
69    pub fn part1(&self) -> i64 {
70        let mut state = self.initial;
71        for _ in 0..PART1_GENERATIONS {
72            state = state.next(self.rules);
73        }
74        state.sum
75    }
76
77    #[must_use]
78    pub fn part2(&self) -> i64 {
79        let mut state = self.initial;
80        for remaining in (PART2_GENERATIONS - 1000..PART2_GENERATIONS).rev() {
81            let next = state.next(self.rules);
82
83            // In the input the pattern eventually stabilizes and just moves to the right each
84            // iteration
85            if state.len == next.len && state.pots == next.pots {
86                return next.sum + remaining * (next.sum - state.sum);
87            }
88
89            state = next;
90        }
91        panic!("no solution found: reached generation limit")
92    }
93}
94
95impl State {
96    fn next(&self, rules: u32) -> State {
97        if self.len + 4 >= WIDTH * 64 {
98            panic!("no solution found: reached width limit");
99        }
100
101        let (mut pots, mut start, mut len, mut sum) = ([0; WIDTH], self.start - 2, 0, 0);
102        let (mut index, mut rule) = (0, 0);
103        for (old_index, pot_num) in (0..self.len + 4).zip(start..) {
104            rule >>= 1;
105            rule |= ((self.pots[old_index / 64] >> (old_index % 64)) & 1) << 4;
106
107            let value = (rules & (1 << rule)) != 0;
108            if index == 0 && !value {
109                // Skip over empty plant pots at the start
110                start += 1;
111                continue;
112            }
113            pots[index / 64] |= (value as u64) << (index % 64);
114
115            index += 1;
116            if value {
117                sum += pot_num;
118
119                // Don't include empty plant pots at the end in the length
120                len = index;
121            }
122        }
123
124        State {
125            pots,
126            start,
127            len,
128            sum,
129        }
130    }
131}
132
133examples!(Day12 -> (i64, i64) [
134    {file: "day12_example0.txt", part1: 325},
135    // Custom examples
136    {
137        input: "initial state: .#\n\n..#.. => #",
138        part1: 1,
139        part2: 1
140    },
141    {
142        input: "initial state: #\n\n.#... => #",
143        part1: PART1_GENERATIONS,
144        part2: PART2_GENERATIONS
145    },
146    {
147        input: "initial state: #\n\n....# => #",
148        part1: -2 * PART1_GENERATIONS,
149        part2: -2 * PART2_GENERATIONS
150    },
151    {
152        input: "initial state: ##\n\n.##.. => #\n##... => #",
153        part1: 2 * PART1_GENERATIONS + 1,
154        part2: 2 * PART2_GENERATIONS + 1,
155    },
156    //             01234
157    // 0:          ##.##
158    // 1:         ##.#
159    // 2:        ##...#
160    // 3:       ##....##
161    // 4:      ##....##
162    // 5:    ##....##
163    {
164        input: "initial state: ##.##\n\n##.## => #\n..#.. => #\n.#... => #\n..##. => #\n...## => #",
165        part1: -4 * PART1_GENERATIONS + 14,
166        part2: -4 * PART2_GENERATIONS + 14,
167    },
168]);
year2018/day12.rs

year2018/
day12.rs
