Frog codility leap sort variant

[MoreMoney]

Frog codility leap sort variant

input_str = input("Enter Frogs: ")  # User types 5 1 3 4 2 <enter>.  Do not type the zero.
frog_list = [0]
for number_str in input_str.split():
    frog_list.append(int(number_str))
sorted_frogs = [0] + sorted(frog_list[1:], reverse=True)
frog_count = len(frog_list) - 1
 
print(frog_list, sorted_frogs, frog_count)

My attempt :

input_str = input("Enter Frogs: ")  # User types 5 1 3 4 2 <enter>.  Do not type the zero.
frog_list = [0]
for number_str in input_str.split():
    frog_list.append(int(number_str))
sorted_frogs = [0] + sorted(frog_list[1:], reverse=True)
frog_count = len(frog_list) - 1
 
move_count = 0
position = 0
direction = 0
 
print(frog_list)
if frog_count == 1:
    move_count = 0
else:
    while frog_list != sorted_frogs:
        if direction == 0:
            if frog_list[position] == frog_list[-2]:
                frog_list[position], frog_list[position + 1] = frog_list[position + 1], frog_list[position]
                position += 1
            elif frog_list[position] == frog_list[-1]:
                direction = 1
            elif frog_list[position + 2] > frog_list[position + 1]:
                frog_list[position], frog_list[position + 2] = frog_list[position + 2], frog_list[position]
                position += 2
            else:
                frog_list[position], frog_list[position + 1] = frog_list[position + 1], frog_list[position]
                position += 1
        elif direction == 1:
            if frog_list[position] == frog_list[1]:
                frog_list[position], frog_list[position - 1] = frog_list[position - 1], frog_list[position]
                position -= 1
            elif frog_list[position] == frog_list[0]:
                direction = 0
            elif frog_list[position - 2] < frog_list[position - 1]:
                frog_list[position], frog_list[position - 2] = frog_list[position - 2], frog_list[position]
                position -= 2
            else:
                frog_list[position], frog_list[position - 1] = frog_list[position - 1], frog_list[position]
                position -= 1
         
        move_count += 1
        print(frog_list)
 
    move_count = move_count
 
print('Minimum number of moves: ', move_count)   

Current output:

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

[Program finished]

Can anyone make the code show the steps
Desired output :

Output:
Output:
[0, 5, 1, 3, 4, 2]
[2, 5, 1, 3, 4, 0]
[2, 5, 0, 3, 4, 1]
[2, 5, 4, 3, 0, 1]
[0, 5, 4, 3, 2, 1]
Minimum number of moves:  4

You can help me improve my code or you can share a whole code that do this better since i'm not really good at changing small part of code if you give me one, sorry for that, thank you so much

[Pedroski55]

Hi again!

Like I said, your other code works, but to tell you the truth I don't know how it works

This morning I had an idea. This seems to work and I can understand how it works:

from random import randint

# this saves unnecessary checking, if the list is ordered, or the ml part is ordered, job done
def checkOrder(alist):    
    for i in range(len(alist) - 1):
            if not alist[i] >= alist[i+1]:
                return False
    return True

# get the biggest number in the list, the most important frog!
def findBiggest(sublist):
    return max(sublist)

# seems to work ok
for j in range(3):
    print(f'\nloop {j}\n')
    moves = 0
    #frog_list = [0] + [randint(1, 10) for i in range(6)]
    frog_list = [0] + [randint(1, 16) for i in range(10)]
    #frog_list = [0] + [randint(1, 16) for i in range(16)]     
    print(f'start frog_list = {frog_list}')
    for i in range(0, len(frog_list)):
        ml = frog_list[i:]
        print(f'i-loop starts here:frog_list = {frog_list}, ml = {ml}, i = {i}, moves = {moves}')
        if i == 0:
            index_big = ml.index(findBiggest(ml))
            ml[i] = findBiggest(ml)
            ml[index_big] = 0
            moves +=1
            print(f'first if i == 0: frog_list = {frog_list}, ml = {ml}, biggest = {findBiggest(ml)}, i = {i}, moves = {moves}')
            frog_list = frog_list[0:i] + ml
            continue
        elif i > 0:
            if  ml[0] == findBiggest(ml):
                print('No move necessary, go to next i ... ')
                print(f'elif if ml[0] == findBiggest(ml): frog_list = {frog_list}, ml = {ml},  biggest = {findBiggest(ml)}, i = {i}, moves = {moves}')
                continue
            elif ml[0] == 0:
                index_big = ml.index(findBiggest(ml))
                ml[0] = ml[index_big]
                ml[index_big] = 0
                moves +=1
                print(f'sub elif ml[0] = 0: frog_list = {frog_list}, ml = {ml}, biggest = {findBiggest(ml)}, i = {i}, moves = {moves}')
            else: # here 2 frogs move places so add 2
                index0 = ml.index(0)            
                index_big = ml.index(findBiggest(ml))
                temp1 = ml[0]
                temp2 = ml[index_big]
                # a frog can only jump to empty lilypad
                ml[index0] = temp1
                ml[0] = 0
                # now the biggest frog jumps to ml[0] = 0, leaving ml[index_big] empty, i.e. = 0
                ml[0] = temp2
                ml[index_big] = 0
                moves +=2
        frog_list = frog_list[0:i] + ml
        print(f'elif else: frog_list = {frog_list}, ml = {ml},  biggest = {findBiggest(ml)}, i = {i}, moves = {moves}')
        if checkOrder(frog_list):
            break

I never liked using sorted(frog_list) to check if the sorting actually works, that seems wrong! Either the sorting does its job, or it is useless!

I seem to remember that there was a limit to the number of frogs a frog could jump over, like 2.

That complicates the matter!

[deanhystad]

I seem to remember that there was a limit to the number of frogs a frog could jump over, like 2.

This is not mentioned at all in the OP, but there are a lot of things not mentioned by the OP. It could explain the "i+1" and "i+2" that are in the original solution provided in the OP.

I never liked using sorted(frog_list) to check if the sorting actually works, that seems wrong! Either the sorting does its job, or it is useless!

Sorting is not the job. Efficient sorting is the job. There is nothing in your solution that guarantees the result is efficient. A heuristic approach might weigh all possible moves. Moving a frog to the correct position gets the maximum weight. Moving a frog two spaces closer to their destination less weight, Moving a frog one space closer the least weight. Or maybe you compute a score for each possible move, say the sum of distances the frogs are from their destination, and pick the lowest score as the best move. That at least tries to pick a good solution, but there is no guarantee the optimum solution is found.

An exhaustive search will find the optimum solution but is computationally expensive.

[Pedroski55]

@ deanhystad: I seem to remember from schooldays, that a frog could not make unlimited jumps. We could limit the range to any amount and then do the sorting. Still working on that!

I think the OP is not fluent in English, so could not express himself or herself too well.

This morning I thought, just change checkOrder(alist) a little and maybe save some steps.

Using frog_list = [0] + [randint(1, 16) for i in range(10)] the average is about 12 or 13 steps, can be less.

# this saves unnecessary checking and
# by removing the 0 can save some steps
def checkOrder2(alist):
    index0 = alist.index(0)
    alist.pop(index0)
    for i in range(len(alist) - 1):
            if not alist[i] >= alist[i+1]:
                return False
    return True

for j in range(3):
    print(f'\nloop {j}\n')
    moves = 0
    #frog_list = [0] + [randint(1, 10) for i in range(6)]
    frog_list = [0] + [randint(1, 16) for i in range(10)]
    #frog_list = [0] + [randint(1, 16) for i in range(16)]     
    print(f'start frog_list = {frog_list}')
    for i in range(0, len(frog_list)):
        ml = frog_list[i:]
        print(f'i-loop starts here:frog_list = {frog_list}, ml = {ml}, i = {i}, moves = {moves}')
        if i == 0: # always true at the start, so swap 0 and biggest number
            index_big = ml.index(findBiggest(ml))
            ml[i] = findBiggest(ml)
            ml[index_big] = 0
            moves +=1
            print(f'first if i == 0: frog_list = {frog_list}, ml = {ml}, biggest = {findBiggest(ml)}, i = {i}, moves = {moves}')
            frog_list = frog_list[0:i] + ml
            continue
        elif i > 0: 
            if  ml[0] == findBiggest(ml): # if the biggest number of the slice is at position 0, nothing to do
                print('No move necessary, go to next i ... ')
                print(f'elif if ml[0] == findBiggest(ml): frog_list = {frog_list}, ml = {ml},  biggest = {findBiggest(ml)}, i = {i}, moves = {moves}')
                continue
            elif ml[0] == 0: # if position 0 = 0 just swap 0 and biggest number
                index_big = ml.index(findBiggest(ml))
                ml[0] = ml[index_big]
                ml[index_big] = 0
                moves +=1
                print(f'sub elif ml[0] = 0: frog_list = {frog_list}, ml = {ml}, biggest = {findBiggest(ml)}, i = {i}, moves = {moves}')
            else: # here 2 frogs move places so add 2
                # if position 0 is not 0: swap ml[0] and 0, then swap 0 and biggest
                index0 = ml.index(0)            
                index_big = ml.index(findBiggest(ml))
                temp1 = ml[0]
                temp2 = ml[index_big]
                # a frog can only jump to empty lilypad
                ml[index0] = temp1
                ml[0] = 0
                # now the biggest frog jumps to ml[0] = 0, leaving ml[index_big] empty, i.e. = 0
                ml[0] = temp2
                ml[index_big] = 0
                moves +=2
        frog_list = frog_list[0:i] + ml
        print(f'elif else: frog_list = {frog_list}, ml = {ml},  biggest = {findBiggest(ml)}, i = {i}, moves = {moves}')
        # make copy of ml, or ml will be changed
        l = ml.copy()
        # if l without 0 is ordered we are finished, except for moving the lilypad to the top of the list!
        if checkOrder2(l):
            index0 = ml.index(0)
            ml.pop(index0)
            frog_list = [0] + frog_list[1:i] + ml
            print(f'frog_list = {frog_list}')
            break

[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.

[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