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:

input.txt

2413432311323
3215453535623
3255245654254
3446585845452
4546657867536
1438598798454
4457876987766
3637877979653
4654967986887
4564679986453
1224686865563
2546548887735
4322674655533

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 pq
    pq.push(initial_crucibles);

    // loop until the goal is reached, or the pq is empty
    while let Some(crucible) = pq.pop() {
        if crucible.pos == goal {
            return crucible.cost;
        }
        // determine the next possible crucibles and push them onto the pq
        for 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 Crucibles 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 pq
impl 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 further
                continue;
            }
            if self.dir.opposite() == dir {
                // can't move in opposite direction
                continue;
            }
            // simulate a move inside the bounds
            if 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 neighbour
                let 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 direction
                let 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.

day_17.rs

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 UltraCrucibles:

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 turn
            if 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 further
                continue;
            }
            if self.dir.opposite() == dir {
                // can't move in opposite direction
                continue;
            }
            // simulate a move inside the bounds
            if 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 neighbour
                let 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 direction
                let 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

day_17.rs

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

day_17.rs

1use std::{
2    cmp::Ordering,
3    collections::{BinaryHeap, HashSet},
4};
5
6#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy)]
7struct Coord {
8    row: usize,
9    col: usize,
10}
11
12impl 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}
36
37#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy)]
38enum Direction {
39    Up,
40    Down,
41    Left,
42    Right,
43}
44
45impl 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}
55
56#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
57struct Crucible {
58    cost: u32,
59    pos: Coord,
60    dir: Direction,
61    moves_in_dir: u8,
62}
63
64// The priority queue holds Nodes
65// 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 pq
68impl Ord for Crucible {
69    fn cmp(&self, other: &Self) -> Ordering {
70        other.cost.cmp(&self.cost)
71    }
72}
73
74// 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 fields
75// 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}
84
85impl Crucible {
86    fn successors(&self, grid: &Vec<Vec<u8>>) -> Vec<Self> {
87        let rows = grid.len();
88        let cols = grid[0].len();
89
90        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 further
99                continue;
100            }
101            if self.dir.opposite() == dir {
102                // can't move in opposite direction
103                continue;
104            }
105            // simulate a move inside the bounds
106            if let Some(pos) = self.pos.forward(&dir, rows, cols) {
107                // calculate the total cost to get to that neighbour
108                // it's the total cost to get to the current node + the cost to travel to the neighbour
109                let cost = self.cost + grid[pos.row][pos.col] as u32;
110
111                // increment straight_moves if we went straight, else we moved 1 tile in the current direction
112                let moves_in_dir = if self.dir == dir {
113                    self.moves_in_dir + 1
114                } else {
115                    1
116                };
117
118                successors.push(Crucible {
119                    pos,
120                    cost,
121                    dir,
122                    moves_in_dir,
123                })
124            }
125        }
126
127        successors
128    }
129}
130
131fn parse(input: &str) -> Vec<Vec<u8>> {
132    input
133        .lines()
134        .map(|line| {
135            line.chars()
136                .map(|c| c.to_digit(10).unwrap() as u8)
137                .collect()
138        })
139        .collect()
140}
141
142pub 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    };
148
149    let mut pq = BinaryHeap::new();
150    let mut seen = HashSet::new();
151
152    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);
159
160    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);
167
168    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    }
178
179    panic!("No path found")
180}
181
182#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
183struct UltraCrucible {
184    cost: u32,
185    pos: Coord,
186    dir: Direction,
187    moves_in_dir: u8,
188}
189
190impl Ord for UltraCrucible {
191    fn cmp(&self, other: &Self) -> Ordering {
192        other.cost.cmp(&self.cost)
193    }
194}
195
196impl PartialOrd for UltraCrucible {
197    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
198        Some(self.cmp(other))
199    }
200}
201
202impl UltraCrucible {
203    fn successors(&self, grid: &Vec<Vec<u8>>) -> Vec<Self> {
204        let rows = grid.len();
205        let cols = grid[0].len();
206
207        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 turn
215            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 further
221                continue;
222            }
223            if self.dir.opposite() == dir {
224                // can't move in opposite direction
225                continue;
226            }
227            // simulate a move inside the bounds
228            if let Some(pos) = self.pos.forward(&dir, rows, cols) {
229                // calculate the total cost to get to that neighbour
230                // it's the total cost to get to the current node + the cost to travel to the neighbour
231                let cost = self.cost + grid[pos.row][pos.col] as u32;
232
233                // increment straight_moves if we went straight, else we moved 1 tile in the current direction
234                let moves_in_dir = if self.dir == dir {
235                    self.moves_in_dir + 1
236                } else {
237                    1
238                };
239
240                successors.push(UltraCrucible {
241                    pos,
242                    cost,
243                    dir,
244                    moves_in_dir,
245                })
246            }
247        }
248
249        successors
250    }
251}
252
253pub 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    };
259
260    let mut pq = BinaryHeap::new();
261    let mut seen = HashSet::new();
262
263    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);
270
271    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);
278
279    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    }
293
294    panic!("No path found")
295}

Date

Last update

By

Tagged

Part of series

Older post

Newer post

Advent of Code 2023 Day 17

Day 17: Clumsy Crucible

Parsing

Part 1

Helpers

Code

Part 2

Helpers

Code

Final code