Frog codility leap sort variant - Printable Version +- Python Forum (https://python-forum.io) +-- Forum: Python Coding (https://python-forum.io/forum-7.html) +--- Forum: Homework (https://python-forum.io/forum-9.html) +--- Thread: Frog codility leap sort variant (/thread-41865.html) |
Frog codility leap sort variant - MoreMoney - Mar-31-2024 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: Can anyone make the code show the stepsDesired output : 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
RE: Frog codility leap sort variant - Pedroski55 - Apr-04-2024 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): breakI 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! RE: Frog codility leap sort variant - deanhystad - Apr-04-2024 Quote: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. Quote: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. RE: Frog codility leap sort variant - Pedroski55 - Apr-05-2024 @ 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 RE: Frog codility leap sort variant - deanhystad - Apr-05-2024 @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") 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. 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") 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.
RE: Frog codility leap sort variant - deanhystad - Apr-06-2024 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. 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.
|