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 find_paths_2(current, prev, duped=False):
    if current == "end":
        return 1
    return sum([find_paths_2(next, prev + [current], duped or (next.islower() and next in prev)) for next in neighbour_map[current] if not ((duped and next.islower() and (next in prev)) or next == "start")])

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