54 lines
1.5 KiB
Python
Executable File
54 lines
1.5 KiB
Python
Executable File
#!/usr/bin/env python3
|
|
from useful import *
|
|
|
|
def parseline(s):
|
|
return [x for x in s.strip().split('-')]
|
|
|
|
def solve(pos, matrix, can_twice=False, path=[]):
|
|
global pathname, index, visit, cheat
|
|
visit += 1
|
|
|
|
if pathname[pos] == 'end':
|
|
pathtext = '-'.join([pathname[i] for i in (*path, pos)])
|
|
cheat |= {pathtext}
|
|
return 1
|
|
|
|
acc = 0
|
|
if not pathname[pos].isupper():
|
|
nextrix = matrix.copy()
|
|
nextrix[:,pos] = False
|
|
nextrix[pos,:] = False
|
|
else:
|
|
nextrix = matrix
|
|
for i in range(len(matrix)):
|
|
if matrix[pos][i]:
|
|
acc += solve(i, nextrix, can_twice, path + [pos, ])
|
|
if can_twice and not pathname[pos].isupper() and pathname[pos] != 'start':
|
|
acc += solve(i, matrix, False, path + [pos, ])
|
|
return acc
|
|
|
|
with open(0) as f:
|
|
|
|
paths = [parseline(l) for l in lines(f)]
|
|
points = set()
|
|
pathstrings = set()
|
|
for a, b in paths:
|
|
points |= {a}
|
|
points |= {b}
|
|
|
|
pathname = {k: v for (k, v) in enumerate(points)}
|
|
index = {k: v for (v, k) in pathname.items()}
|
|
visit = 0
|
|
ic(index, pathname)
|
|
|
|
matrix = np.zeros((len(index), len(index)), dtype=bool)
|
|
for a, b in paths:
|
|
matrix[index[a], index[b]] = True
|
|
matrix[index[b], index[a]] = True
|
|
ic(matrix)
|
|
cheat = set()
|
|
print(solve(index['start'], matrix))
|
|
print(solve(index['start'], matrix, can_twice=True), '(may be duplicates)')
|
|
print(len(cheat))
|
|
ic(visit)
|