aoc 15 part 1

mail@pastecode.io avatar
unknown
python
2 years ago
1.3 kB
4
Indexable
Never
import sys
import queue

def main(input_file=sys.stdin, output_file=sys.stdout):
    risk_level = []

    for row in input_file.readlines():
        risk_level.append([int(x) for x in list(row.strip())])

    n = len(risk_level)

    # print(risk_level)

    # Dijkstra

    # Holds pairs of total distance, coordinate
    q = queue.PriorityQueue()
    visited = set()

    q.put((0, (0, 0)))
    while not q.empty():
        next_dist, next_co = q.get()
        # print(next_dist, next_co)
        if next_co in visited:
            continue
        visited.add(next_co)

        # print(next_dist, next_co)
        if next_co == (n-1, n-1):
            output_file.write(str(next_dist))
            return

        children = []
        next_x, next_y = next_co
        if next_x - 1 >= 0:
            children.append((next_x-1, next_y))
        if next_x + 1 < n:
            children.append((next_x+1, next_y))
        if next_y - 1 >= 0:
            children.append((next_x, next_y-1))
        if next_y + 1 < n:
            children.append((next_x, next_y+1))

        for child_co in children:
            if child_co not in visited:
                c_x, c_y = child_co
                q.put((risk_level[c_x][c_y] + next_dist, child_co))


if __name__ == "__main__":
    main()