-
Notifications
You must be signed in to change notification settings - Fork 0
/
untitled3.py
70 lines (55 loc) · 2.01 KB
/
untitled3.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# -*- coding: utf-8 -*-
"""
Created on Wed Jan 2 07:41:09 2019
@author: bjwil
"""
edge_dict = copy.deepcopy(edges)
def eulerian_cycle(edge_dict):
'''Generates an Eulerian cycle from the given edges.'''
#current_node = edge_dict.keys()[0]
current_node = next(iter(edge_dict.keys()))
path = [current_node]
# Get the initial cycle.
while True:
path.append(edge_dict[current_node][0])
if len(edge_dict[current_node]) == 1:
del edge_dict[current_node]
else:
edge_dict[current_node] = edge_dict[current_node][1:]
if path[-1] in edge_dict:
current_node = path[-1]
else:
break
# Continually expand the initial cycle until we're out of edge_dict.
while len(edge_dict) > 0:
for i in range(len(path)):
if path[i] in edge_dict:
current_node = path[i]
cycle = [current_node]
while True:
cycle.append(edge_dict[current_node][0])
if len(edge_dict[current_node]) == 1:
del edge_dict[current_node]
else:
edge_dict[current_node] = edge_dict[current_node][1:]
if cycle[-1] in edge_dict:
current_node = cycle[-1]
else:
break
path = path[:i] + cycle + path[i+1:]
break
return path
if __name__ == '__main__':
# Read the input data.
with open ('last.txt', 'r') as in_file:
lines = in_file.read().split('\n')
edges = {}
for connection in lines:
connection = connection.replace(" ", "")
edges[connection.split('->')[0]] = [v for v in connection.split('->')[1].split(',')]
# Get the Eulerian cycle.
path = eulerian_cycle(edges)
# Print and save the answer.
print('->'.join(map(str,path)))
with open('Output9.txt', 'w') as output_data:
output_data.write('->'.join(map(str,path)))