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

aoc/year2018/
day18.rs
