Module day18 

Like a GIF For Your Yard

To solve this efficiently we use a SWAR approach, packing 50 lights into a u64 taking 1 bit each, drawing inspiration from a solution from u/terje_wiig_mathisen/.

But rather than taking the bits consecutively, split the odd columns into one int and the even into another - that way, when it is time to check neighbors, all left and right neighbors of the odd lanes are already available with just one shift of all the even lanes, and vice versa. 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 binary digits, split into odd and even lanes. An extra empty row at the bottom reduces later special-casing.

                   .even .odd
            column: 024   135
    #...#.          101   000
    .#.##. =>       001   110
    ###.#.          111   100

2. Perform half-adder and full-adder computation of each bit with its vertical neighbors, using only bitwise logic. Just two bit-wise additions provides data for three 2-bit column sums, since the left and right neighbors are one bit apart in the opposite parity integer and already added in parallel. Visually, for cell e, we are computing a+b+c, d+f, and g+h+i of its neighbors.

                  .odd   .even
    ..adg..       ..d..  ..ag..
    ..beh..  =>   ..e..  ..bh..
    ..cfi..       ..f..  ..ci..
                l,m=d+f  j,k=a+b+c  n,o=g+h+i

3. Taking the 3 two-bit column sums learned in the last step, perform two more full-adders to form four new bits p, q, r, s, which we could add into a usual four-bit number, but which are good enough for our needs as-is. Bit s is set if there were an odd number of neighbors; bit p must be clear or we already know there are more than 3 neighbors; and exactly one of bits q and r must be set for the final 4-bit sum to have the second bit set.

    a d g
    b - h
  + c f i
  -------
      j k
      l m
  +   n o
  -------
    p q -
      r s

4. 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 neighbors, 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.

Using the bits as labelled above, the next cell is (e|s) & (q^r) & !p, masked back to the 50 bits per integer.

Structs

Row

100 lights of a single row, split by column parity.

Constants

LEFT_CORNER 🔒

MASK 🔒

RIGHT_CORNER 🔒

Functions

full_adder 🔒

game_of_life 🔒

half_adder 🔒

parse

Pack the lights into 1 bit each in big-endian order.

part1

part2