Advent of Code 2023 Day 17
Day 17: Clumsy Crucible
https://adventofcode.com/2023/day/17
The lava starts flowing down to Metal Island.
There, elves are busy taking the lava to the factory in big crucibles (cups for molten stuff).
They want to get the crucibles to the factory as fast as possible to lose the least amount of heat.
Figuring out the ideal route to take is your job.
The elves prepared a map that list how much heat is lost if you enter a tile. The starting location is in the top-left, the ending location in the bottom-right.
An example input looks like this:
2413432311323321545353562332552456542543446585845452454665786753614385987984544457876987766363787797965346549679868874564679986453122468686556325465488877354322674655533
Parsing
A 2D list of digits:
fn parse(input: &str) -> Vec<Vec<u8>> {input.lines().map(|line| {line.chars().map(|c| c.to_digit(10).unwrap() as u8).collect()}).collect()}
Part 1
The crucibles are unwieldy, pretty hard to “drive” (is that the right word? Hard to move.)
- They cannot move in a straight line for more than 3 tiles.
- They cannot reverse direction
The question asks for the minimum amount of heatloss when you reach the destination.
This is a shortest path problem, time to pull out the Dijkstra.
Helpers
To do some Dijkstra’s algorithm, I need a priority queue.
In Rust, I’ll use a BinaryHeap
for this.
Some skeleton/pseudo-code I want to work towards:
pub fn part_1(input: &str) -> u32 {let grid = parse(input);let goal = Coord {row: grid.len() - 1,col: grid[0].len() - 1,};let mut pq = BinaryHeap::new();// push the initial 2 directions the crucible can move onto the pqpq.push(initial_crucibles);// loop until the goal is reached, or the pq is emptywhile let Some(crucible) = pq.pop() {if crucible.pos == goal {return crucible.cost;}// determine the next possible crucibles and push them onto the pqfor successor in node.successors(&grid) {pq.push(successor);}}}
The things I’ll push onto that queue and pop off it are my own data structures, Crucible
:
struct Crucible {cost: u32,pos: Coord,dir: Direction,moves_in_dir: u8,}
The position it has is tracked by a Coord
:
struct Coord {row: usize,col: usize,}
The direction the crucible is moving in is a Direction
:
enum Direction {Up,Down,Left,Right,}
Now, to handle the soring of the Crucible
s in that priority queue, I specified how they should be sorted, by cost, from low to high.
That way, every time I pop from the queue, I get the crucible with the lowest cost.
// The priority queue holds Crucible// We define an ordering trait so the one with the lowest cost gets popped from the pq first.// We do this by flipping the ordering on cost (comparing "other to self" instead of "self to other")// that way, nodes with a lower cost will compare as Ordering::Greater, and get sent to the front of the pqimpl Ord for Crucible {fn cmp(&self, other: &Self) -> Ordering {other.cost.cmp(&self.cost)}}// Ensure partialOrd is consistent with Ord. From the docs:// > If Ord is also implemented for Self and Rhs, it must also be consistent with partial_cmp (see the documentation of that trait for the exact requirements).// > It’s easy to accidentally make them disagree by deriving some of the traits and manually implementing others.// tl;dr: implement PartialOrd in terms of the Ord we just specified to ensure correctness. Letting it be automatically determined is wrong sometimes.impl PartialOrd for Crucible {fn partial_cmp(&self, other: &Self) -> Option<Ordering> {Some(self.cmp(other))}}
The next step is the function that determines the successors (a fancy word for the next possible crucibles). It tries to move in every direction, and only does so if the rules from the question pass:
impl Crucible {fn successors(&self, grid: &Vec<Vec<u8>>) -> Vec<Self> {let rows = grid.len();let cols = grid[0].len();let mut successors = Vec::new();for dir in [Direction::Up,Direction::Down,Direction::Left,Direction::Right,] {if self.dir == dir && self.moves_in_dir == 3 {// already moved 3 tiles in a straight line, can't move furthercontinue;}if self.dir.opposite() == dir {// can't move in opposite directioncontinue;}// simulate a move inside the boundsif let Some(pos) = self.pos.forward(&dir, rows, cols) {// calculate the total cost to get to that neighbour// it's the total cost to get to the current node + the cost to travel to the neighbourlet cost = self.cost + grid[pos.row][pos.col] as u32;// increment straight_moves if we went straight, else we moved 1 tile in the current directionlet moves_in_dir = if self.dir == dir {self.moves_in_dir + 1} else {1};successors.push(Crucible {pos,cost,dir,moves_in_dir,})}}successors}}
This handles some of the rules crucibles must adhere to, like:
- Not moving more than 3 tiles in a straight line
- Not reversing direction
The not reversing direction rule uses another helper:
impl Direction {fn opposite(&self) -> Self {match self {Direction::Up => Direction::Down,Direction::Down => Direction::Up,Direction::Left => Direction::Right,Direction::Right => Direction::Left,}}}
It also makes sure a crucible doesn’t go off the map with that forward
helper, it only adds a new crucible if it’s inside the grid.
That’s because that forward
helper only returns a valid coordinate if it’s inside the grid:
impl Coord {fn forward(&self, dir: &Direction, rows: usize, cols: usize) -> Option<Self> {let coord = match dir {Direction::Up if self.row > 0 => Coord {row: self.row - 1,col: self.col,},Direction::Down if self.row < (rows - 1) => Coord {row: self.row + 1,col: self.col,},Direction::Left if self.col > 0 => Coord {row: self.row,col: self.col - 1,},Direction::Right if self.col < (cols - 1) => Coord {row: self.row,col: self.col + 1,},_ => return None,};Some(coord)}}
Code
This worked, but went very slow, so I kept track of previous crucibles in a HashSet
.
Only tracking the Crucible
position is not enough, as it matters which direction the crucible is travelling in, and how far it already has in a straight line.
So every time I want to add a successor to the priority queue, I check if that (coord, dir, moves_in_dir)
triplet has already been seen.
If it hasn’t, I add that crucible to the queue, and that triplet to the seen
cache.
pub fn part_1(input: &str) -> u32 {let grid = parse(input);let goal = Coord {row: grid.len() - 1,col: grid[0].len() - 1,};let mut pq = BinaryHeap::new();let mut seen = HashSet::new();let right = Crucible {cost: grid[0][1] as u32,dir: Direction::Right,pos: Coord { row: 0, col: 1 },moves_in_dir: 1,};pq.push(right);let down = Crucible {cost: grid[1][0] as u32,dir: Direction::Down,pos: Coord { row: 1, col: 0 },moves_in_dir: 1,};pq.push(down);while let Some(crucible) = pq.pop() {if crucible.pos == goal {return crucible.cost;}for crucible in crucible.successors(&grid) {if seen.insert((crucible.pos, crucible.dir, crucible.moves_in_dir)) {pq.push(crucible);}}}panic!("No path found")}
Part 2
It’s not going fast enough, to remedy this, the elves brought bigger crucibles, ultracrucibles.
They can move more lava, but are also even more unwieldy.
They need to move a minimum of 4 tiles in a single direction before they can turn or stop.
They can’t go further than 10 tiles in a single direction before they have to turn.
The question asks for the minimum amount of heatloss when you reach the destination.
Helpers
The nodes that go into the priority queue now are UltraCrucible
s:
struct UltraCrucible {cost: u32,pos: Coord,dir: Direction,moves_in_dir: u8,}
The same logic is used to order them:
impl Ord for UltraCrucible {fn cmp(&self, other: &Self) -> Ordering {other.cost.cmp(&self.cost)}}impl PartialOrd for UltraCrucible {fn partial_cmp(&self, other: &Self) -> Option<Ordering> {Some(self.cmp(other))}}
And now, for the part that is different between part1 and part2, the successors
:
impl UltraCrucible {fn successors(&self, grid: &Vec<Vec<u8>>) -> Vec<Self> {let rows = grid.len();let cols = grid[0].len();let mut successors = Vec::new();for dir in [Direction::Up,Direction::Down,Direction::Left,Direction::Right,] {// Once an ultra crucible starts moving in a direction, it needs to move a minimum of four blocks in that direction before it can turnif self.moves_in_dir < 4 && dir != self.dir {continue;}// an ultra crucible can move a maximum of ten consecutive blocks without turning.if self.dir == dir && self.moves_in_dir == 10 {// already moved 3 tiles in a straight line, can't move furthercontinue;}if self.dir.opposite() == dir {// can't move in opposite directioncontinue;}// simulate a move inside the boundsif let Some(pos) = self.pos.forward(&dir, rows, cols) {// calculate the total cost to get to that neighbour// it's the total cost to get to the current node + the cost to travel to the neighbourlet cost = self.cost + grid[pos.row][pos.col] as u32;// increment straight_moves if we went straight, else we moved 1 tile in the current directionlet moves_in_dir = if self.dir == dir {self.moves_in_dir + 1} else {1};successors.push(UltraCrucible {pos,cost,dir,moves_in_dir,})}}successors}}
This function encodes the movement rules laid out by the question.
The only other minor change is the check to see if the destination has been reached in the loop.
Since an UltraCrucible
can’t stop immediately, I added a check to see if it has been moving for at least 4 tiles.
Code
pub fn part_2(input: &str) -> u32 {let grid = parse(input);let goal = Coord {row: grid.len() - 1,col: grid[0].len() - 1,};let mut pq = BinaryHeap::new();let mut seen = HashSet::new();let right = UltraCrucible {cost: grid[0][1] as u32,dir: Direction::Right,pos: Coord { row: 0, col: 1 },moves_in_dir: 1,};pq.push(right);let down = UltraCrucible {cost: grid[1][0] as u32,dir: Direction::Down,pos: Coord { row: 1, col: 0 },moves_in_dir: 1,};pq.push(down);while let Some(ultra_crucible) = pq.pop() {if ultra_crucible.pos == goal && ultra_crucible.moves_in_dir >= 4 {return ultra_crucible.cost;}for ultra_crucible in ultra_crucible.successors(&grid) {if seen.insert((ultra_crucible.pos,ultra_crucible.dir,ultra_crucible.moves_in_dir,)) {pq.push(ultra_crucible);}}}panic!("No path found")}
Final code
1use std::{2 cmp::Ordering,3 collections::{BinaryHeap, HashSet},4};56#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy)]7struct Coord {8 row: usize,9 col: usize,10}1112impl Coord {13 fn forward(&self, dir: &Direction, rows: usize, cols: usize) -> Option<Self> {14 let coord = match dir {15 Direction::Up if self.row > 0 => Coord {16 row: self.row - 1,17 col: self.col,18 },19 Direction::Down if self.row < (rows - 1) => Coord {20 row: self.row + 1,21 col: self.col,22 },23 Direction::Left if self.col > 0 => Coord {24 row: self.row,25 col: self.col - 1,26 },27 Direction::Right if self.col < (cols - 1) => Coord {28 row: self.row,29 col: self.col + 1,30 },31 _ => return None,32 };33 Some(coord)34 }35}3637#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy)]38enum Direction {39 Up,40 Down,41 Left,42 Right,43}4445impl Direction {46 fn opposite(&self) -> Self {47 match self {48 Direction::Up => Direction::Down,49 Direction::Down => Direction::Up,50 Direction::Left => Direction::Right,51 Direction::Right => Direction::Left,52 }53 }54}5556#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]57struct Crucible {58 cost: u32,59 pos: Coord,60 dir: Direction,61 moves_in_dir: u8,62}6364// The priority queue holds Nodes65// We define an ordering trait so the one with the lowest cost gets popped from the pq first.66// We do this by flipping the ordering on cost (comparing "other to self" instead of "self to other")67// that way, nodes with a lower cost will compare as Ordering::Greater, and get sent to the front of the pq68impl Ord for Crucible {69 fn cmp(&self, other: &Self) -> Ordering {70 other.cost.cmp(&self.cost)71 }72}7374// Ensure partialOrd is consistent with Ord. If you #[derive(PartialOrd)] this it might not be the same as that implementation uses a top-down ordering on the Node struct fields75// in this case, it would order by idx first (as that field occurs first in the source code where Node is defined) and would not be consistent.76// From the docs:77// > If Ord is also implemented for Self and Rhs, it must also be consistent with partial_cmp (see the documentation of that trait for the exact requirements).78// > It’s easy to accidentally make them disagree by deriving some of the traits and manually implementing others.79impl PartialOrd for Crucible {80 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {81 Some(self.cmp(other))82 }83}8485impl Crucible {86 fn successors(&self, grid: &Vec<Vec<u8>>) -> Vec<Self> {87 let rows = grid.len();88 let cols = grid[0].len();8990 let mut successors = Vec::new();91 for dir in [92 Direction::Up,93 Direction::Down,94 Direction::Left,95 Direction::Right,96 ] {97 if self.dir == dir && self.moves_in_dir == 3 {98 // already moved 3 tiles in a straight line, can't move further99 continue;100 }101 if self.dir.opposite() == dir {102 // can't move in opposite direction103 continue;104 }105 // simulate a move inside the bounds106 if let Some(pos) = self.pos.forward(&dir, rows, cols) {107 // calculate the total cost to get to that neighbour108 // it's the total cost to get to the current node + the cost to travel to the neighbour109 let cost = self.cost + grid[pos.row][pos.col] as u32;110111 // increment straight_moves if we went straight, else we moved 1 tile in the current direction112 let moves_in_dir = if self.dir == dir {113 self.moves_in_dir + 1114 } else {115 1116 };117118 successors.push(Crucible {119 pos,120 cost,121 dir,122 moves_in_dir,123 })124 }125 }126127 successors128 }129}130131fn parse(input: &str) -> Vec<Vec<u8>> {132 input133 .lines()134 .map(|line| {135 line.chars()136 .map(|c| c.to_digit(10).unwrap() as u8)137 .collect()138 })139 .collect()140}141142pub fn part_1(input: &str) -> u32 {143 let grid = parse(input);144 let goal = Coord {145 row: grid.len() - 1,146 col: grid[0].len() - 1,147 };148149 let mut pq = BinaryHeap::new();150 let mut seen = HashSet::new();151152 let right = Crucible {153 cost: grid[0][1] as u32,154 dir: Direction::Right,155 pos: Coord { row: 0, col: 1 },156 moves_in_dir: 1,157 };158 pq.push(right);159160 let down = Crucible {161 cost: grid[1][0] as u32,162 dir: Direction::Down,163 pos: Coord { row: 1, col: 0 },164 moves_in_dir: 1,165 };166 pq.push(down);167168 while let Some(crucible) = pq.pop() {169 if crucible.pos == goal {170 return crucible.cost;171 }172 for crucible in crucible.successors(&grid) {173 if seen.insert((crucible.pos, crucible.dir, crucible.moves_in_dir)) {174 pq.push(crucible);175 }176 }177 }178179 panic!("No path found")180}181182#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]183struct UltraCrucible {184 cost: u32,185 pos: Coord,186 dir: Direction,187 moves_in_dir: u8,188}189190impl Ord for UltraCrucible {191 fn cmp(&self, other: &Self) -> Ordering {192 other.cost.cmp(&self.cost)193 }194}195196impl PartialOrd for UltraCrucible {197 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {198 Some(self.cmp(other))199 }200}201202impl UltraCrucible {203 fn successors(&self, grid: &Vec<Vec<u8>>) -> Vec<Self> {204 let rows = grid.len();205 let cols = grid[0].len();206207 let mut successors = Vec::new();208 for dir in [209 Direction::Up,210 Direction::Down,211 Direction::Left,212 Direction::Right,213 ] {214 // Once an ultra crucible starts moving in a direction, it needs to move a minimum of four blocks in that direction before it can turn215 if self.moves_in_dir < 4 && dir != self.dir {216 continue;217 }218 // an ultra crucible can move a maximum of ten consecutive blocks without turning.219 if self.dir == dir && self.moves_in_dir == 10 {220 // already moved 3 tiles in a straight line, can't move further221 continue;222 }223 if self.dir.opposite() == dir {224 // can't move in opposite direction225 continue;226 }227 // simulate a move inside the bounds228 if let Some(pos) = self.pos.forward(&dir, rows, cols) {229 // calculate the total cost to get to that neighbour230 // it's the total cost to get to the current node + the cost to travel to the neighbour231 let cost = self.cost + grid[pos.row][pos.col] as u32;232233 // increment straight_moves if we went straight, else we moved 1 tile in the current direction234 let moves_in_dir = if self.dir == dir {235 self.moves_in_dir + 1236 } else {237 1238 };239240 successors.push(UltraCrucible {241 pos,242 cost,243 dir,244 moves_in_dir,245 })246 }247 }248249 successors250 }251}252253pub fn part_2(input: &str) -> u32 {254 let grid = parse(input);255 let goal = Coord {256 row: grid.len() - 1,257 col: grid[0].len() - 1,258 };259260 let mut pq = BinaryHeap::new();261 let mut seen = HashSet::new();262263 let right = UltraCrucible {264 cost: grid[0][1] as u32,265 dir: Direction::Right,266 pos: Coord { row: 0, col: 1 },267 moves_in_dir: 1,268 };269 pq.push(right);270271 let down = UltraCrucible {272 cost: grid[1][0] as u32,273 dir: Direction::Down,274 pos: Coord { row: 1, col: 0 },275 moves_in_dir: 1,276 };277 pq.push(down);278279 while let Some(ultra_crucible) = pq.pop() {280 if ultra_crucible.pos == goal && ultra_crucible.moves_in_dir >= 4 {281 return ultra_crucible.cost;282 }283 for ultra_crucible in ultra_crucible.successors(&grid) {284 if seen.insert((285 ultra_crucible.pos,286 ultra_crucible.dir,287 ultra_crucible.moves_in_dir,288 )) {289 pq.push(ultra_crucible);290 }291 }292 }293294 panic!("No path found")295}
Series navigation for: Advent of Code 2023