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 crate::util::grid::*;
17use crate::util::hash::*;
18use crate::util::point::*;
19use State::*;
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        Node { 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.
44struct BitSet {
45    bits: [u64; 190],
46}
47
48impl BitSet {
49    fn new() -> Self {
50        BitSet { bits: [0; 190] }
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: &BitSet) {
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    let grid = Grid::parse(input);
80    let width = grid.width;
81    let height = grid.height;
82
83    let graph = &mut Graph {
84        grid,
85        seen: Grid::new(width, height, [false; 2]),
86        state: Grid::new(width, height, Todo),
87        stack: Vec::new(),
88        nodes: Vec::new(),
89    };
90
91    let part_one = follow(graph, ORIGIN, RIGHT);
92    let mut part_two = part_one;
93
94    for x in 0..width {
95        part_two = part_two.max(follow(graph, Point::new(x, 0), DOWN));
96        part_two = part_two.max(follow(graph, Point::new(x, height - 1), UP));
97    }
98
99    for y in 0..height {
100        part_two = part_two.max(follow(graph, Point::new(0, y), RIGHT));
101        part_two = part_two.max(follow(graph, Point::new(width - 1, y), LEFT));
102    }
103
104    (part_one, part_two)
105}
106
107pub fn part1(input: &Input) -> u32 {
108    input.0
109}
110
111pub fn part2(input: &Input) -> u32 {
112    input.1
113}
114
115/// Starting from an edge, find either the first node marked by a splitter of any orientation or
116/// exit from another edge of the grid. If the node is not yet computed, then recursively compute
117/// the node and all descendants, caching the result to speed up future checks.
118///
119/// This does not mark paths in the grid to avoid corrupting potential future calculations.
120fn follow(graph: &mut Graph, mut position: Point, mut direction: Point) -> u32 {
121    let mut node = Node::new();
122
123    while graph.grid.contains(position) {
124        match graph.grid[position] {
125            // Retrieve cached value or compute recursively.
126            b'|' | b'-' => {
127                let index = match graph.state[position] {
128                    Todo => strong_connect(graph, position),
129                    Done(index) => index,
130                    OnStack(_) => unreachable!(),
131                };
132                node.tiles.union(&graph.nodes[index].tiles);
133                break;
134            }
135            // Mirrors change direction.
136            b'\\' => direction = Point::new(direction.y, direction.x),
137            b'/' => direction = Point::new(-direction.y, -direction.x),
138            // If we have already travelled on this path then this must be an exit from a splitter
139            // node already computed. The energized tiles can be at most equal so exit early.
140            _ => {
141                let index = (direction == LEFT || direction == RIGHT) as usize;
142                if graph.seen[position][index] {
143                    return 0;
144                }
145            }
146        }
147
148        node.tiles.insert(position);
149        position += direction;
150    }
151
152    node.tiles.size()
153}
154
155/// Traces the path of a beam until we hit the flat side of another splitter or exit the grid.
156fn beam(graph: &mut Graph, node: &mut Node, mut position: Point, mut direction: Point) {
157    while graph.grid.contains(position) {
158        match graph.grid[position] {
159            b'|' => {
160                // If we encounter the pointy edge of a splitter then this additional splitter is
161                // also part of this node. Nodes can contain multiple splitters in the same path.
162                if direction == UP || direction == DOWN {
163                    node.from.insert(position);
164                } else {
165                    node.to.insert(position);
166                    break;
167                }
168            }
169            b'-' => {
170                if direction == LEFT || direction == RIGHT {
171                    node.from.insert(position);
172                } else {
173                    node.to.insert(position);
174                    break;
175                }
176            }
177            // Mirrors change direction.
178            b'\\' => direction = Point::new(direction.y, direction.x),
179            b'/' => direction = Point::new(-direction.y, -direction.x),
180            // If we are travelling horizontally or vertically in the same tile where
181            // we have travelled in the same orientation before, then we're in a loop so break.
182            // Beams can cross perpendicularly without causing a cycle.
183            _ => {
184                let index = (direction == LEFT || direction == RIGHT) as usize;
185                if graph.seen[position][index] {
186                    break;
187                }
188                graph.seen[position][index] = true;
189            }
190        }
191
192        node.tiles.insert(position);
193        position += direction;
194    }
195}
196
197/// Tarjan's algorithm to find strongly connected components, e.g cycles in a directed graph.
198fn strong_connect(graph: &mut Graph, position: Point) -> usize {
199    // Push current index to stack and insert a dummy node to keep the vector index correct when
200    // processing children.
201    let index = graph.nodes.len();
202    graph.stack.push(index);
203    graph.nodes.push(Node::new());
204
205    // Find all tiles energized by this node, the splitters that are part of it (`from`) and the
206    // possible splitters that are children (`to`).
207    let mut node = Node::new();
208
209    if graph.grid[position] == b'|' {
210        beam(graph, &mut node, position, UP);
211        beam(graph, &mut node, position + DOWN, DOWN);
212    } else {
213        beam(graph, &mut node, position, LEFT);
214        beam(graph, &mut node, position + RIGHT, RIGHT);
215    }
216
217    // Mark all splitters belonging to this node as in progress.
218    node.from.iter().for_each(|&p| graph.state[p] = OnStack(index));
219
220    // If any children connect to a previous node then lowlink will become less than current index.
221    let mut lowlink = index;
222
223    for &next in &node.to {
224        match graph.state[next] {
225            Todo => lowlink = lowlink.min(strong_connect(graph, next)),
226            OnStack(other) => lowlink = lowlink.min(other),
227            Done(_) => (),
228        }
229    }
230
231    // We are the root of a cycle (possibly an independent component of one).
232    if lowlink == index {
233        // Merge all nodes in the cycle into this one.
234        while let Some(next) = graph.stack.pop()
235            && next != index
236        {
237            let other = &graph.nodes[next];
238            node.tiles.union(&other.tiles);
239            node.from.extend(&other.from);
240            node.to.extend(&other.to);
241        }
242
243        // Mark node as done.
244        node.from.iter().for_each(|&p| graph.state[p] = Done(index));
245
246        // Merge depduplicated children, removing self-references that point to this node.
247        for &next in node.to.difference(&node.from) {
248            if let Done(other) = graph.state[next] {
249                node.tiles.union(&graph.nodes[other].tiles);
250            }
251        }
252    }
253
254    // Replace dummy node with real thing.
255    graph.nodes[index] = node;
256    lowlink
257}
aoc/year2023/day16.rs

aoc/year2023/
day16.rs
