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

year2018/
day12.rs
