aoc/year2021/
day15.rs

1//! # Chiton
2//!
3//! Traversing a graph with different non-negative edge weights is a job for the classic
4//! [Dijkstra's algorithm](https://www.redblobgames.com/pathfinding/a-star/introduction.html),
5//! explained really well in the linked blog post.
6//!
7//! To speed things up we use a trick. Classic Dijkstra uses a generic priority queue that
8//! can be implemented in Rust using a [`BinaryHeap`]. However the total cost follows a strictly
9//! increasing order in a constrained range of values, so we can use a much faster single purpose
10//! data structure instead.
11//!
12//! The maximum possible increase in risk is 9, so we create an array of 10 `vec`s. The current
13//! list of items to process is at `risk % 10` and each new item is added at `risk % 10 + new_cost`.
14//! Once we have processed the current risk level we clear the vec to avoid having to reallocate
15//! memory.
16//!
17//! [`BinaryHeap`]: std::collections::BinaryHeap
18use crate::util::parse::*;
19use std::array::from_fn;
20
21pub struct Square {
22    size: usize,
23    bytes: Vec<u8>,
24}
25
26pub fn parse(input: &str) -> Square {
27    let raw: Vec<_> = input.lines().map(str::as_bytes).collect();
28    let size = raw.len();
29    let bytes = raw.into_iter().flatten().map(|b| b.to_decimal()).collect();
30    Square { size, bytes }
31}
32
33/// Search the regular size grid.
34pub fn part1(input: &Square) -> usize {
35    dijkstra(input)
36}
37
38/// Create an expanded grid then search.
39pub fn part2(input: &Square) -> usize {
40    let Square { size, bytes } = input;
41
42    let mut expanded = Square { size: 5 * size, bytes: vec![0; 25 * size * size] };
43
44    for (i, &b) in bytes.iter().enumerate() {
45        let x1 = i % size;
46        let y1 = i / size;
47        let base = b as usize;
48
49        for x2 in 0..5 {
50            for y2 in 0..5 {
51                let index = (5 * size) * (y2 * size + y1) + (x2 * size + x1);
52                expanded.bytes[index] = (1 + (base - 1 + x2 + y2) % 9) as u8;
53            }
54        }
55    }
56
57    dijkstra(&expanded)
58}
59
60/// Implementation of [Dijkstra's algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)
61/// without using the decrease-key functionality.
62fn dijkstra(square: &Square) -> usize {
63    let Square { size, bytes } = square;
64    let edge = size - 1;
65    let end = size * size - 1;
66
67    // Initialise our specialized priority queue with 10 vecs.
68    let mut todo: [Vec<u32>; 10] = from_fn(|_| Vec::with_capacity(1_000));
69    let mut cost = vec![u16::MAX; size * size];
70    let mut risk = 0;
71
72    // Start location and risk are both zero.
73    todo[0].push(0);
74    cost[0] = 0;
75
76    loop {
77        let i = risk % 10;
78
79        for j in 0..todo[i].len() {
80            let current = todo[i][j] as usize;
81            if current == end {
82                return risk;
83            }
84
85            let mut check = |next: usize| {
86                let next_cost = risk as u16 + bytes[next] as u16;
87                if next_cost < cost[next] {
88                    todo[(next_cost % 10) as usize].push(next as u32);
89                    cost[next] = next_cost;
90                }
91            };
92            let x = current % size;
93            let y = current / size;
94
95            if x > 0 {
96                check(current - 1);
97            }
98            if x < edge {
99                check(current + 1);
100            }
101            if y > 0 {
102                check(current - size);
103            }
104            if y < edge {
105                check(current + size);
106            }
107        }
108
109        todo[i].clear();
110        risk += 1;
111    }
112}
aoc/year2021/day15.rs

aoc/year2021/
day15.rs
