[Day 17] Clumsy Crucible // Advent of Code 2023 (Python)

Clumsy Crucible (via DALL-E 3)

Advent of Code
The lava starts flowing rapidly once the Lava Production Facility is operational. As you leave, the reindeer offers you…adventofcode.com

---

Part One

The lava starts flowing rapidly once the Lava Production Facility is operational. As you leave, the reindeer offers you a parachute, allowing you to quickly reach Gear Island.

As you descend, your bird’s-eye view of Gear Island reveals why you had trouble finding anyone on your way up: half of Gear Island is empty, but the half below you is a giant factory city!

You land near the gradually-filling pool of lava at the base of your new lavafall. Lavaducts will eventually carry the lava throughout the city, but to make use of it immediately, Elves are loading it into large crucibles on wheels.

The crucibles are top-heavy and pushed by hand. Unfortunately, the crucibles become very difficult to steer at high speeds, and so it can be hard to go in a straight line for very long.

To get Desert Island the machine parts it needs as soon as possible, you’ll need to find the best way to get the crucible from the lava pool to the machine parts factory. To do this, you need to minimize heat loss while choosing a route that doesn’t require the crucible to go in a straight linefor too long.

Fortunately, the Elves here have a map (your puzzle input) that uses traffic patterns, ambient temperature, and hundreds of other parameters to calculate exactly how much heat loss can be expected for a crucible entering any particular city block.

For example:

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

Each city block is marked by a single digit that represents the amount of heat loss if the crucible enters that block. The starting point, the lava pool, is the top-left city block; the destination, the machine parts factory, is the bottom-right city block. (Because you already start in the top-left block, you don’t incur that block’s heat loss unless you leave that block and then return to it.)

Because it is difficult to keep the top-heavy crucible going in a straight line for very long, it can move at most three blocks in a single direction before it must turn 90 degrees left or right. The crucible also can’t reverse direction; after entering each city block, it may only turn left, continue straight, or turn right.

One way to minimize heat loss is this path:

2>>34^>>>1323
32v>>>35v5623
32552456v>>54
3446585845v52
4546657867v>6
14385987984v4
44578769877v6
36378779796v>
465496798688v
456467998645v
12246868655<v
25465488877v5
43226746555v>

This path never moves more than three consecutive blocks in the same direction and incurs a heat loss of only 102.

Directing the crucible from the lava pool to the machine parts factory, but not moving more than three consecutive blocks in the same direction, what is the least heat loss it can incur?

---

Yay! Lava Production Facility is operational!

Seems like now we need to find the best way to get the lava crucible from the lava pool to the machine parts factory!

We need to minimize heat loss by NOT taking a route with a long straight line as supposedly, crucibles become difficult to steer at high speed?! Well, that’s an interesting limitation.

So, to solve this, we are given a map with traffic patterns, ambient temperature and hundred of other params to help us calculate expected heatloss for the crucible while entering any city block, that look something like this:

💡Conditions to remember:

• Because you already start in the top-left block, you don’t incur that block’s heat loss unless you leave that block and then return to it!
• Because it is difficult to keep the top-heavy crucible going in a straight line for very long, it can move at most three blocks in a single direction before it must turn 90 degrees left or right.
• The crucible also can’t reverse direction; after entering each city block, it may only turn left, continue straight, or turn right.

So, let’s see for the given base case example, what can be a way to minimize the heat loss in the path?

This path never moves more than three consecutive blocks in the same direction. Here we incur a total heat loss of 102 units.

Now we need to find the answer similarly in the puzzle input. First things first, let’s write unit test for base case and try to fix that first?

Skelton code

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_17/clumsy_crucible.py"
Traceback (most recent call last):
  File "/Users/jmalik/github/advent-of-code-2023/day_17/clumsy_crucible.py", line 29, in <module>
    test_get_min_heat_loss_path()
  File "/Users/jmalik/github/advent-of-code-2023/day_17/clumsy_crucible.py", line 25, in test_get_min_heat_loss_path
    assert min_heat_loss == 102, f"Expected 102, got {min_heat_loss}"
AssertionError: Expected 102, got 0

[Done] exited with code=1 in 0.224 seconds

Let’s break down the problem!

It seems very similar to the last few problems, where we need to find path from top left to bottom right while obeying some rules and trying to minimize the heat loss!

The naive approach is to just explore all possible paths and then just pick the one with the lowest heat loss, but it will lead to a time complexity of: O(2^(N*M)) which means we will have:

• 2¹⁶⁹ combinations for our base test case here with 13 x 13 grid
• 2¹⁹⁸⁸¹ combinations for puzzle input with a 141 x 141 grid.

Fun fact? It is estimated that there may be ~2²⁵⁶ atoms in the known universe!

So, you can we the problem with the brute force approach here!

We can reduce our search space by a lot here by following the given constraints!

💭 One way that crosses my mind is to just do the DFS (Depth first search) by iterating through grid and store result in a var which will update whenever a path reaches bottom right like:

MIN_HEAT_LOSS = min(MIN_HEAT_LOSS, path_heat_loss)

And during iteration, on each choice just abandon any path that takes our path_heat_loss > MIN_HEAT_LOSS ! By doing this, we can greatly reduce our search space to opt for more efficient paths on each try!

Let’s write some code?

Shit tons of debugging ensued!

So, we have written functionally correct code, as I can see the output trending towards the intended result, but the problem is our stack keeps increasing as it backtracks for all possible directions! I wrote a small script to visualize the state of my MIN_HEAT_LOSS_PATH, take a look as it optimises the path quickly at start but then gets caught up:

It’s clear that my code as it backtracks, it tries to process same path again as again as in DFS it will keep looping into a subsection of those 2¹⁶⁹ combinations as we discussed above!

To avoid this, we can use memoization to store the minimum heat loss encountered at each node. If a path reaches the same node with a higher heat loss than previously recorded, we can just prune that path early.

Adding a simple 2D arraymemo of same size as grid just to keep a track of lowest_heat_loss seen at every iteration:

memo = [[float('inf') for _ in range(len(grid[0]))] for _ in range(len(grid))]

And we can add a simple check in our code to ensure that:

# if heat loss is already greater than min heat loss, continue
if next_heat_loss >= memo[next_row][next_col]:
  continue

Let’s run it? And…

New min heat loss: 107
# # # # . . # # # # . . .
. . . # # # # . . # . . .
. . . . . . . . . # # . .
. . . . . . . . . . # # .
. . . . . . . . . . . # .
. . . . . . . . . . . # #
. . . . . . . . . . . . #
. . . . . . . . . . . # #
. . . . . . . . . . . # .
. . . . . . . . . . . # #
. . . . . . . . . . . . #
. . . . . . . . . . . . #
. . . . . . . . . . . . #

Traceback (most recent call last):
  File "/Users/jmalik/github/advent-of-code-2023/day_17/clumsy_crucible.py", line 112, in <module>
    test_get_min_heat_loss_path()
  File "/Users/jmalik/github/advent-of-code-2023/day_17/clumsy_crucible.py", line 107, in test_get_min_heat_loss_path
    assert min_heat_loss == 102, f"Expected 102, got {min_heat_loss}"
AssertionError: Expected 102, got 107

[Done] exited with code=1 in 0.251 seconds

We are getting close! Atleast our runtime suggests that we have reduced our search space by a lot! We should get 102 but we are getting 107 here.

Again, some debugging to go:

.

.

.

Ah! Found it. Our memo is currently just storing 1 dimension of heat_loss but we can basically get to that cell from any direction which may lead to a shorter path overall! We need to store heat_loss for all 4 directions for each cell

# Initialize memoization table with dictionaries
memo = [[{d: float('inf') for d in Direction} for _ in range(len(grid[0]))] for _ in range(len(grid))]

And our memo condition will be modified to:

# Continue to the next direction if the new path is not better
if next_heat_loss > memo[next_row][next_col][direction]:
    continue
.
.
.
# Update memo
memo[next_row][next_col][direction] = next_heat_loss  

Let’s run the base test case?

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_17/clumsy_crucible.py"
✅ get_min_heat_loss_path() tests passed!

[Done] exited with code=0 in 0.726 seconds

Yas! Now, let’s load up our puzzle input?

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/tempCodeRunnerFile.python"
❗️ Minimum heat loss for crucible: XXX

[Done] exited with code=0 in 0.818 seconds

Let’s input the answer and….

⭐️

Our approach is quite messy! I am inclined to also explore this from BFS point of view in next part as I now feel we could have just used Djikstra's algo and called it a day by optimizing for low_heat_loss using a heapq.

---

Part Two

The crucibles of lava simply aren’t large enough to provide an adequate supply of lava to the machine parts factory. Instead, the Elves are going to upgrade to ultra crucibles.

Ultra crucibles are even more difficult to steer than normal crucibles. Not only do they have trouble going in a straight line, but they also have trouble turning!

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 (or even before it can stop at the end). However, it will eventually start to get wobbly: an ultra crucible can move a maximum of ten consecutive blocks without turning.

In the above example, an ultra crucible could follow this path to minimize heat loss:

2>>>>>>>>1323
32154535v5623
32552456v4254
34465858v5452
45466578v>>>>
143859879845v
445787698776v
363787797965v
465496798688v
456467998645v
122468686556v
254654888773v
432267465553v

In the above example, an ultra crucible would incur the minimum possible heat loss of 94.

Here’s another example:

111111111111
999999999991
999999999991
999999999991
999999999991

Sadly, an ultra crucible would need to take an unfortunate path like this one:

1>>>>>>>1111
9999999v9991
9999999v9991
9999999v9991
9999999v>>>>

This route causes the ultra crucible to incur the minimum possible heat loss of 71.

Directing the ultra crucible from the lava pool to the machine parts factory, what is the least heat loss it can incur?

---

So! We now have Ultra Crucibles!

It seems like we need to modifty our code to handle the new conditions:

• once it starts moving in a direction, it needs to move a minimum of four blocks in that direction before it can turn.
  • or even before it can stop at the end.
• can move a maximum of ten consecutive blocks without turning.

So, for the same example like in last part, here’s how the traversal will look like for an Ultra Crucible:

Now, using the similar thinking, all we need to change is blocks_before_turn and max_in_direction for the given crucible where for:

• normal crucible: blocks_before_turn=0, max_in_direction=3
• ultra crucible: blocks_before_turn=3, max_in_direction=10

We will try and go for the Dijkstra’s algorithm to solve this one! The idea is that I would like to create memo i.e. a nested dict of dicts which will store heat_loss for the given cell for all 4 directions!

Something like:

And to simplify our crucible turning, we can just define a map: ALLOWED_CRUCIBLE_TURNS to keep a track of:

ALLOWED_CRUCIBLE_TURNS = {
    Direction.RIGHT: [Direction.UP, Direction.DOWN],
    Direction.LEFT: [Direction.UP, Direction.DOWN],
    Direction.UP: [Direction.LEFT, Direction.RIGHT],
    Direction.DOWN: [Direction.LEFT, Direction.RIGHT]
}

Let’s write some code:

First, we initialize a nested defaultdict memo with sys.maxsize as the default value. This dictionary will store the minimum heat loss for each position and direction.

The use of sys.maxsize is a common trick in algorithms that need to find a minimum value - it’s the largest possible integer in Python, so any real heat loss will be less than this.

# Initialize heat loss dictionary with max values for each direction
memo = defaultdict(lambda: defaultdict(lambda: sys.maxsize))

Next, we initialize the heat loss for each direction at the starting position (0, 0) to be 0. This makes sense because we haven’t moved the crucible yet, so there’s no heat loss.

for direction in Direction:
  memo[(0, 0)][direction] = 0

We can then create a priority queue pq to manage the positions we need to explore. The priority queue is a perfect data structure for Dijkstra’s algorithm because it allows us to efficiently get the position with the smallest heat loss.

Our pq will store (heat_loss, position, dir_name) where it will be sorted wrt to heat_loss. We can seed the queue with all possible directions from the starting position i.e: RIGHT and DOWN:

# Initialize the priority queue for Dijkstra's algorithm
pq = PriorityQueue()

# seed pq with all possible directions from the starting position
pq.put((0, (0, 0), Direction.RIGHT.name))
pq.put((0, (0, 0), Direction.DOWN.name))

Now, all we need to do is:

• continually take the position with the smallest heat loss from the queue and explore new positions from there
• if the new position’s heat loss is less than the currently known minimum for that position and direction, we update the minimum and add the new position to the queue.

Once we are done with this, our memo will have min(heat_loss) from all 4 directions for each cell, something like:

For (12, 12), we have 4 values: 104, 104, 102, 102

All we need to do is, return the minimun value!

Let’s update our base case now for Part 2?

Let’s run it?

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_17/clumsy_crucible.py"
✅ get_min_heat_loss_path() tests passed for Crucible!
✅ get_min_heat_loss_path() tests passed for Ultra Crucible!

[Done] exited with code=0 in 0.227 seconds

We can now run for Part 2 for ultra crucible with values: blocks_before_turn=3, max_in_direction=10

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_17/clumsy_crucible.py"
❗️❗️ Minimum heat loss for Ultra Crucible: XXX

[Done] exited with code=0 in 1.337 seconds

We have an answer! Let’s input this in our answer box, and:

🌟

Here’s our final code till now, I am keeping inline comments in for the understanding of the reader:

# Day 17: Clumsy Crucible

import sys
from enum import Enum
from queue import PriorityQueue
from collections import defaultdict

# Define the Direction Enum for clarity and ease of use
class Direction(Enum):
    UP = (-1, 0)
    DOWN = (1, 0)
    LEFT = (0, -1)
    RIGHT = (0, 1)

# Define allowed turns for the crucible from each direction
ALLOWED_CRUCIBLE_TURNS = {
    Direction.RIGHT: [Direction.UP, Direction.DOWN],
    Direction.LEFT: [Direction.UP, Direction.DOWN],
    Direction.UP: [Direction.LEFT, Direction.RIGHT],
    Direction.DOWN: [Direction.LEFT, Direction.RIGHT],
}

# Function to find the minimum heat loss for moving the crucible
def find_min_heat_loss(grid, blocks_before_turn, max_in_direction):
    # Initialize distance dictionary with max values for each direction
    memo = defaultdict(lambda: defaultdict(lambda: sys.maxsize))

    for direction in Direction:
        memo[(0, 0)][direction] = 0

    # Initialize the priority queue for Dijkstra's algorithm
    pq = PriorityQueue()

    # seed pq with all possible directions from the starting position
    pq.put((0, (0, 0), Direction.RIGHT.name))
    pq.put((0, (0, 0), Direction.DOWN.name))

    while not pq.empty():
        heat_loss, position, dir_name = pq.get()
        direction = Direction[dir_name]  # Convert back to Direction enum

        # Skip if the current path's heat loss is not better than already known
        if heat_loss > memo[position][direction]:
            continue

        x, y = position
        for block in range(max_in_direction):
            # Move in the current direction
            dx, dy = direction.value
            x, y = x + dx, y + dy

            # Check if the new position is out of bounds
            if x < 0 or x >= len(grid[0]) or y < 0 or y >= len(grid):
                break

            # Accumulate heat loss
            heat_loss += grid[y][x]

            # Check if the crucible has moved the required blocks before turning
            if block < blocks_before_turn:
                continue

            # Explore new directions from the current position
            for new_dir in ALLOWED_CRUCIBLE_TURNS[direction]:
                if heat_loss < memo[(x, y)][new_dir]:
                    memo[(x, y)][new_dir] = heat_loss
                    pq.put((heat_loss, (x, y), new_dir.name))

    # Return the minimum heat loss to reach the bottom-right corner
    return min(memo[(len(grid[0]) - 1, len(grid) - 1)].values())

def parse_grid(input_str):
    return [[int(x) for x in line] for line in input_str.split("\n")]

def part_one():
    with open("day_17/input.txt", "r") as f:
        grid = parse_grid(f.read())
    min_heat_loss = find_min_heat_loss(grid, 0, 3)
    print(f"❗️ Minimum heat loss for Normal Crucible: {min_heat_loss}")

def part_two():
    with open("day_17/input.txt", "r") as f:
        grid = parse_grid(f.read())
    min_heat_loss = find_min_heat_loss(grid, 3, 10)
    print(f"❗️❗️ Minimum heat loss for Ultra Crucible: {min_heat_loss}")

def test_get_min_heat_loss_path_normal_crucible():
    input_str = """2413432311323
3215453535623
3255245654254
3446585845452
4546657867536
1438598798454
4457876987766
3637877979653
4654967986887
4564679986453
1224686865563
2546548887735
4322674655533"""
    grid = parse_grid(input_str)
    min_heat_loss = find_min_heat_loss(grid, 0, 3)
    assert min_heat_loss == 102, f"Expected 102, got {min_heat_loss}"
    print("✅ get_min_heat_loss_path() tests passed for Crucible!")

def test_get_min_heat_loss_path_ultra_crucible():
    input_str = """2413432311323
3215453535623
3255245654254
3446585845452
4546657867536
1438598798454
4457876987766
3637877979653
4654967986887
4564679986453
1224686865563
2546548887735
4322674655533"""
    grid = parse_grid(input_str)
    min_heat_loss = find_min_heat_loss(grid, 3, 10)
    assert min_heat_loss == 94, f"Expected 94, got {min_heat_loss}"
    print("✅ get_min_heat_loss_path() tests passed for Ultra Crucible!")

if __name__ == "__main__":
    test_get_min_heat_loss_path_normal_crucible()
    part_one()

    test_get_min_heat_loss_path_ultra_crucible()
    part_two()

---

p.s: I am deliberating not adding answers here so you can actually spend some time trying to understand how we solved the problem!

Feel free to checkout code on my Github repo and try to set it up and run on your machine 👇

GitHub - jatinkrmalik/advent-of-code-2023: Well, here’s my attempt to solve all 25 problems of…
Well, here’s my attempt to solve all 25 problems of Advent of Code 2023 with Python! 🎄 - GitHub …github.com