aoc/year2023/
day16.rs

1//! # The Floor Will Be Lava
2//!
3//! Each `-` or `|` splitter is a node in a graph connected by the light beams. Although each
4//! splitter emits two beams the graph is not a binary tree. There can be cycles between splitters
5//! and beams can also leave the grid.
6//!
7//! To speed things up
8//! [Tarjan's algorithm](https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm)
9//! is used to find cycles in the graph, then the energized tiles are cached in reverse topological
10//! order. As some cycles contain about half the total splitters in the grid, this results in a
11//! significant savings.
12//!
13//! A specialized bit set is used to cache the energized tiles. Each input is 110 x 110 tiles,
14//! needing 12,100 bits or 190 `u64`s to store the grid. Bitwise logic allows merging bitsets
15//! and counting the number of elements very quickly.
16use self::State::*;
17use crate::util::grid::*;
18use crate::util::hash::*;
19use crate::util::point::*;
20
21type Input = (u32, u32);
22
23struct Graph {
24    grid: Grid<u8>,
25    seen: Grid<[bool; 2]>,
26    state: Grid<State>,
27    stack: Vec<usize>,
28    nodes: Vec<Node>,
29}
30
31struct Node {
32    tiles: BitSet,
33    from: FastSet<Point>,
34    to: FastSet<Point>,
35}
36
37impl Node {
38    fn new() -> Self {
39        Self { tiles: BitSet::new(), from: FastSet::new(), to: FastSet::new() }
40    }
41}
42
43/// Fixed size bitset large enough to store the entire 110 x 110 grid plus border.
44struct BitSet {
45    bits: [u64; 196],
46}
47
48impl BitSet {
49    fn new() -> Self {
50        Self { bits: [0; 196] }
51    }
52
53    fn insert(&mut self, position: Point) {
54        let index = (110 * position.y + position.x) as usize;
55        let base = index / 64;
56        let offset = index % 64;
57        self.bits[base] |= 1 << offset;
58    }
59
60    fn union(&mut self, other: &Self) {
61        self.bits.iter_mut().zip(&other.bits).for_each(|(a, b)| *a |= b);
62    }
63
64    fn size(&self) -> u32 {
65        self.bits.iter().map(|&b| b.count_ones()).sum()
66    }
67}
68
69/// Used by Tarjan's algorithm.
70#[derive(Clone, Copy)]
71enum State {
72    Todo,
73    OnStack(usize),
74    Done(usize),
75}
76
77/// Computes both parts together in order to reuse cached results.
78pub fn parse(input: &str) -> Input {
79    // A newline border allows us to avoid boundary checks.
80    let grid = Grid::parse_with_border(input);
81    let width = grid.width;
82    let height = grid.height;
83
84    let graph = &mut Graph {
85        grid,
86        seen: Grid::new(width, height, [false; 2]),
87        state: Grid::new(width, height, Todo),
88        stack: Vec::new(),
89        nodes: Vec::new(),
90    };
91
92    let part_one = follow(graph, Point::new(1, 1), RIGHT);
93    let mut part_two = part_one;
94
95    // The newline border is asymmetric: the right border is implicit thanks to wraparound.
96    for x in 1..width {
97        part_two = part_two.max(follow(graph, Point::new(x, 1), DOWN));
98        part_two = part_two.max(follow(graph, Point::new(x, height - 2), UP));
99    }
100
101    for y in 1..height - 1 {
102        part_two = part_two.max(follow(graph, Point::new(1, y), RIGHT));
103        part_two = part_two.max(follow(graph, Point::new(width - 1, y), LEFT));
104    }
105
106    (part_one, part_two)
107}
108
109pub fn part1(input: &Input) -> u32 {
110    input.0
111}
112
113pub fn part2(input: &Input) -> u32 {
114    input.1
115}
116
117/// Starting from an edge, find either the first node marked by a splitter of any orientation or
118/// exit from another edge of the grid. If the node is not yet computed, then recursively compute
119/// the node and all descendants, caching the result to speed up future checks.
120///
121/// This does not mark paths in the grid to avoid corrupting potential future calculations.
122fn follow(graph: &mut Graph, mut position: Point, mut direction: Point) -> u32 {
123    let mut node = Node::new();
124
125    loop {
126        match graph.grid[position] {
127            // A newline border ends the path.
128            b'\n' => break,
129            // Retrieve cached value or compute recursively.
130            b'|' | b'-' => {
131                let index = match graph.state[position] {
132                    Todo => strong_connect(graph, position),
133                    Done(index) => index,
134                    OnStack(_) => unreachable!(),
135                };
136                node.tiles.union(&graph.nodes[index].tiles);
137                break;
138            }
139            // Mirrors change direction.
140            b'\\' => direction = Point::new(direction.y, direction.x),
141            b'/' => direction = Point::new(-direction.y, -direction.x),
142            // If we have already travelled on this path then this must be an exit from a splitter
143            // node already computed. The energized tiles can be at most equal so exit early.
144            _ => {
145                let index = (direction == LEFT || direction == RIGHT) as usize;
146                if graph.seen[position][index] {
147                    return 0;
148                }
149            }
150        }
151
152        node.tiles.insert(position);
153        position += direction;
154    }
155
156    node.tiles.size()
157}
158
159/// Traces the path of a beam until we hit the flat side of another splitter or exit the grid.
160fn beam(graph: &mut Graph, node: &mut Node, mut position: Point, mut direction: Point) {
161    loop {
162        match graph.grid[position] {
163            // A newline border ends the path.
164            b'\n' => break,
165            b'|' => {
166                // If we encounter the pointy edge of a splitter then this additional splitter is
167                // also part of this node. Nodes can contain multiple splitters in the same path.
168                if direction == UP || direction == DOWN {
169                    node.from.insert(position);
170                } else {
171                    node.to.insert(position);
172                    break;
173                }
174            }
175            b'-' => {
176                if direction == LEFT || direction == RIGHT {
177                    node.from.insert(position);
178                } else {
179                    node.to.insert(position);
180                    break;
181                }
182            }
183            // Mirrors change direction.
184            b'\\' => direction = Point::new(direction.y, direction.x),
185            b'/' => direction = Point::new(-direction.y, -direction.x),
186            // If we are travelling horizontally or vertically in the same tile where
187            // we have travelled in the same orientation before, then we're in a loop so break.
188            // Beams can cross perpendicularly without causing a cycle.
189            _ => {
190                let index = (direction == LEFT || direction == RIGHT) as usize;
191                if graph.seen[position][index] {
192                    break;
193                }
194                graph.seen[position][index] = true;
195            }
196        }
197
198        node.tiles.insert(position);
199        position += direction;
200    }
201}
202
203/// Tarjan's algorithm to find strongly connected components, e.g. cycles in a directed graph.
204fn strong_connect(graph: &mut Graph, position: Point) -> usize {
205    // Push current index to stack and insert a dummy node to keep the vector index correct when
206    // processing children.
207    let index = graph.nodes.len();
208    graph.stack.push(index);
209    graph.nodes.push(Node::new());
210
211    // Find all tiles energized by this node, the splitters that are part of it (`from`) and the
212    // possible splitters that are children (`to`).
213    let mut node = Node::new();
214
215    if graph.grid[position] == b'|' {
216        beam(graph, &mut node, position, UP);
217        beam(graph, &mut node, position + DOWN, DOWN);
218    } else {
219        beam(graph, &mut node, position, LEFT);
220        beam(graph, &mut node, position + RIGHT, RIGHT);
221    }
222
223    // Mark all splitters belonging to this node as in progress.
224    node.from.iter().for_each(|&p| graph.state[p] = OnStack(index));
225
226    // If any children connect to a previous node then lowlink will become less than current index.
227    let mut lowlink = index;
228
229    for &next in &node.to {
230        match graph.state[next] {
231            Todo => lowlink = lowlink.min(strong_connect(graph, next)),
232            OnStack(other) => lowlink = lowlink.min(other),
233            Done(_) => (),
234        }
235    }
236
237    // We are the root of a cycle (possibly an independent component of one).
238    if lowlink == index {
239        // Merge all nodes in the cycle into this one.
240        while let Some(next) = graph.stack.pop()
241            && next != index
242        {
243            let other = &graph.nodes[next];
244            node.tiles.union(&other.tiles);
245            node.from.extend(&other.from);
246            node.to.extend(&other.to);
247        }
248
249        // Mark node as done.
250        node.from.iter().for_each(|&p| graph.state[p] = Done(index));
251
252        // Merge deduplicated children, removing self-references that point to this node.
253        for &next in node.to.difference(&node.from) {
254            if let Done(other) = graph.state[next] {
255                node.tiles.union(&graph.nodes[other].tiles);
256            }
257        }
258    }
259
260    // Replace dummy node with real thing.
261    graph.nodes[index] = node;
262    lowlink
263}
aoc/year2023/day16.rs

aoc/year2023/
day16.rs
