62 lines
1.3 KiB
Python
62 lines
1.3 KiB
Python
|
import pprint
|
||
|
|
import itertools
|
||
|
|
import fileinput
|
||
|
|
|
||
|
|
nodes = []
|
||
|
|
edges = []
|
||
|
|
for raw in fileinput.input():
|
||
|
|
line = raw.strip()
|
||
|
|
if line == '': continue
|
||
|
|
[a,b] = line.split('-')
|
||
|
|
nodes += [a, b]
|
||
|
|
edges.append((a, b))
|
||
|
|
|
||
|
|
nodes = list(set(nodes))
|
||
|
|
nodes.sort()
|
||
|
|
|
||
|
|
graph = [[0 for j in range(len(nodes))] for i in range(len(nodes))]
|
||
|
|
|
||
|
|
#pprint.pprint(graph)
|
||
|
|
|
||
|
|
for (a,b) in edges:
|
||
|
|
i, j = nodes.index(a), nodes.index(b)
|
||
|
|
graph[i][j] = 1
|
||
|
|
graph[j][i] = 1
|
||
|
|
|
||
|
|
visit_only_once = [e for e in nodes if e.lower() == e and e != 'start' and e != 'end']
|
||
|
|
|
||
|
|
start_index = nodes.index('start')
|
||
|
|
end_index = nodes.index('end')
|
||
|
|
|
||
|
|
print(f'{visit_only_once=}')
|
||
|
|
|
||
|
|
visit_only_once_index = [nodes.index(e) for e in visit_only_once]
|
||
|
|
|
||
|
|
possibles = []
|
||
|
|
|
||
|
|
def explore_path(stack, level, locked, s):
|
||
|
|
edges = [i for i,e in enumerate(graph[s]) if e]
|
||
|
|
|
||
|
|
if s == end_index:
|
||
|
|
possibles.append(stack)
|
||
|
|
return
|
||
|
|
|
||
|
|
for edge in edges:
|
||
|
|
new_locked = locked.copy()
|
||
|
|
if edge in locked: continue
|
||
|
|
if edge == start_index: continue
|
||
|
|
if edge in visit_only_once_index:
|
||
|
|
new_locked += [edge]
|
||
|
|
|
||
|
|
#print(f'{level=} , {nodes[edge]=}, {new_locked=}')
|
||
|
|
explore_path([s]+stack, level+1, new_locked, edge)
|
||
|
|
|
||
|
|
print('start exploring...')
|
||
|
|
|
||
|
|
explore_path([], 0, [], start_index)
|
||
|
|
|
||
|
|
for p in possibles:
|
||
|
|
print([ nodes[i] for i in list(reversed(p))])
|
||
|
|
|
||
|
|
print(f'There are {len(possibles)} paths')
|