Module day16

The Floor Will Be Lava

Each - or | splitter is a node in a graph connected by the light beams. Although each splitter emits two beams the graph is not a binary tree. There can be cycles between splitters and beams can also leave the grid.

To speed things up Tarjan’s algorithm is used to find cycles in the graph, then the energized tiles are cached in reverse topological order. As some cycles contain about half the total splitters in the grid, this results in a significant savings.

A specialized bit set is used to cache the energized tiles. Each input is 110 x 110 tiles, needing 12,100 bits or 190 u64s to store the grid. Bitwise logic allows merging bitsets and counting the number of elements very quickly.

Structs

BitSet 🔒

Fixed size bitset large enough to store the entire 110 x 110 grid.

Graph 🔒

Node 🔒

Enums

State 🔒

Used by Tarjan’s algorithm.

Functions

beam 🔒

Traces the path of a beam until we hit the flat side of another splitter or exit the grid.

follow 🔒

Starting from an edge, find either the first node marked by a splitter of any orientation or exit from another edge of the grid. If the node is not yet computed, then recursively compute the node and all descendants, caching the result to speed up future checks.

parse

Computes both parts together in order to reuse cached results.

part1

part2

strong_connect 🔒

Tarjan’s algorithm to find strongly connected components, e.g cycles in a directed graph.

Type Aliases

Input 🔒