Module aoc::year2015::day18

Like a GIF For Your Yard

To solve this efficiently we use a 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.

    #...#    10001
    .#.#. => 01010
    ###.#    11101

2. Add left and right neighbors to each column horizontally, shifting in zeroes at the edge.

    11011
    11211
    23221

3. Add 3 rows together to give the total sum including the light itself:

    45443

4. Subtract the middle row to get neighbors only.

    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.

Functions

• default 🔒
• game_of_life 🔒
• parse
  Pack the lights into 4 bits each in big-endian order.
• part1
• part2

Type Aliases

• Lights 🔒