Posts: 17
Threads: 5
Joined: Mar 2024
Mar-28-2024, 07:30 AM
(This post was last modified: Mar-28-2024, 07:52 AM by MoreMoney.)
(Mar-27-2024, 06:14 PM)deanhystad Wrote: @Pedroski55, the goal is not to sort the frogs. The goal is to move the frogs into sorted order using the fewest moves. There is also a restriction that a frog can only move to an open spot, the zero spot. That is my understanding of the problem from thr OP and some web searching for frog puzzle.
@MoreMoney, the main problem with your code is it makes moves that don't get you any closer to the solution. Pedroski pointed out that your solution moved frogs that were in the correct position. That's a waste compounded by a move that gets you further from the solution.
I suggest you pull out a notepad and a pencil and solve some of these puzzles by hand. I would start by using a very methodical approach. Move the correct frog to position 1, then correctly fill position 2 and so on until you fill al N positions.
Output: [0, 5, 1, 3, 4, 2] Move 5 to position 1, Already there, no move required.
[0, 5, 1, 3, 4, 2] Move 4 to position 2. 2 is not empty, so move frog from position 2 to the open position
[1, 5, 0, 3, 4, 2] Now move 4 to position 2
[1, 5, 4, 3, 0, 2] Move 3 to position 3. Already there, no move required.
[1, 5, 4, 3, 0, 2] Move 2 to position 4
[1, 5, 4, 3, 2, 0] Move 1 to position 5
[0, 5, 4, 3, 2, 1]
This is easily converted to pseudo code
for position from 1 to 5
if frog[position] is not correct
if frog[position] is not open
move frog[position] to open the spot
move correct frog into frog[position]It is easy to see that the maximum possible number of moves for N frogs is 2N moves, two moves for each frog, but I have yet to test a puzzle that takes more than N+1 moves unless I allow repeating a number.
Another solition I tired is something I called "Find a hole, fill a hole". In this solution I look for a frog that is in the wrong space and I swap that frog with 0 Now I loop, moving the correct frog to the open position until the open position is frogs[0]. Repeat until I can no longer find any frogs in the wrong position.
func find_a_hole()
for frog in frogs
if frog is in wrong position
move frog to open spot
return True
return False
while find_a_hole()
while frogs[0] is not open:
move correct frog to open position( You are right thank you, im keep trying but can't implemented the logic yet
import random
import time
leapfrog = [0]
n = int(input('Masukkan jumlah angka pertama yang ingin anda sortir : '))
for i in range(1, n + 1):
leapfrog_number = random.randint(1,100)
leapfrog.append(leapfrog_number)
start = time.time()
print(leapfrog)
def even_leapfrog(leapfrog):
shift_count = 0
for i in range(0, n, 2):
while leapfrog[i] < leapfrog[i + 2]:
leapfrog[i], leapfrog[i + 2] = leapfrog[i + 2], leapfrog[i]
shift_count += 1
print(leapfrog)
leapfrog[n], leapfrog[n - 1] = leapfrog[n - 1], leapfrog[n]
shift_count += 1
print(leapfrog)
for i in range(n - 1, 1, -2):
leapfrog[i], leapfrog[i - 2] = leapfrog[i - 2], leapfrog[i]
shift_count += 1
print(leapfrog)
leapfrog[0], leapfrog[1] = leapfrog[1], leapfrog[0]
shift_count += 1
print(leapfrog)
return shift_count
def odd_leapfrog(leapfrog):
shift_count = 0
for i in range(0, n, 2):
try:
while leapfrog[i] < leapfrog[i + 2]:
leapfrog[i], leapfrog[i + 2] = leapfrog[i + 2], leapfrog[i]
shift_count += 1
print(leapfrog)
except IndexError:
leapfrog[n], leapfrog[n - 1] = leapfrog[n - 1], leapfrog[n]
shift_count += 1
print(leapfrog)
for i in range(n, 1, -2):
leapfrog[i], leapfrog[i - 2] = leapfrog[i - 2], leapfrog[i]
shift_count += 1
print(leapfrog)
leapfrog[0], leapfrog[1] = leapfrog[1], leapfrog[0]
shift_count += 1
print(leapfrog)
return shift_count
shift_count = 0
while leapfrog[1] < leapfrog[2]:
try:
if n % 2 == 1:
shift_count += odd_leapfrog(leapfrog)
end = time.time()
period = end - start
else:
shift_count += even_leapfrog(leapfrog)
end = time.time()
period = end - start
except (IndexError, ValueError):
break
print("Jumlah pergeseran:", shift_count)
print("Waktu yang dibutuhkan adalah:", period, " ms")Would you like to give me a code to replace my code logic on bottom?
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) Thank you for helping me
Thanks for trying to help me, sorry for making you confused, would you like to help me in this one? @ Pedroski55
Posts: 6,221
Threads: 16
Joined: Feb 2020
Solve a puzzle by hand, like I did here:
Output: [0, 5, 1, 3, 4, 2] Move 5 to position 1, Already there, no move required.
[0, 5, 1, 3, 4, 2] Move 4 to position 2. 2 is not empty, so move frog from position 2 to the open position
[1, 5, 0, 3, 4, 2] Now move 4 to position 2
[1, 5, 4, 3, 0, 2] Move 3 to position 3. Already there, no move required.
[1, 5, 4, 3, 0, 2] Move 2 to position 4
[1, 5, 4, 3, 2, 0] Move 1 to position 5
[0, 5, 4, 3, 2, 1]
Solve [0, 1, 5, 2, 4, 3] showing the steps and describing the logic for each step.
Posts: 832
Threads: 131
Joined: Jul 2017
Mar-29-2024, 09:48 AM
(This post was last modified: Mar-29-2024, 09:48 AM by Pedroski55.)
To continue the saga: Can you explain why you chose the ifs and elifs you chose? I can't understand why you made the choices you made.
These 2 functions let you run things as many times as you want, more or less using your code.
Try it out, see what you get!
from random import randint
def makeList():
move_count = position = direction = 0
frog_list = [randint(0, 20) for i in range(6)]
sorted_frogs = sorted(frog_list, reverse=True)
return (move_count, frog_list, sorted_frogs)
def loop():
start = makeList()
move_count = position = direction = start[0]
frog_list = start[1]
sorted_frogs = start[2]
while frog_list != sorted_frogs:
if move_count == 0:
print(f'Original frog_list = {frog_list}, position = {position}, direction = {direction}, move_count = {move_count}')
if direction == 0: # direction starts as 0
if frog_list[position] == frog_list[-2]: # why -2?
print('This is direction = 0, if 1')
print(f'frog_list[position] = {frog_list[position]} , frog_list[-2] = {frog_list[-2]}')
# simple bubble sort technique but how is that related to the above: if frog_list[position] == frog_list[-2]:??
print(f'frog_list[position] = {frog_list[position]}, frog_list[position + 1] = {frog_list[position + 1]}')
frog_list[position], frog_list[position + 1] = frog_list[position + 1], frog_list[position]
print(f'Swapped around: frog_list[position] = {frog_list[position]}, frog_list[position + 1] = {frog_list[position + 1]}')
position += 1
elif frog_list[position] == frog_list[-1]: # why -1?
print('This is elif 1')
direction = 1
elif frog_list[position + 2] > frog_list[position + 1]: # why +2 and plus +1?
print('This is direction = 0, elif 2')
print(f'frog_list[position + 2] = {frog_list[position + 2]}, frog_list[position + 1] = {frog_list[position + 1]}')
frog_list[position], frog_list[position + 2] = frog_list[position + 2], frog_list[position]
print(f'Swapped around: frog_list[position + 2] = {frog_list[position + 2]}, frog_list[position + 1] = {frog_list[position + 1]}')
position += 2
else:
# same bubble sort condition as above in first if of direction == 0
print('This is direction = 0, else')
print(f'frog_list[position] = {frog_list[position]}, frog_list[position + 1] = {frog_list[position + 1]}')
frog_list[position], frog_list[position + 1] = frog_list[position + 1], frog_list[position]
print(f'Swapped around: frog_list[position] = {frog_list[position]}, frog_list[position + 1] = {frog_list[position + 1]}')
position += 1
elif direction == 1:
if frog_list[position] == frog_list[1]: # why 1??
print('This is direction = 1, if 1')
print(f'frog_list[position] = {frog_list[position]}, frog_list[position - 1] = {frog_list[position - 1]}')
frog_list[position], frog_list[position - 1] = frog_list[position - 1], frog_list[position]
print(f'Swapped around: frog_list[position] = {frog_list[position]}, frog_list[position - 1] = {frog_list[position - 1]}')
position -= 1
elif frog_list[position] == frog_list[0]: # why 0?
print('This is direction = 1, elif 1')
direction = 0
elif frog_list[position - 2] < frog_list[position - 1]: # why -2 and -1?
print('This is direction = 1, elif 2')
print(f'frog_list[position] = {frog_list[position]}, frog_list[position - 2] = {frog_list[position - 2]}')
# reversed bubble sort condition
frog_list[position], frog_list[position - 2] = frog_list[position - 2], frog_list[position]
print(f'Swapped around: frog_list[position] = {frog_list[position]}, frog_list[position -2] = {frog_list[position - 2]}')
position -= 2
else:
print('This is direction = 1, else')
print(f'frog_list[position] = {frog_list[position]}, frog_list[position - 1] = {frog_list[position - 1]}')
# reversed bubble sort condition
frog_list[position], frog_list[position - 1] = frog_list[position - 1], frog_list[position]
print(f'Swapped around: frog_list[position] = {frog_list[position]}, frog_list[position - 1] = {frog_list[position - 1]}')
position -= 1
move_count += 1
print(f'frog_list = {frog_list}, position = {position}, direction = {direction}, move_count = {move_count}')Now just run loop() in your IDE.
Your solution definitely works, it just seems a bit random in the choices you make!
This might take a long time on a large list!
Posts: 6,221
Threads: 16
Joined: Feb 2020
You are making this so much harder than it has to be. There should be no "odd_leapfrog" or "even_leapfrog". There should be no "direction". There should be no "position + 1" or "position + 2". There shouldn't even be an "else" statement.
for n in range(1, len(frog_list)
if frog_list[n] != sorted_frogs[n]
move frog_list[n] to the empty_space
while the empty space is not frog_list[0]
move correct frog to empty space
n = n + 1That's all there is to it. The hardest part is finding what frog gets moved to the empty space, and that is simple since you have a sorted list of frogs that tells you where every frog belongs.
Posts: 832
Threads: 131
Joined: Jul 2017
Use the sorted list to sort the list you just sorted?
So the question is really: How did sorted sort the list? timsort?
I'm just surprised that the sort actually seems to work!
Posts: 6,221
Threads: 16
Joined: Feb 2020
Mar-29-2024, 10:55 PM
(This post was last modified: Mar-30-2024, 02:21 AM by deanhystad.)
If the sorting really bothers you, think of the frogs as A, B, C, D and E. The frogs rest on lily pads a, b, c, d and e. The goal is to move each frog to the corresponding lily pad using the least number of moves. The sorting only establishes the relationship between the frog's number (say 11) and the eventual landing place (frog_list[4]).
The task is to move the frogs into sorted order using the fewest number of moves. This is one of those problems where you know the final result and the task is to figure the best way to get there. An insertion sort would be the best choice EXCEPT there is also a restriction on how the "frogs" can be moved. Frogs can only be moved 1 at a time and must move to an empty spot.
For example, say you want to sort [1, 2, 3].
The first thing we do is add an empty landing spot.
Output: [0, 1, 2, 3]
The 1 and 3 frogs are out of order, so we move one of those frogs to the empty spot.
Output: [1, 0, 2, 3]
Now we can move the 3 frog to correct position.
Output: [1, 3, 2, 0]
And we can also move the 1 frog to the correct position. Moving is most efficient when each move opens a spot for the next move.
Output: [0, 3, 2, 1]
The frogs are in sorted order and it took 3 moves.
The minimum number of moves is zero when the frogs start in sorted order. if any frogs are out of order the minimum number of moves is the number of frogs out of order + 1. I ran tests on all permutations on [1, 2, 3, 4, 5] and counted how many "extra" moves were required.
Output: [(1, 84), (2, 35), (0, 1)]
Most puzzles only require 1 extra move, but 35 puzzles required 2 extra moves. When I increased the number of frogs to 6, I found 15 puzzles that required 3 extra moves, These are:
Output: [1, 2, 3, 4, 5, 6]
[1, 3, 2, 5, 4, 6]
[1, 4, 5, 2, 3, 6]
[2, 1, 3, 4, 6, 5]
[2, 3, 1, 5, 6, 4]
[2, 4, 5, 1, 6, 3]
[3, 1, 2, 6, 4, 5]
[3, 2, 1, 6, 5, 4]
[3, 4, 5, 6, 1, 2]
[4, 1, 6, 2, 3, 5]
[4, 2, 6, 1, 5, 3]
[4, 3, 6, 5, 1, 2]
[5, 6, 1, 2, 3, 4]
[5, 6, 2, 1, 4, 3]
[5, 6, 3, 4, 1, 2]
Notice that all of these follow a similar pattern. The out of position frogs are paired so that moving frog A to allow moving frog B opens up the spot for moving frog A. When frog A is moved, the open spot is moved back to zero. In [5, 6, 3, 4, 1, 2], moving any frog results in the "landing spot" getting moved back to zero in 2 moves.
Output: [0, 5, 6, 3, 4, 1, 2]
[5, 0, 6, 3, 4, 1, 2] <- Move to open up a spot for 6
[5, 6, 0, 3, 4, 1, 2] <- Moving 6 creates open spot for 5
[0, 6, 5, 3, 4, 1, 2] <- Moving 5 puts the open spot back in the zero position.
We want to avoid the landing spot going to zero, because it requires an extra move to create an open spot for moving a frog to the correct spot. Looking at the 15 puzzles I cannot find a way to reduce then number of moves.
MoreMoney likes this post
Posts: 832
Threads: 131
Joined: Jul 2017
Thanks for that!
The old clock finally ticked, I remember vaguely having heard of this frog puzzle in school!
Frog may only land on empty lilypad!
Got it at last!
Posts: 17
Threads: 5
Joined: Mar 2024
(Mar-30-2024, 07:54 AM)Pedroski55 Wrote: Thanks for that!
The old clock finally ticked, I remember vaguely having heard of this frog puzzle in school!
Frog may only land on empty lilypad!
Got it at last!
Thanks, i got the idea but i can't find the right code to do that, do you have code that can do my sort?
The best i can do is this
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)
Posts: 17
Threads: 5
Joined: Mar 2024
(Mar-29-2024, 10:55 PM)deanhystad Wrote: If the sorting really bothers you, think of the frogs as A, B, C, D and E. The frogs rest on lily pads a, b, c, d and e. The goal is to move each frog to the corresponding lily pad using the least number of moves. The sorting only establishes the relationship between the frog's number (say 11) and the eventual landing place (frog_list[4]).
The task is to move the frogs into sorted order using the fewest number of moves. This is one of those problems where you know the final result and the task is to figure the best way to get there. An insertion sort would be the best choice EXCEPT there is also a restriction on how the "frogs" can be moved. Frogs can only be moved 1 at a time and must move to an empty spot.
For example, say you want to sort [1, 2, 3].
The first thing we do is add an empty landing spot.
Output: [0, 1, 2, 3]
The 1 and 3 frogs are out of order, so we move one of those frogs to the empty spot.
Output: [1, 0, 2, 3]
Now we can move the 3 frog to correct position.
Output: [1, 3, 2, 0]
And we can also move the 1 frog to the correct position. Moving is most efficient when each move opens a spot for the next move.
Output: [0, 3, 2, 1]
The frogs are in sorted order and it took 3 moves.
The minimum number of moves is zero when the frogs start in sorted order. if any frogs are out of order the minimum number of moves is the number of frogs out of order + 1. I ran tests on all permutations on [1, 2, 3, 4, 5] and counted how many "extra" moves were required.
Output: [(1, 84), (2, 35), (0, 1)]
Most puzzles only require 1 extra move, but 35 puzzles required 2 extra moves. When I increased the number of frogs to 6, I found 15 puzzles that required 3 extra moves, These are:
Output: [1, 2, 3, 4, 5, 6]
[1, 3, 2, 5, 4, 6]
[1, 4, 5, 2, 3, 6]
[2, 1, 3, 4, 6, 5]
[2, 3, 1, 5, 6, 4]
[2, 4, 5, 1, 6, 3]
[3, 1, 2, 6, 4, 5]
[3, 2, 1, 6, 5, 4]
[3, 4, 5, 6, 1, 2]
[4, 1, 6, 2, 3, 5]
[4, 2, 6, 1, 5, 3]
[4, 3, 6, 5, 1, 2]
[5, 6, 1, 2, 3, 4]
[5, 6, 2, 1, 4, 3]
[5, 6, 3, 4, 1, 2]
Notice that all of these follow a similar pattern. The out of position frogs are paired so that moving frog A to allow moving frog B opens up the spot for moving frog A. When frog A is moved, the open spot is moved back to zero. In [5, 6, 3, 4, 1, 2], moving any frog results in the "landing spot" getting moved back to zero in 2 moves.
Output: [0, 5, 6, 3, 4, 1, 2]
[5, 0, 6, 3, 4, 1, 2] <- Move to open up a spot for 6
[5, 6, 0, 3, 4, 1, 2] <- Moving 6 creates open spot for 5
[0, 6, 5, 3, 4, 1, 2] <- Moving 5 puts the open spot back in the zero position.
We want to avoid the landing spot going to zero, because it requires an extra move to create an open spot for moving a frog to the correct spot. Looking at the 15 puzzles I cannot find a way to reduce then number of moves.
Thank you that's right, i stil got no idea how to make correct logic like your output
Posts: 832
Threads: 131
Joined: Jul 2017
Mar-31-2024, 10:59 AM
(This post was last modified: Mar-31-2024, 10:59 AM by Pedroski55.)
You could try this, it seems to work. This doesn't have any if logic that I do not understand.
from random import randint
# see if a list is in descending order
# shortcut out of the loop if True
def checkOrder(alist):
for i in range(len(alist) - 1):
if not alist[i] >= alist[i+1]:
return False
return True
# zero is at position 0 at the start
def swap(alist):
if not alist[0] == 0:
print('This is if not alist[0] == 0 ... ')
temp = alist[0]
#index0 = alist.index(0)
index_max = alist.index(max(alist))
final.append(alist[index_max])
alist[0] = alist[index_max]
alist[index_max] = temp
print(f'current list = {alist}, final = {final}')
else:
print('This is else: alist[0] == 0 ... ')
index_max = alist.index(max(alist))
temp = alist[index_max]
alist[index_max] = 0
alist[0] = temp
final.append(temp)
print(f'current list = {alist}, final = {final}')
return alist[1:len(alist)]
def loop(nl, moves):
while len(nl) >= 2:
print(f'nl before swap = {nl}')
nl = swap(nl)
if checkOrder(nl):
for n in range(len(nl)-1):
final.append(nl[n])
moves +=1
print(f'nl after swap and checkOrder() = {nl}, final = {final}, moves = {moves}')
return
moves +=1
print(f'nl after swap = {nl}, final = {final}, moves = {moves}')
return
for j in range(3):
print(f'\nloop {j+1}\n')
#frogs = [randint(1, 10) for i in range(6)]
frogs = [randint(1, 15) for i in range(15)]
frogs.insert(0, 0)
nl = frogs.copy()
final = [0]
moves = 0
loop(nl, moves)
|
