AoC 2024/21

#Advent of Code 2024: Day 21
from icecream import ic
from collections import deque
from itertools import product

def bfs(first, second, keyboard):
    result = []
    queue = deque([[keyboard[first], "", set()]])
    min_length = 100

    while queue:
        (r, c), path, seen = queue.popleft()
        if first == second: return ["A"]
        seen.add((r,c))
        for r, c, p in [(r-1, c, "^"), (r, c-1, "<"), (r+1, c, "v"), (r, c+1, ">")]:
            if (r, c) not in keyboard.values(): continue
            if (r, c) in seen: continue
            if keyboard[second] == (r,c):
                if min_length >= len(path + p):
                    min_length = len(path + p + "A")
                    result.append(path + p + "A")
            else:
                queue.append([(r, c), path + p, seen])
    return result

def generate_paths(keyb):
    #generate all possible paths between all buttons on a keyboard
    keyboard = {}
    paths = dict()
    for r, line in enumerate(keyb):
        for c, char in enumerate(line):
            if char == None: continue
            keyboard[char] = (r,c)
    for first in keyboard.keys():
        for second in keyboard.keys():
            paths[(first, second)] = bfs(first, second, keyboard)
    return paths

def solve_path(path, path_keyboard):
    result = []
    for first, second in zip("A" + path, path):
        result.append(path_keyboard[(first, second)])
    paths = ["".join(map(str, combo)) for combo in list(product(*result))]
    length = min(len(s) for s in paths)
    return [s for s in paths if len(s) == length]

#MAIN
with open("test.txt") as file:
    lines = file.read().splitlines()

#generate all possible paths between all buttons on both keyboards
paths_nums = generate_paths([["7", "8", "9"], ["4","5","6"], ["1", "2" ,"3"], [None, "0","A"]])
paths_arrows = generate_paths([[None, "^", "A"], ["<", "v", ">"]])

ic(paths_nums)


for num in lines:
    paths = solve_path(num, paths_nums)
    for path in paths:
        second = solve_path(path, paths_arrows)
    for path in second:
        third = solve_path(path, paths_arrows)
    print(num, len(third[0]))