|
1
|
|
|
import heapq |
|
2
|
|
|
|
|
3
|
|
|
|
|
4
|
|
View Code Duplication |
def shortest_path(graph, start, end): |
|
|
|
|
|
|
5
|
|
|
queue = [(0, start, [])] |
|
6
|
|
|
seen = set() |
|
7
|
|
|
while True: |
|
8
|
|
|
(cost, v, path) = heapq.heappop(queue) |
|
9
|
|
|
if v not in seen: |
|
10
|
|
|
path = path + [v] |
|
11
|
|
|
seen.add(v) |
|
12
|
|
|
if v == end: |
|
13
|
|
|
return cost, path |
|
14
|
|
|
for (next_item, c) in graph[v].items(): |
|
15
|
|
|
heapq.heappush(queue, (cost + c, next_item, path)) |
|
16
|
|
|
return queue |
|
17
|
|
|
|
|
18
|
|
|
|
|
19
|
|
|
def checkio(numbers): |
|
20
|
|
|
number_dict = {} |
|
21
|
|
|
for i in range(len(numbers)): |
|
22
|
|
|
for j in range(i + 1, len(numbers)): |
|
23
|
|
|
if ( |
|
24
|
|
|
len([k for k in zip(str(numbers[i]), str(numbers[j])) if k[0] != k[1]]) |
|
25
|
|
|
== 1 |
|
26
|
|
|
): |
|
27
|
|
|
if numbers[i] not in number_dict: |
|
28
|
|
|
number_dict[numbers[i]] = {} |
|
29
|
|
|
if numbers[j] not in number_dict: |
|
30
|
|
|
number_dict[numbers[j]] = {} |
|
31
|
|
|
number_dict[numbers[i]][numbers[j]] = 1 |
|
32
|
|
|
number_dict[numbers[j]][numbers[i]] = 1 |
|
33
|
|
|
return shortest_path(number_dict, numbers[0], numbers[-1])[1] |
|
34
|
|
|
|
|
35
|
|
|
|
|
36
|
|
|
# These "asserts" using only for self-checking and not necessary for |
|
37
|
|
|
# auto-testing |
|
38
|
|
View Code Duplication |
if __name__ == '__main__': |
|
|
|
|
|
|
39
|
|
|
assert checkio([123, 991, 323, 321, 329, 121, 921, 125, 999]) == [ |
|
40
|
|
|
123, |
|
41
|
|
|
121, |
|
42
|
|
|
921, |
|
43
|
|
|
991, |
|
44
|
|
|
999, |
|
45
|
|
|
], "First" |
|
46
|
|
|
assert checkio([111, 222, 333, 444, 555, 666, 121, 727, 127, 777]) == [ |
|
47
|
|
|
111, |
|
48
|
|
|
121, |
|
49
|
|
|
127, |
|
50
|
|
|
727, |
|
51
|
|
|
777, |
|
52
|
|
|
], "Second" |
|
53
|
|
|
assert checkio([456, 455, 454, 356, 656, 654]) == [ |
|
54
|
|
|
456, |
|
55
|
|
|
454, |
|
56
|
|
|
654, |
|
57
|
|
|
], "Third, [456, 656, 654] is correct too" |
|
58
|
|
|
|
KenMercusLai /
checkio
Loading history...