12/4/2019 - 8:38 PM

Breadth-first_search - BFS

# Task from:

def count_diff(first, second):
    Count how many digits are distinguished in the two numbers.
    return len(str(first)) - sum(f == s for f, s in zip(str(first), str(second)))

def list_to_graph(numbers):
    Convert a list of numbers in the dict graph representation,
    where each key is a node and values are "neighbour" numbers.
    res = {}
    for node in numbers:
        res[node] = []
        for second_node in numbers:
            if count_diff(node, second_node) == 1:
    return res

def checkio(numbers):
    I'm using "Breadth-first search" algorithm here.
    graph = list_to_graph(numbers)
    goal = numbers[-1]
    # the queue contains positions and paths for they.
    queue = [(numbers[0], (numbers[0],))]
    # the visited numbers we store in the set, because it faster
    closed = set()
    while queue:
        current, path = queue.pop(0)
        if current in closed:
        if current == goal:
            return list(path)
        for neigh in graph[current]:
            if neigh in closed:
            queue.append((neigh, path + (neigh,)))
    return []
    # ----------------------- Or --------------------
    def checkio(numbers):
      paths = [[numbers[0]]]
      while True:
          p = paths.pop(0)
          # find node neighbors which are not in p (path)
          for c in set(numbers)-set(p):
              if sum(x!=y for x, y in zip(str(p[-1]), str(c))) == 1:
                  if c == numbers[-1]:
                      return p + [c]
                  paths.append(p + [c])