1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

//! # Like a GIF For Your Yard
//!
//! To solve this efficiently we use a [SWAR](https://en.wikipedia.org/wiki/SWAR) approach,
//! packing 16 lights into a `u64` taking 4 bits each. We calculate the next generation using no
//! conditional statements with the following steps.
//!
//! 1. Pack the input bytes into register values that can be represented as hex digits.
//!
//! ```none
//!     #...#    10001
//!     .#.#. => 01010
//!     ###.#    11101
//! ```
//!
//! 2. Add left and right neighbors to each column horizontally, shifting in zeroes at the edge.
//!
//! ```none
//!     11011
//!     11211
//!     23221
//! ```
//!
//! 3. Add 3 rows together to give the total sum including the light itself:
//!
//! ```none
//!     45443
//! ```
//!
//! 4. Subtract the middle row to get neighbors only.
//!
//! ```none
//!     44433
//! ```
//!
//! 5. Apply the rules using only bitwise logic.
//!
//! Consider the binary representation of a 4 bit hex digit.
//! * A cell stays on if it has 2 or 3 neigbours, binary `0010` or binary `0011`.
//! * A cell turns on if it has exactly 3 neighbors, binary `0011`.
//!
//! If we `OR` the neighbor count with the current cell, either `0000` or `0001` then the
//! binary representation of a lit cell will always be `0011`.
//!
//! Labelling the bits `abcd` then the next cell is `!a & !b & c & d`.
type Lights = [[u64; 7]; 100];

/// Pack the lights into 4 bits each in [big-endian order](https://en.wikipedia.org/wiki/Endianness).
pub fn parse(input: &str) -> Lights {
    let mut grid = default();

    for (y, row) in input.lines().enumerate() {
        for (x, col) in row.bytes().enumerate() {
            let index = x / 16;
            let offset = 4 * (15 - (x % 16));
            let bit = (col & 1) as u64;
            grid[y][index] |= bit << offset;
        }
    }

    grid
}

pub fn part1(input: &Lights) -> u32 {
    game_of_life(input, false)
}

pub fn part2(input: &Lights) -> u32 {
    game_of_life(input, true)
}

fn game_of_life(input: &Lights, part_two: bool) -> u32 {
    let mut grid = *input;
    let mut temp = default();
    let mut next = default();

    for _ in 0..100 {
        for y in 0..100 {
            for x in 0..7 {
                // Add left and right neighbors from this block.
                let mut sum = grid[y][x] + (grid[y][x] >> 4) + (grid[y][x] << 4);

                // Add immediate right or left neighbor from previous or next block.
                if x > 0 {
                    sum += grid[y][x - 1] << 60;
                }
                if x < 6 {
                    sum += grid[y][x + 1] >> 60;
                }

                temp[y][x] = sum;
            }
        }

        for y in 0..100 {
            for x in 0..7 {
                // Get neighbor count by summing the rows above and below the light
                // then subtracting the light itself.
                let mut sum = temp[y][x] - grid[y][x];

                if y > 0 {
                    sum += temp[y - 1][x];
                }
                if y < 99 {
                    sum += temp[y + 1][x];
                }

                // Calculate the next generation with no conditional statements.
                let a = sum >> 3;
                let b = sum >> 2;
                let c = sum >> 1;
                let d = sum | grid[y][x];

                next[y][x] = (!a & !b & c & d) & 0x1111111111111111;
            }

            // 100 = 16 * 6 + 4 = so only use the first 4 places of the last element.
            next[y][6] &= 0x1111000000000000;
        }

        // Set corner lights to always on.
        if part_two {
            next[0][0] |= 1 << 60;
            next[0][6] |= 1 << 48;
            next[99][0] |= 1 << 60;
            next[99][6] |= 1 << 48;
        }

        (grid, next) = (next, grid);
    }

    grid.iter().map(|row| row.iter().map(|n| n.count_ones()).sum::<u32>()).sum()
}

fn default() -> Lights {
    [[0; 7]; 100]
}