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] |= u64::from(b) << (i % 64);
46            sum += i64::from(b) * i as i64;
47        }
48
49        let mut rules_mask = 0;
50        for &(lhs, rhs) in &rules {
51            let index = lhs
52                .iter()
53                .enumerate()
54                .fold(0, |acc, (i, &b)| acc | u32::from(b) << i);
55            rules_mask |= u32::from(rhs) << 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        assert!(
99            self.len + 4 < WIDTH * 64,
100            "no solution found: reached width limit"
101        );
102
103        let (mut pots, mut start, mut len, mut sum) = ([0; WIDTH], self.start - 2, 0, 0);
104        let (mut index, mut rule) = (0, 0);
105        for (old_index, pot_num) in (0..self.len + 4).zip(start..) {
106            rule >>= 1;
107            rule |= ((self.pots[old_index / 64] >> (old_index % 64)) & 1) << 4;
108
109            let value = (rules & (1 << rule)) != 0;
110            if index == 0 && !value {
111                // Skip over empty plant pots at the start
112                start += 1;
113                continue;
114            }
115            pots[index / 64] |= u64::from(value) << (index % 64);
116
117            index += 1;
118            if value {
119                sum += pot_num;
120
121                // Don't include empty plant pots at the end in the length
122                len = index;
123            }
124        }
125
126        State {
127            pots,
128            start,
129            len,
130            sum,
131        }
132    }
133}
134
135examples!(Day12 -> (i64, i64) [
136    {file: "day12_example0.txt", part1: 325},
137    // Custom examples
138    {
139        input: "initial state: .#\n\n..#.. => #",
140        part1: 1,
141        part2: 1
142    },
143    {
144        input: "initial state: #\n\n.#... => #",
145        part1: PART1_GENERATIONS,
146        part2: PART2_GENERATIONS
147    },
148    {
149        input: "initial state: #\n\n....# => #",
150        part1: -2 * PART1_GENERATIONS,
151        part2: -2 * PART2_GENERATIONS
152    },
153    {
154        input: "initial state: ##\n\n.##.. => #\n##... => #",
155        part1: 2 * PART1_GENERATIONS + 1,
156        part2: 2 * PART2_GENERATIONS + 1,
157    },
158    //             01234
159    // 0:          ##.##
160    // 1:         ##.#
161    // 2:        ##...#
162    // 3:       ##....##
163    // 4:      ##....##
164    // 5:    ##....##
165    {
166        input: "initial state: ##.##\n\n##.## => #\n..#.. => #\n.#... => #\n..##. => #\n...## => #",
167        part1: -4 * PART1_GENERATIONS + 14,
168        part2: -4 * PART2_GENERATIONS + 14,
169    },
170]);
year2018/day12.rs

year2018/
day12.rs
