Frog codility leap sort variant

[deanhystad]

@Pedroski55, your code is an insertion sort. You find the max value and insert it in [1], the second largest value goes in [2] and so on. Insertions are a little odd because you use [0] as a temporary landing spot for the frogs swapping places. It could be written like this:

def frog_sort(frogs):
    """Sort frogs in decreasing order."""
    def swap(a, b):
        """Move frog from from pad a to pad b using pad 0 for the exchange."""
        frogs[0], frogs[a] = frogs[a], frogs[0]
        moves.append(str(frogs))
        frogs[b], frogs[a] = frogs[a], frogs[b]
        moves.append(str(frogs))
        frogs[0], frogs[b] = frogs[b], frogs[0]
        moves.append(str(frogs))

    frogs = [0] + frogs
    moves = [str(frogs)]
    for i in range(1, len(frogs)):
        max_index = frogs.index(max(frogs[i:]))
        if max_index != i:
            swap(i, max_index)
    return moves

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

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

For this particular arrangement of frogs, this is the least number of moves to sort the frogs.

Sorting this arrangment of frogs wastes several moves retuning the empty lily pad back to zero.

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

Changing the code to not return the empty lily pad to [0] each time reduces the number of moves, but we can no longer use max(frogs[i:] ) to find the frog to move to frogs[i]. The frog that belons in frogs[i] might be in frogs[0]. That is where having a sorted list comes in handy.

def frog_sort(frogs):
    """Sort frogs in decreasing order."""
    def swap(index):
        """Move frog from index to the empty pad."""
        nonlocal empty
        frogs[empty], frogs[index], empty = frogs[index], frogs[empty], index
        moves.append(str(frogs))

    empty = 0
    order = [0] + sorted(frogs, reverse=True)
    frogs = [0] + frogs
    moves = [str(frogs)]
    for dst in range(1, len(frogs)):
        src = frogs.index(order[dst])
        if src != dst:
            if dst != empty:
                swap(dst)
            swap(src)
    return moves

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

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

Neither of these use the "limited leap" that's been discussed recently. That adds an interesting twist to the problem and I can see that an "out and back" solution where you bubble the smallest value to the right, then bubble back larger values to the left might work. That could be what the OP was doing the "direction" flag.