aoc/year2021/
day15.rs

1//! # Chiton
2//!
3//! Traversing a graph with different non-negative edge weights is a job for the classic
4//! [Djisktra'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 Djisktra 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 in 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 mut bytes = Vec::with_capacity(size * size);
30
31    raw.iter().for_each(|slice| bytes.extend_from_slice(slice));
32    bytes.iter_mut().for_each(|b| *b = b.to_decimal());
33
34    Square { size, bytes }
35}
36
37/// Search the regular size grid.
38pub fn part1(input: &Square) -> usize {
39    dijkstra(input)
40}
41
42/// Create an expanded grid then search.
43pub fn part2(input: &Square) -> usize {
44    let Square { size, bytes } = input;
45
46    let mut expanded = Square { size: 5 * size, bytes: vec![0; 25 * size * size] };
47
48    for (i, b) in bytes.iter().enumerate() {
49        let x1 = i % size;
50        let y1 = i / size;
51        let base = *b as usize;
52
53        for x2 in 0..5 {
54            for y2 in 0..5 {
55                let index = (5 * size) * (y2 * size + y1) + (x2 * size + x1);
56                expanded.bytes[index] = (1 + (base - 1 + x2 + y2) % 9) as u8;
57            }
58        }
59    }
60
61    dijkstra(&expanded)
62}
63
64/// Implementation of [Dijkstra's algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)
65/// without using the decrease-key functionality.
66fn dijkstra(square: &Square) -> usize {
67    let Square { size, bytes } = square;
68    let edge = size - 1;
69    let end = size * size - 1;
70
71    // Initialise our specialized priority queue with 10 vecs.
72    let mut todo: [Vec<u32>; 10] = from_fn(|_| Vec::with_capacity(1_000));
73    let mut cost = vec![u16::MAX; size * size];
74    let mut risk = 0;
75
76    // Start location and risk are both zero.
77    todo[0].push(0);
78    cost[0] = 0;
79
80    loop {
81        let i = risk % 10;
82
83        for j in 0..todo[i].len() {
84            let current = todo[i][j] as usize;
85            if current == end {
86                return risk;
87            }
88
89            let mut check = |next: usize| {
90                let next_cost = risk as u16 + bytes[next] as u16;
91                if next_cost < cost[next] {
92                    todo[(next_cost % 10) as usize].push(next as u32);
93                    cost[next] = next_cost;
94                }
95            };
96            let x = current % size;
97            let y = current / size;
98
99            if x > 0 {
100                check(current - 1);
101            }
102            if x < edge {
103                check(current + 1);
104            }
105            if y > 0 {
106                check(current - size);
107            }
108            if y < edge {
109                check(current + size);
110            }
111        }
112
113        todo[i].clear();
114        risk += 1;
115    }
116}
aoc/year2021/day15.rs

aoc/year2021/
day15.rs
