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 neighbors, 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 cell = grid[y][x];
81                let mut sum = cell + (cell >> 4) + (cell << 4);
82
83                // Add immediate right or left neighbor from previous or next block.
84                if x > 0 {
85                    sum += grid[y][x - 1] << 60;
86                }
87                if x < 6 {
88                    sum += grid[y][x + 1] >> 60;
89                }
90
91                temp[y][x] = sum;
92            }
93        }
94
95        for y in 0..100 {
96            for x in 0..7 {
97                // Get neighbor count by summing the rows above and below the light
98                // then subtracting the light itself.
99                let mut sum = temp[y][x] - grid[y][x];
100
101                if y > 0 {
102                    sum += temp[y - 1][x];
103                }
104                if y < 99 {
105                    sum += temp[y + 1][x];
106                }
107
108                // Calculate the next generation with no conditional statements.
109                let a = sum >> 3;
110                let b = sum >> 2;
111                let c = sum >> 1;
112                let d = sum | grid[y][x];
113
114                next[y][x] = (!a & !b & c & d) & 0x1111111111111111;
115            }
116
117            // 100 = 16 * 6 + 4 = so only use the first 4 places of the last element.
118            next[y][6] &= 0x1111000000000000;
119        }
120
121        // Set corner lights to always on.
122        if part_two {
123            next[0][0] |= 1 << 60;
124            next[0][6] |= 1 << 48;
125            next[99][0] |= 1 << 60;
126            next[99][6] |= 1 << 48;
127        }
128
129        (grid, next) = (next, grid);
130    }
131
132    grid.iter().flat_map(|row| row.iter()).map(|n| n.count_ones()).sum()
133}
134
135fn default() -> Lights {
136    [[0; 7]; 100]
137}
aoc/year2015/day18.rs

aoc/year2015/
day18.rs
