from util import get_input

input = get_input("12.input")

neighbour_map = {}

def add_neighbour(a, b):
    ns = neighbour_map.get(a, [])
    ns.append(b)
    neighbour_map[a] = ns

for line in input:
    [a, b] = line.split("-")
    add_neighbour(a, b)
    add_neighbour(b, a)

def find_paths_1(current, prev):
    if current == "end":
        return 1
    return sum([find_paths_1(next, prev + [current]) for next in neighbour_map[current] if not (next.islower() and next in prev)])

print(find_paths_1("start", ["start"]))

def ndup(ls):
    curr = []
    dups = 0
    for l in ls:
        if l in curr and l.islower():
            dups += 1
        curr.append(l)
    return dups

def find_paths_2(current, prev):
    if current == "end":
        return 1
    return sum([find_paths_2(next, prev + [current]) for next in neighbour_map[current] if not ((next.islower() and next in prev and ndup(prev + [current]) > 0) or next == "start")])

print(find_paths_2("start", []))