1234567891011121314151617181920212223242526272829303132333435363738 |
- 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", []))
|