Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dijkstra solution in Creative category for Digits Doublets by Rcp8jzd
def is_neighbour(a: int, b: int) -> bool:
"""
Returns True if the given numbers differ only by 1 digit,
false otherwise
"""
a, b = str(a), str(b)
# Booleans are ints, we can sum the number of differences
if sum(a[i] != b[i] for i in range(len(a))) == 1:
return True
return False
def checkio(numbers: list) -> list:
# for each node of the graph, the neighbours are a set of ints
graph = {a: {b for b in numbers if is_neighbour(a, b)} for a in numbers}
# dijkstra algorithm
initial_node, end_node = numbers[0], numbers[-1]
path = {}
adj_node = {}
queue = numbers
for node in graph:
path[node] = float("inf")
adj_node[node] = None
path[initial_node] = 0
while queue:
# find min distance which wasn't marked as current
key_min = queue[0]
min_val = path[key_min]
for n in range(1, len(queue)):
if path[queue[n]] < min_val:
key_min = queue[n]
min_val = path[key_min]
current = key_min
queue.remove(current)
for i in graph[current]:
# 1 because each node has a distance of 1 to its neighbours
alternate = 1 + path[current]
if path[i] > alternate:
path[i] = alternate
adj_node[i] = current
# Construct the answer starting from the end
x = end_node
shortest_path = [end_node]
while True:
x = adj_node[x]
if x is None:
break
shortest_path = [x] + shortest_path
return shortest_path
#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"
March 2, 2020
Comments:
