DEV Community

Cover image for Advent of Code 2023 - December 17th
Rob van der Leek
Rob van der Leek

Posted on

Advent of Code 2023 - December 17th

In this series, I'll share my progress with the 2023 version of Advent of Code.

Check the first post for a short intro to this series.

You can also follow my progress on GitHub.

December 17th

The puzzle of day 17 caused a big headache. In a way it's straightforward Dijkstra shortest path, but the path requirements really made me loose my mind (I resorted to Reddit for some guidance).

My pitfall for this puzzle: In the end the amount is code low (and could be much more concise with some refactorings), but it took me a long way to get there. The performance of the code is terrible since I'm not so familiar with priority queues in Python. Anyway, I want to forget this one as fast as possible.

Solution here, do not click if you want to solve the puzzle first yourself
#!/usr/bin/env python3

grid = []
with open('input.txt') as infile:
    lines = infile.readlines()
    for line in lines:
        grid.append([int(n) for n in line.strip()])

# right: 0, down: 1, left: 2, up: 3
def can_go(pos, direction, history, length):
    if pos[0] < 0 or pos[0] >= len(grid) or pos[1] < 0 or \
            pos[1] >= len(grid[0]):
        return False
    if history == -1:
        return True
    if length < 3:
        return direction == history:
    if length > 8 and direction == history:
        return False
    if direction == 0 and history == 2:
        return False
    if direction == 1 and history == 3:
        return False
    if direction == 3 and history == 1:
        return False
    if direction == 2 and history == 0:
        return False
    return True

min_loss = {}

def dijkstra():
    heads = [(0, (0, 0), -1, 0)]
    while True:
        heads.sort(key=lambda h: (h[0], h[2], h[3]), reverse=True)
        head = heads.pop()
        key = (head[1], head[2], head[3])
        loss = head[0]
        pos = head[1]
        history = head[2]
        length = head[3]
        if key in min_loss and min_loss[key] <= loss:
            continue
        if pos == (len(grid) - 1, len(grid[0]) - 1) and length >= 3:
            return head
        min_loss[key] = loss 
        right = (head[1][0], head[1][1] + 1)
        if can_go(right, 0, history, length):
            new_loss = loss + grid[right[0]][right[1]]
            new_length = length + 1 if history == 0 else 0
            heads.append((new_loss, right, 0, new_length))
        down = (head[1][0] + 1, head[1][1])
        if can_go(down, 1, history, length):
            new_loss = loss + grid[down[0]][down[1]]
            new_length = length + 1 if history == 1 else 0
            heads.append((new_loss, down, 1, new_length))
        up = (head[1][0] - 1, head[1][1])
        if can_go(up, 3, history, length):
            new_loss = loss + grid[up[0]][up[1]]
            new_length = length + 1 if history == 3 else 0
            heads.append((new_loss, up, 3, new_length))
        left = (head[1][0], head[1][1] - 1)
        if can_go(left, 2, history, length):
            new_loss = loss + grid[left[0]][left[1]]
            new_length = length + 1 if history == 2 else 0
            heads.append((new_loss, left, 2, new_length))

print(dijkstra())
Enter fullscreen mode Exit fullscreen mode

That's it! See you again tomorrow!

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

Top comments (0)

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay