You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
28 lines
930 B
28 lines
930 B
#!/bin/env python3
|
|
import sys
|
|
import string
|
|
from collections import Counter
|
|
|
|
def isSmall(node): return all(c in string.ascii_lowercase for c in node)
|
|
|
|
def ext(path, ns, visits=1):
|
|
if path[-1] == 'end': return (yield path)
|
|
for n in ns[path[-1]]:
|
|
if n == 'start': continue
|
|
ext = path + (n,)
|
|
m = list(map(lambda x: x[1], Counter(n for n in ext if isSmall(n)).most_common(2)))
|
|
if m[0] > visits or len(m) > 1 and m[1] > 1: continue
|
|
yield ext
|
|
|
|
if __name__ == '__main__':
|
|
edges = [line.strip().split('-') for line in open(sys.argv[1])]
|
|
ns = { n: set() for e in edges for n in e }
|
|
for a,b in edges: ns[a].add(b); ns[b].add(a)
|
|
|
|
ps = set([('start',)])
|
|
while (n := set(np for p in ps for np in ext(p, ns))) != ps: ps = n
|
|
print(len(ps))
|
|
|
|
ps = set([('start',)])
|
|
while (n := set(np for p in ps for np in ext(p, ns, visits=2))) != ps: ps = n
|
|
print(len(ps))
|
|
|