Frog codility leap sort variant

[deanhystad]

I reviewed the OP and it does limit hops to 1 or 2 frogs. This is the code cleaned up a little with some comments.

def frog_sort(frogs):
    """Sort frogs in decreasing order.  Frogs move by hopping to
    the empty pad.  A frog cannot hop over more htan 1 frog
    """
    def hop(count):
        """Hop frogs[x+count] to frogs[x]."""
        nonlocal x
        frog = x + count
        frogs[frog], frogs[x], x = frogs[x], frogs[frog], frog
        moves.append(str(frogs))

    x = 0  # Index of the empty lily pad.
    count = len(frogs)
    direction = 1
    frogs = [0] + frogs  # Add empty lily pad.
    moves = [str(frogs)]  # Record of moves.

    # Uses an odd bubble sort variant, weaving the empty pad left and
    # right though the list of frogs, moving higher numbered frogs to
    # the left and lower numbered frogs to the right.
    while x or any(a < b for a, b in zip(frogs[1:], frogs[2:])):
        if direction == 1:
            # Moving through frogs left to right
            if x == count:
                direction = -1  # Hit end of list.  Reverse direction
            elif x == count-1:
                hop(1)
            elif frogs[x+2] > frogs[x+1]:
                hop(2)
            else:
                hop(1)
        else:
            # Moving through frogs right to left
            if x == 0:
                direction = 1  # Hit end of list.  Reverse direction
            elif x == 1:
                hop(-1)
            elif frogs[x-2] < frogs[x-1]:
                hop(-2)
            else:
                hop(-1)
    return frogs[1:], moves


frogs, moves = frog_sort([int(x) for x in input("Enter Frogs: ").split()])
print(*moves, len(moves)-1, sep="\n")

This sorts the frogs, but like a bubble sort it takes a lot of moves to do so.

Output:
Enter Frogs: 5 4 3 1 2
[0, 5, 4, 3, 1, 2]
[5, 0, 4, 3, 1, 2]
[5, 4, 0, 3, 1, 2]
[5, 4, 3, 0, 1, 2]
[5, 4, 3, 2, 1, 0]
[5, 4, 3, 2, 0, 1]
[5, 4, 3, 0, 2, 1]
[5, 4, 0, 3, 2, 1]
[5, 0, 4, 3, 2, 1]
[0, 5, 4, 3, 2, 1]
9

This is a better solution, but it took my exhaustive search algorithm 5 seconds to find it. Longer lists will take a really long time to solve.

Output:
Enter Frogs: 5 4 3 1 2
[0, 5, 4, 3, 1, 2]
[4, 5, 0, 3, 1, 2]
[4, 5, 3, 0, 1, 2]
[4, 5, 3, 2, 1, 0]
[4, 5, 3, 2, 0, 1]
[4, 5, 3, 0, 2, 1]
[4, 5, 0, 3, 2, 1]
[0, 5, 4, 3, 2, 1]
7