year2018/
day18.rs

1use utils::bit::bitwise_count8;
2use utils::prelude::*;
3
4/// Simulating a cyclic forest cellular automaton.
5#[derive(Clone, Debug)]
6pub struct Day18 {
7    masks: [[u64; 52]; 2],
8}
9
10impl Day18 {
11    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
12        // 50x50 bitmasks, with 1 bit/row of padding on each side
13        let mut tree_mask = [0u64; 52];
14        let mut lumberyard_mask = [0u64; 52];
15
16        let mut row = 0;
17        for line in input.lines() {
18            if row >= 50 {
19                return Err(InputError::new(input, line, "too many rows"));
20            }
21            if line.len() > 50 {
22                return Err(InputError::new(input, line, "too many columns"));
23            }
24            for (col, b) in line.bytes().enumerate() {
25                match b {
26                    b'.' => {}
27                    b'|' => tree_mask[row + 1] |= 1 << (col + 1),
28                    b'#' => lumberyard_mask[row + 1] |= 1 << (col + 1),
29                    _ => {
30                        return Err(InputError::new(input, b as char, "expected '.', '|', '#'"));
31                    }
32                };
33            }
34            row += 1;
35        }
36
37        if row != 50 {
38            return Err(InputError::new(input, 0, "expected 50 rows"));
39        }
40
41        Ok(Self {
42            masks: [tree_mask, lumberyard_mask],
43        })
44    }
45
46    #[must_use]
47    pub fn part1(&self) -> u32 {
48        let mut masks = &mut self.masks.clone();
49        let mut temp = &mut [[0u64; _]; _];
50
51        for _ in 0..10 {
52            Self::advance(masks, temp);
53            (masks, temp) = (temp, masks);
54        }
55
56        Self::resource_value(masks)
57    }
58
59    #[must_use]
60    pub fn part2(&self) -> u32 {
61        // Brent's algorithm for cycle detection, as used in 2017 day 6.
62        let (mut power, mut lambda) = (1, 1);
63
64        let mut tortoise = &mut self.masks.clone();
65        let mut hare = &mut self.masks.clone();
66        let mut temp = &mut [[0u64; _]; _];
67
68        Self::advance(hare, temp);
69        (hare, temp) = (temp, hare);
70
71        while tortoise != hare {
72            if power == lambda {
73                *tortoise = *hare;
74                power *= 2;
75                lambda = 0;
76            }
77
78            Self::advance(hare, temp);
79            (hare, temp) = (temp, hare);
80
81            lambda += 1;
82        }
83
84        *tortoise = self.masks;
85        *hare = self.masks;
86        for _ in 0..lambda {
87            Self::advance(hare, temp);
88            (hare, temp) = (temp, hare);
89        }
90
91        let mut mu = 0;
92        while tortoise != hare {
93            Self::advance(tortoise, temp);
94            (tortoise, temp) = (temp, tortoise);
95
96            Self::advance(hare, temp);
97            (hare, temp) = (temp, hare);
98
99            mu += 1;
100        }
101
102        let mut minutes = 1_000_000_000 - mu;
103        minutes -= (minutes / lambda) * lambda;
104
105        while minutes > 0 {
106            Self::advance(hare, temp);
107            (hare, temp) = (temp, hare);
108
109            minutes -= 1;
110        }
111
112        Self::resource_value(hare)
113    }
114
115    #[inline(never)]
116    fn advance([trees, yards]: &[[u64; 52]; 2], [next_trees, next_yards]: &mut [[u64; 52]; 2]) {
117        const COLUMNS_MASK: u64 = ((1 << 50) - 1) << 1;
118
119        // This loop should be vectorized by the compiler
120        for row in 1..51 {
121            let (gte1_trees, gte3_trees) = Self::adjacent_gte1_gte3(trees, row);
122            let (gte1_yards, gte3_yards) = Self::adjacent_gte1_gte3(yards, row);
123
124            let open_to_trees = !trees[row] & !yards[row] & gte3_trees;
125            let trees_to_yard = trees[row] & gte3_yards;
126            let yard_to_open = yards[row] & !(gte1_trees & gte1_yards);
127
128            next_trees[row] = ((trees[row] & !trees_to_yard) | open_to_trees) & COLUMNS_MASK;
129            next_yards[row] = ((yards[row] & !yard_to_open) | trees_to_yard) & COLUMNS_MASK;
130        }
131    }
132
133    #[inline]
134    pub fn adjacent_gte1_gte3(mask: &[u64; 52], row: usize) -> (u64, u64) {
135        let adjacent = [
136            mask[row - 1] << 1,
137            mask[row - 1],
138            mask[row - 1] >> 1,
139            mask[row] << 1,
140            mask[row] >> 1,
141            mask[row + 1] << 1,
142            mask[row + 1],
143            mask[row + 1] >> 1,
144        ];
145
146        let [bit0, bit1, bit2, bit3] = bitwise_count8(&adjacent);
147        let gte1 = bit0 | bit1 | bit2 | bit3;
148        let gte3 = (bit0 & bit1) | bit2 | bit3;
149
150        (gte1, gte3)
151    }
152
153    #[inline]
154    fn resource_value([trees, yards]: &[[u64; 52]; 2]) -> u32 {
155        let tree_count = trees.iter().map(|m| m.count_ones()).sum::<u32>();
156        let yard_count = yards.iter().map(|m| m.count_ones()).sum::<u32>();
157        tree_count * yard_count
158    }
159}
160
161examples!(Day18 -> (u32, u32) []);
year2018/day18.rs

year2018/
day18.rs
