aoc/year2015/
day18.rs

1//! # Like a GIF For Your Yard
2//!
3//! To solve this efficiently we use a [SWAR](https://en.wikipedia.org/wiki/SWAR) approach,
4//! packing 16 lights into a `u64` taking 4 bits each. We calculate the next generation using no
5//! conditional statements with the following steps.
6//!
7//! 1. Pack the input bytes into register values that can be represented as hex digits.
8//!
9//! ```none
10//!     #...#    10001
11//!     .#.#. => 01010
12//!     ###.#    11101
13//! ```
14//!
15//! 2. Add left and right neighbors to each column horizontally, shifting in zeroes at the edge.
16//!
17//! ```none
18//!     11011
19//!     11211
20//!     23221
21//! ```
22//!
23//! 3. Add 3 rows together to give the total sum including the light itself:
24//!
25//! ```none
26//!     45443
27//! ```
28//!
29//! 4. Subtract the middle row to get neighbors only.
30//!
31//! ```none
32//!     44433
33//! ```
34//!
35//! 5. Apply the rules using only bitwise logic.
36//!
37//! Consider the binary representation of a 4 bit hex digit.
38//! * A cell stays on if it has 2 or 3 neigbours, binary `0010` or binary `0011`.
39//! * A cell turns on if it has exactly 3 neighbors, binary `0011`.
40//!
41//! If we `OR` the neighbor count with the current cell, either `0000` or `0001` then the
42//! binary representation of a lit cell will always be `0011`.
43//!
44//! Labelling the bits `abcd` then the next cell is `!a & !b & c & d`.
45type Lights = [[u64; 7]; 100];
46
47/// Pack the lights into 4 bits each in [big-endian order](https://en.wikipedia.org/wiki/Endianness).
48pub fn parse(input: &str) -> Lights {
49    let mut grid = default();
50
51    for (y, row) in input.lines().enumerate() {
52        for (x, col) in row.bytes().enumerate() {
53            let index = x / 16;
54            let offset = 4 * (15 - (x % 16));
55            let bit = (col & 1) as u64;
56            grid[y][index] |= bit << offset;
57        }
58    }
59
60    grid
61}
62
63pub fn part1(input: &Lights) -> u32 {
64    game_of_life(input, false)
65}
66
67pub fn part2(input: &Lights) -> u32 {
68    game_of_life(input, true)
69}
70
71fn game_of_life(input: &Lights, part_two: bool) -> u32 {
72    let mut grid = *input;
73    let mut temp = default();
74    let mut next = default();
75
76    for _ in 0..100 {
77        for y in 0..100 {
78            for x in 0..7 {
79                // Add left and right neighbors from this block.
80                let mut sum = grid[y][x] + (grid[y][x] >> 4) + (grid[y][x] << 4);
81
82                // Add immediate right or left neighbor from previous or next block.
83                if x > 0 {
84                    sum += grid[y][x - 1] << 60;
85                }
86                if x < 6 {
87                    sum += grid[y][x + 1] >> 60;
88                }
89
90                temp[y][x] = sum;
91            }
92        }
93
94        for y in 0..100 {
95            for x in 0..7 {
96                // Get neighbor count by summing the rows above and below the light
97                // then subtracting the light itself.
98                let mut sum = temp[y][x] - grid[y][x];
99
100                if y > 0 {
101                    sum += temp[y - 1][x];
102                }
103                if y < 99 {
104                    sum += temp[y + 1][x];
105                }
106
107                // Calculate the next generation with no conditional statements.
108                let a = sum >> 3;
109                let b = sum >> 2;
110                let c = sum >> 1;
111                let d = sum | grid[y][x];
112
113                next[y][x] = (!a & !b & c & d) & 0x1111111111111111;
114            }
115
116            // 100 = 16 * 6 + 4 = so only use the first 4 places of the last element.
117            next[y][6] &= 0x1111000000000000;
118        }
119
120        // Set corner lights to always on.
121        if part_two {
122            next[0][0] |= 1 << 60;
123            next[0][6] |= 1 << 48;
124            next[99][0] |= 1 << 60;
125            next[99][6] |= 1 << 48;
126        }
127
128        (grid, next) = (next, grid);
129    }
130
131    grid.iter().map(|row| row.iter().map(|n| n.count_ones()).sum::<u32>()).sum()
132}
133
134fn default() -> Lights {
135    [[0; 7]; 100]
136}
aoc/year2015/day18.rs

aoc/year2015/
day18.rs
