Module aoc::year2018::day18

Settlers of The North Pole

This problem is a cellular automaton similar to the well known Game of Life. To solve part two we look for a cycle then extrapolate forward a billion generations.

To efficiently compute the next generation a SWAR approach is used. The count of trees and lumberyards is packed into a u64 so that we can process 8 acres at a time. Lumberyards are stored in the high nibble of each byte and trees in the low nibble. For example:

    .#.#...|
    .....#|# => 11 11 21 11 21 02 21 02 => 0x1111211121022102
    .|..|...

The total number of adjacent trees or lumberyards is then calculated in two passes. First the horizontal sum of each row is computed by bit shifting left and right by 8. Then the vertical sum of 3 horizontal sums gives the total.

Bitwise logic then computes the next generation in batches of 8 acres at a time.

Structs

• Key
  New type wrapper so that we can use a custom hash function.

Constants

• EDGE 🔒
• FIFTEENS 🔒
• LOWER 🔒
• LUMBERYARD 🔒
• OPEN 🔒
  Bitwise logic galore.
• THIRTEENS 🔒
• TREE 🔒
• UPPER 🔒

Functions

• horizontal_sum 🔒
  Convenience method that also takes correct byte from left and right neighbors.
• parse
  Pack the input into an array of u64. The input is 50 acres wide, so requires ceil(50 / 8) = 7 elements for each row.
• part1
  Compute 10 generations.
• part2
  Compute generations until a cycle is detected.
• resource_value 🔒
  Each tree or lumberyard is represented by a single bit.
• step 🔒