aoc/year2018/
day18.rs

1//! # Settlers of The North Pole
2//!
3//! This problem is a cellular automaton similar to the well known
4//! [Game of Life](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life). To solve part two
5//! we look for a [cycle](https://en.wikipedia.org/wiki/Cycle_detection) then
6//! extrapolate forward a billion generations.
7//!
8//! To efficiently compute the next generation a [SWAR](https://en.wikipedia.org/wiki/SWAR)
9//! approach is used. The count of trees and lumberyards is packed into a `u64` so that we can
10//! process 8 acres at a time. Lumberyards are stored in the high nibble of each byte
11//! and trees in the low nibble. For example:
12//!
13//! ```none
14//!     .#.#...|
15//!     .....#|# => 11 11 21 11 21 02 21 02 => 0x1111211121022102
16//!     .|..|...
17//! ```
18//!
19//! The total number of adjacent trees or lumberyards is then calculated in two passes.
20//! First the horizontal sum of each row is computed by bit shifting left and right by 8.
21//! Then the vertical sum of 3 horizontal sums gives the total.
22//!
23//! Bitwise logic then computes the next generation in batches of 8 acres at a time.
24use crate::util::hash::*;
25use std::hash::{Hash, Hasher};
26
27/// Bitwise logic galore.
28const OPEN: u64 = 0x00;
29const TREE: u64 = 0x01;
30const LUMBERYARD: u64 = 0x10;
31const EDGE: u64 = 0xffff000000000000;
32const LOWER: u64 = 0x0f0f0f0f0f0f0f0f;
33const UPPER: u64 = 0xf0f0f0f0f0f0f0f0;
34const THIRTEENS: u64 = 0x0d0d0d0d0d0d0d0d;
35const FIFTEENS: u64 = 0x0f0f0f0f0f0f0f0f;
36
37/// New type wrapper so that we can use a custom hash function.
38#[derive(PartialEq, Eq)]
39pub struct Key {
40    area: [u64; 350],
41}
42
43/// Hash only two cells as a reasonable tradeoff between speed and collision resistance.
44impl Hash for Key {
45    fn hash<H: Hasher>(&self, state: &mut H) {
46        self.area[100].hash(state);
47        self.area[200].hash(state);
48    }
49}
50
51/// Pack the input into an array of `u64`.
52/// The input is 50 acres wide, so requires `ceil(50 / 8) = 7` elements for each row.
53pub fn parse(input: &str) -> Key {
54    let mut area = [0; 350];
55
56    for (y, line) in input.lines().map(str::as_bytes).enumerate() {
57        for (x, byte) in line.iter().enumerate() {
58            let acre = match byte {
59                b'|' => TREE,
60                b'#' => LUMBERYARD,
61                _ => OPEN,
62            };
63            let index = (y * 7) + (x / 8);
64            let offset = 56 - 8 * (x % 8);
65            area[index] |= acre << offset;
66        }
67    }
68
69    Key { area }
70}
71
72/// Compute 10 generations.
73pub fn part1(input: &Key) -> u32 {
74    let mut area = input.area;
75    let mut rows = [0; 364];
76
77    for _ in 0..10 {
78        step(&mut area, &mut rows);
79    }
80
81    resource_value(&area)
82}
83
84/// Compute generations until a cycle is detected.
85pub fn part2(input: &Key) -> u32 {
86    let mut area = input.area;
87    let mut rows = [0; 364];
88    let mut seen = FastMap::with_capacity(1_000);
89
90    for minute in 1.. {
91        step(&mut area, &mut rows);
92
93        if let Some(previous) = seen.insert(Key { area }, minute) {
94            // Find the index of the state after 1 billion repetitions.
95            let offset = 1_000_000_000 - previous;
96            let cycle_width = minute - previous;
97            let remainder = offset % cycle_width;
98            let target = previous + remainder;
99
100            let (result, _) = seen.iter().find(|&(_, &i)| i == target).unwrap();
101            return resource_value(&result.area);
102        }
103    }
104
105    unreachable!()
106}
107
108fn step(area: &mut [u64], rows: &mut [u64]) {
109    // Compute the horizontal sum of each column with its immediate neighbors.
110    for y in 0..50 {
111        // Shadow slices at correct starting offset for convenience. We pad `rows` on the top and
112        // bottom then shift index by 7 to avoid having to check for edge conditions.
113        let area = &area[7 * y..];
114        let rows = &mut rows[7 * (y + 1)..];
115
116        rows[0] = horizontal_sum(0, area[0], area[1]);
117        rows[1] = horizontal_sum(area[0], area[1], area[2]);
118        rows[2] = horizontal_sum(area[1], area[2], area[3]);
119        rows[3] = horizontal_sum(area[2], area[3], area[4]);
120        rows[4] = horizontal_sum(area[3], area[4], area[5]);
121        rows[5] = horizontal_sum(area[4], area[5], area[6]);
122        rows[6] = horizontal_sum(area[5], area[6], 0);
123
124        // The grid is 50 wide so the last 6 bytes in each row are unused and must be set to zero.
125        rows[6] &= EDGE;
126    }
127
128    for i in 0..350 {
129        // Sum of all adjacent trees and lumberyards, not including center acre.
130        let acre = area[i];
131        let sum = rows[i] + rows[i + 7] + rows[i + 14] - acre;
132
133        // Add 13 so that any values 3 and higher overflow into high nibble.
134        let mut to_tree = (sum & LOWER) + THIRTEENS;
135        // Clear low nibble as this is irrelevant.
136        to_tree &= UPPER;
137        // To become a tree, we must be open space.
138        to_tree &= !(acre | (acre << 4));
139        // Shift result back to low nibble.
140        to_tree >>= 4;
141
142        // Check for any values 3 or higher.
143        let mut to_lumberyard = ((sum >> 4) & LOWER) + THIRTEENS;
144        // Clear low nibble.
145        to_lumberyard &= UPPER;
146        // To become a lumberyard, we must already be a tree.
147        to_lumberyard &= acre << 4;
148        // Spread result to both high and low nibble. We will later XOR this to flip correct bits.
149        to_lumberyard |= to_lumberyard >> 4;
150
151        // We must be a lumberyard.
152        let mut to_open = acre & UPPER;
153        // Check for at least one adjacent tree.
154        to_open &= (sum & LOWER) + FIFTEENS;
155        // Check for at least one adjacent lumberyard.
156        to_open &= ((sum >> 4) & LOWER) + FIFTEENS;
157        // Flip bit as we will later XOR.
158        to_open ^= acre & UPPER;
159
160        // Flip relevant bits to transition to next state.
161        area[i] = acre ^ (to_tree | to_lumberyard | to_open);
162    }
163}
164
165/// Convenience method that also takes correct byte from left and right neighbors.
166#[inline]
167fn horizontal_sum(left: u64, middle: u64, right: u64) -> u64 {
168    (left << 56) + (middle >> 8) + middle + (middle << 8) + (right >> 56)
169}
170
171/// Each tree or lumberyard is represented by a single bit.
172fn resource_value(area: &[u64]) -> u32 {
173    let trees: u32 = area.iter().map(|n| (n & LOWER).count_ones()).sum();
174    let lumberyards: u32 = area.iter().map(|n| (n & UPPER).count_ones()).sum();
175    trees * lumberyards
176}
aoc/year2018/day18.rs

aoc/year2018/
day18.rs
