Advent of Code 2023 - December 17th

Advent of Code 2023 (25 Part Series)

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!

Advent of Code 2023 (25 Part Series)

原文链接：Advent of Code 2023 – December 17th

文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END