solve_distinct_disks.py

from copy import deepcopy


def copy(entity):
    return deepcopy(entity)


def get_start(l, n):
    """Get a root entity.

    Args:
        l (int): the number of cells
        n (int): the number of disks

    Returns:
        tuple: the root entity as (0, 1, None, None) given l=4, n=2
    """
    return tuple(i if i < n else None for i in range(l))


def move1step(entity):
    """Generate all of the next entities(nodes) by just moving one disk.

    Args:
        entity (tuple): Current entity(node)

    Returns:
        tuple: A collection consists move procedure as the first element
                and the next entity as the second element. Generate None
                if next entity does not exist.
    """
    entity = list(entity)
    length = len(entity)
    for i, cell in enumerate(entity):
        if entity[i] is not None:
            if i + 1 < length and entity[i + 1] is None:
                new_entity = copy(entity)
                new_entity[i], new_entity[i + 1] = new_entity[i + 1], new_entity[i]
                yield ((i, i + 1), tuple(new_entity))
            elif i + 2 < length and entity[i + 2] is None:
                new_entity = copy(entity)
                new_entity[i], new_entity[i + 2] = new_entity[i + 2], new_entity[i]
                yield ((i, i+2), tuple(new_entity))
    else:
        yield


def build_graph(root):
    """
    Build the graph of the collection of entities.

    Args:
        root (tuple): The root node of the graph

    Returns:
        dick: The collection of all entities that denotes key to the parent
                entity, value to the list of all possible next entities.
    """
    graph = {}
    stack = []
    stack.append(root)

    while stack:
        vertax = stack.pop()
        for entity in move1step(vertax):
            container = graph.get(vertax, [])
            if entity is not None:
                stack.append(entity[1])
                container.append(entity)
            graph[vertax] = container
    else:
        return graph


def bfs(start, end, graph):
    """Search the graph using Breath-first Search algorithm.

    Args:
        start (tuple): The root entity
        end (tuple): The goal
        graph (dict): The entities graph

    Returns:
        tuple: the shorest path from the start entity to the goal entity.
    """
    queue = [([], start)]

    while queue:
        path, vertax = queue.pop(0)
        for entity in graph[vertax]:
            if entity[1] == end:
                return tuple(path + [entity[0]])
            else:
                queue.append((((path + [entity[0]])), entity[1]))


def main(l, n):
    start = get_start(l, n)
    end = tuple(reversed(list(start)))
    graph = build_graph(start)

    ret = bfs(start, end, graph)
    print(ret)

if __name__ == '__main__':
    main(5, 2)