forked from KenMercusLai/checkio
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Digits Doublets.py
41 lines (36 loc) · 1.48 KB
/
Digits Doublets.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
import heapq
def shortest_path(graph, start, end):
queue = [(0, start, [])]
seen = set()
while True:
(cost, v, path) = heapq.heappop(queue)
if v not in seen:
path = path + [v]
seen.add(v)
if v == end:
return cost, path
for (next_item, c) in graph[v].iteritems():
heapq.heappush(queue, (cost + c, next_item, path))
return queue
def checkio(numbers):
number_dict = {}
for i in range(len(numbers)):
for j in range(i + 1, len(numbers)):
if len([k for k in zip(str(numbers[i]), str(numbers[j]))
if k[0] != k[1]]) == 1:
if numbers[i] not in number_dict:
number_dict[numbers[i]] = {}
if numbers[j] not in number_dict:
number_dict[numbers[j]] = {}
number_dict[numbers[i]][numbers[j]] = 1
number_dict[numbers[j]][numbers[i]] = 1
return shortest_path(number_dict, numbers[0], numbers[-1])[1]
# These "asserts" using only for self-checking and not necessary for
# auto-testing
if __name__ == '__main__':
assert checkio([123, 991, 323, 321, 329, 121, 921, 125, 999]) == [
123, 121, 921, 991, 999], "First"
assert checkio([111, 222, 333, 444, 555, 666, 121, 727, 127, 777]) == [
111, 121, 127, 727, 777], "Second"
assert checkio([456, 455, 454, 356, 656, 654]) == [
456, 454, 654], "Third, [456, 656, 654] is correct too"