AoC 21-12

file = "inputs/2021/12/data.txt"

nodes = set()
adjacency_list = dict()
with open(file, "r") as f:
    lines = f.read().split("\n")
    for connection in lines:
        src, dst = connection.split("-")
        nodes.add(src)
        nodes.add(dst)
        adjacency_list[src] = adjacency_list.get(src, set())
        adjacency_list[dst] = adjacency_list.get(dst, set())

        adjacency_list[src].add(dst)
        adjacency_list[dst].add(src)

def is_large_cave(cave_name: str) -> bool:
    return cave_name == cave_name.upper()

def pathfind(start, end, progress, small_doubled):
    if start == end:
        return [progress + [end]]

    sub_paths = []
    for neighbor in adjacency_list[start]:
        if neighbor == start or neighbor == "start":
            continue
        if neighbor in progress and not is_large_cave(neighbor):
            if small_doubled:
                continue
            else:
                sub_paths.extend(
                    pathfind(neighbor, end, progress + [start], True)
                )
                continue
        sub_paths.extend(
            pathfind(neighbor, end, progress + [start], small_doubled)
        )
    return sub_paths

part_1 = pathfind("start", "end", [], True)
print(f"Part 1: {len(part_1):,d}")

part_2 = pathfind("start", "end", [], False)
print(f"Part 2: {len(part_2):,d}")