advent_of_code/2024/day16/main.py

import sys
import bisect
import copy
# import numpy as np
import os
from warnings import showwarning
sys.path.insert(1, os.path.abspath('../../'))
from python_tools.aoc_utils import *


def part_one(p, m):
    SCORES = {}
    SCORES[tuple([0, *p])]=[]
    VISITED = {tuple(p): 0}
    while True:
        keys = list(SCORES.keys())
        keys.sort()
        SCORES.pop(keys[0])
        min = keys[0]
        if m[min[1]][min[2]] == "E":
            return min[0]
        else:
            s = tuple([min[0]+1, min[1]+min[3], min[2]+min[4], min[3], min[4]])
            sl = tuple([min[0]+1001, min[1]-min[4], min[2]+min[3], -min[4], min[3]])
            sr = tuple([min[0]+1001, min[1]+min[4], min[2]-min[3], min[4], -min[3]])
            for i in [s,sl,sr]:
                if m[i[1]][i[2]] != "#":
                    if i[1:] not in VISITED or i[0] < VISITED[i[1:]]:
                        SCORES[i] = []
                        VISITED[i[1:]] = i[0]



def part_two(p, m):
    SCORES = {}
    SCORES[tuple([0, *p])]=set([tuple(p[:2])])
    VISITED = {tuple(p[:2]): 0}
    while True:
        keys = list(SCORES.keys())
        keys.sort()
        trail = SCORES.pop(keys[0])
        min = keys[0]
        if m[min[1]][min[2]] == "E":
            # print(trail)
            # for x in trail:
            #     m[x[0]][x[1]] = "0"
            # for x in m:
            #     print(''.join(x))
            return len(trail)
        else:
            s = tuple([min[0]+1, min[1]+min[3], min[2]+min[4], min[3], min[4]])
            sl = tuple([min[0]+1001, min[1]-min[4], min[2]+min[3], -min[4], min[3]])
            sr = tuple([min[0]+1001, min[1]+min[4], min[2]-min[3], min[4], -min[3]])
            for i in [s,sl,sr]:
                if m[i[1]][i[2]] != "#":
                    if i[1:] not in VISITED or i[0] <= VISITED[i[1:]]:
                        new_trail = trail.copy()
                        new_trail.add(tuple(i[1:3]))
                        if i in SCORES:
                            SCORES[i] = SCORES[i].union(new_trail)
                        else:
                            SCORES[i] = new_trail

                        VISITED[i[1:]] = i[0]


def main():
    pos = [0,0,0,1]
    contents = file2listoflists("input.txt")
    for ci, i in enumerate(contents):
        for cj, j in enumerate(i):
            if j == "S":
                pos[0]=ci
                pos[1]=cj

    print("P1: ", part_one(pos.copy(), copy.deepcopy(contents)))
    print("P2: ", part_two(pos.copy(), copy.deepcopy(contents)))

if __name__ == "__main__":
    main()