_output

$ echo "--------------plain python-------------" && \
    time python a.py && \
    echo "------------compiled with mypyc-----------" && \
    time python -c "import b"
--------------plain python-------------
10
19
226
part a --->  5333
36
103
3509
part b --->  146553

real    0m1.205s
user    0m1.088s
sys     0m0.121s
------------compiled with mypyc-----------
10
19
226
part a --->  5333
36
103
3509
part b --->  146553

real    0m0.819s
user    0m0.722s
sys     0m0.099s

a.py

# advent of code day 12 2021. runs in ~1.2s
from collections import defaultdict


def parse(it):
    graph = defaultdict(list)
    for line in it:
        if not line.strip():
            continue
        a, b = line.strip().split("-")
        graph[a].append(b)
        graph[b].append(a)

    # remove edges to the start node
    for key in graph:
        try:
            graph[key].remove("start")
        except ValueError:
            pass

    # remove edges from the end node
    del graph["end"]

    return graph


def paths(graph):
    paths = [("start",)]
    complete = set()
    while paths:
        newpaths = []
        for path in paths:
            for node in graph[path[-1]]:
                if node == "end":
                    complete.add(path + ("end",))
                elif node.islower() and node not in path:
                    newpaths.append(path + (node,))
                elif node.isupper():
                    newpaths.append(path + (node,))
        paths = newpaths
    return len(complete)


def nodupe(path):
    """return true if there is no duplicate lower-cased letter in the path"""
    ls = [p for p in path if p.islower()]
    return len(ls) == len(set(ls))


def dubbpaths(graph):
    paths = [("start",)]
    complete = set()
    while paths:
        newpaths = []
        for path in paths:
            for node in graph[path[-1]]:
                if node == "end":
                    complete.add(path + ("end",))
                elif node.islower():
                    if node not in path or nodupe(path):
                        newpaths.append(path + (node,))
                else:
                    newpaths.append(path + (node,))
        paths = newpaths
    return len(complete)


print(paths(parse(open("small.txt"))))
print(paths(parse(open("med.txt"))))
print(paths(parse(open("lg.txt"))))
print("part a ---> ", paths(parse(open("input.txt"))))
print(dubbpaths(parse(open("small.txt"))))
print(dubbpaths(parse(open("med.txt"))))
print(dubbpaths(parse(open("lg.txt"))))
print("part b ---> ", dubbpaths(parse(open("input.txt"))))

b.py

# same as a.py, but with typings added. runs in ~0.8s
# install mypyc with `pip install mypy`
# compile with `mypyc b.py`
# run with `python -c "import b"`
from collections import defaultdict
from typing import Iterator, List, Tuple, Set


def parse(it: Iterator[str]) -> defaultdict[str, List[str]]:
    graph: defaultdict[str, List[str]] = defaultdict(list)
    line: str
    for line in it:
        if not line.strip():
            continue
        a: str
        b: str
        a, b = line.strip().split("-")
        graph[a].append(b)
        graph[b].append(a)

    # remove edges to the start node
    key: str
    for key in graph:
        try:
            graph[key].remove("start")
        except ValueError:
            pass

    # remove edges from the end node
    del graph["end"]

    return graph


def paths(graph: defaultdict[str, List[str]]) -> int:
    paths: List[Tuple[str, ...]] = [("start",)]
    complete: Set[Tuple[str, ...]] = set()
    while paths:
        newpaths: List[Tuple[str, ...]] = []
        for path in paths:
            for node in graph[path[-1]]:
                if node == "end":
                    complete.add(path + ("end",))
                elif node.islower() and node not in path:
                    newpaths.append(path + (node,))
                elif node.isupper():
                    newpaths.append(path + (node,))
        paths = newpaths
    return len(complete)


def nodupe(path: Tuple[str, ...]) -> bool:
    """return true if there is no duplicate lower-cased letter in the path"""
    ls: List[str] = [p for p in path if p.islower()]
    return len(ls) == len(set(ls))


def dubbpaths(graph: defaultdict[str, List[str]]) -> int:
    paths: List[Tuple[str, ...]] = [("start",)]
    complete: Set[Tuple[str, ...]] = set()
    while paths:
        newpaths: List[Tuple[str, ...]] = []
        for path in paths:
            for node in graph[path[-1]]:
                if node == "end":
                    complete.add(path + ("end",))
                elif node.islower():
                    if node not in path or nodupe(path):
                        newpaths.append(path + (node,))
                else:
                    newpaths.append(path + (node,))
        paths = newpaths
    return len(complete)


print(paths(parse(open("small.txt"))))
print(paths(parse(open("med.txt"))))
print(paths(parse(open("lg.txt"))))
print("part a ---> ", paths(parse(open("input.txt"))))
print(dubbpaths(parse(open("small.txt"))))
print(dubbpaths(parse(open("med.txt"))))
print(dubbpaths(parse(open("lg.txt"))))
print("part b ---> ", dubbpaths(parse(open("input.txt"))))

input.txt

pq-GX
GX-ah
mj-PI
ey-start
end-PI
YV-mj
ah-iw
te-GX
te-mj
ZM-iw
te-PI
ah-ZM
ey-te
ZM-end
end-mj
te-iw
te-vc
PI-pq
PI-start
pq-ey
PI-iw
ah-ey
pq-iw
pq-start
mj-GX