Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
A* solution in Clear category for Digits Doublets by PositronicLlama
"""Return the shortest path between two numbers, changing one digit each step."""
import collections
import heapq
import itertools
def digit_delta(a, b, base=10):
"""Return the number of digits that differ between a and b."""
count = 0
while a > 0 or b > 0:
count += (a % base) != (b % base)
a //= base
b //= base
return count
def astar(start, goal, graph, heuristic):
"""
Perform an A* search over graph from start to goal.
heuristic: (node, goal) -> estimate of distance from node to goal.
Return the list of traversed nodes from start to goal.
"""
# Estimated, actual, sequence #, previous node (linked list).
# The sequence number is to prevent ever comparing previous nodes.
pending = [(0, 0, 0, (start, None))]
seq = 1
while pending:
_, d, _, prior = heapq.heappop(pending)
node, rest = prior
if node == goal:
path = [node]
while rest is not None:
node, rest = rest
path.append(node)
return list(reversed(path))
for adj in graph[node]:
h = heuristic(adj, goal)
heapq.heappush(pending, (d + 1 + h, d + 1, seq, (adj, prior)))
seq += 1
def checkio(numbers):
"""
Return a list of steps in a path between numbers[0] and numbers[-1].
Each step must appear in number, and successive steps must differ by
only one decimal digit.
"""
graph = collections.defaultdict(list)
for a, b in itertools.combinations(numbers, 2):
if digit_delta(a, b) == 1:
graph[a].append(b)
graph[b].append(a)
return astar(numbers[0], numbers[-1], graph, digit_delta)
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"
Feb. 28, 2014