Sorting Steps

MoreMoney · (This post was last modified: Mar-26-2024, 02:17 PM by MoreMoney.)

I'm trying to make the output on the code

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)

Currently it show

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

[Program finished]

I want the output to show the steps like this instead:

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

Attempt : maybe i can use this, but don't know how to implement it

 if list[-1] != 1:
    list[list.index(0)], list[-1] = list[-1], list[list.index(0)]
    list[-1], list[list.index(1)] = list[list.index(1)], list[-1]

if list[-2] != 2:
    list[list.index(0)], list[-2] = list[-2], list[list.index(0)]
    list[-1], list[list.index(2)] = list[list.index(2)], list[-1]

**deanhystad** · Mar-26-2024, 02:27 PM

I don't understand your question. Why would you not use the frog puzzle solution you already posted and use 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

to replace:

frog_count = int(input('Enter the number of frogs: '))
 
print()
 
min_interval = int(input('Enter the minimum interval: '))
max_interval = int(input('Enter the maximum interval: '))
 
print()
 
from random import randint
frog_list = [0] if frog_count >= 1 else []
sorted_list = []
 
for index in range(1, frog_count + 1):
    random_value = randint(min_interval, max_interval)
    frog_list.append(random_value)
    sorted_list.append(random_value)
 
print(frog_list)
 
sorted_list.sort(reverse=True)

MoreMoney · (This post was last modified: Mar-26-2024, 03:22 PM by MoreMoney.)

(Mar-26-2024, 02:27 PM)deanhystad Wrote: I don't understand your question. Why would you not use the frog puzzle solution you already posted and use 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

to replace:

frog_count = int(input('Enter the number of frogs: '))
 
print()
 
min_interval = int(input('Enter the minimum interval: '))
max_interval = int(input('Enter the maximum interval: '))
 
print()
 
from random import randint
frog_list = [0] if frog_count >= 1 else []
sorted_list = []
 
for index in range(1, frog_count + 1):
    random_value = randint(min_interval, max_interval)
    frog_list.append(random_value)
    sorted_list.append(random_value)
 
print(frog_list)
 
sorted_list.sort(reverse=True)

Thank you for your help and follow up, i attempt to replace it but not working, what did i do wrong?

 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[1:] != sorted_list:
        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)

Output:Enter Frogs: 5 1 3 4 2
[0, 5, 1, 3, 4, 2]
Traceback (most recent call last):
  File "/data/user/0/ru.iiec.pydroid3/files/accomp_files/iiec_run/iiec_run.py", line 31, in <module>
    start(fakepyfile,mainpyfile)
  File "/data/user/0/ru.iiec.pydroid3/files/accomp_files/iiec_run/iiec_run.py", line 30, in start
    exec(open(mainpyfile).read(),  __main__.__dict__)
  File "<string>", line 16, in <module>
NameError: name 'sorted_list' is not defined

[Program finished]

Maybe i should change line 16 with something?
Thank you

My goal is to get this 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

**deanhystad** · Mar-26-2024, 03:24 PM

I think you can figure this one out.

MoreMoney · (This post was last modified: Mar-26-2024, 03:40 PM by MoreMoney.)

(Mar-26-2024, 03:24 PM)deanhystad Wrote: I think you can figure this one out.

Thank you for your help, i trying to replace the name one by one like sorted_frogs, sorted_list, but they create infinite loop, may you give me hint? :) maybe i using wrong code?

**deanhystad** · Mar-26-2024, 04:09 PM

While loop should be:

    while frog_list != sorted_list:

MoreMoney

(Mar-26-2024, 04:09 PM)deanhystad Wrote: While loop should be:
    while frog_list != sorted_list:

Thank you, but it seems doesn't make any difference? Maybe there is more thing i should do?

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_list:
        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)

Output:Enter Frogs: 5 1 3 4 2
[0, 5, 1, 3, 4, 2]
Traceback (most recent call last):
  File "/data/user/0/ru.iiec.pydroid3/files/accomp_files/iiec_run/iiec_run.py", line 31, in <module>
    start(fakepyfile,mainpyfile)
  File "/data/user/0/ru.iiec.pydroid3/files/accomp_files/iiec_run/iiec_run.py", line 30, in start
    exec(open(mainpyfile).read(),  __main__.__dict__)
  File "<string>", line 16, in <module>
NameError: name 'sorted_list' is not defined

[Program finished]

Or how about this, why the steps is inefficient? Line 16 sorted_frogs(?)

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)

Output: Enter Frogs: 5 1 3 4 2
[0, 5, 1, 3, 4, 2]
[5, 0, 1, 3, 4, 2]
[5, 3, 1, 0, 4, 2]
[5, 3, 1, 4, 0, 2]
[5, 3, 1, 4, 2, 0]
[5, 3, 1, 4, 2, 0]
[5, 3, 1, 4, 0, 2]
[5, 3, 0, 4, 1, 2]
[5, 0, 3, 4, 1, 2]
[0, 5, 3, 4, 1, 2]
[0, 5, 3, 4, 1, 2]
[5, 0, 3, 4, 1, 2]
[5, 4, 3, 0, 1, 2]
[5, 4, 3, 2, 1, 0]
[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]
Minimum number of moves:  19

[Program finished]

My goal is to make this output instead

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

Thank you

**deanhystad** · Mar-27-2024, 02:39 AM

You have to do your own homework

Pedroski55 · Mar-27-2024, 09:34 AM

Following your private message:

1. It seems a bit strange to me to check your sort method by using sorted(). If you have already sorted, why do it again?
2. Why make life difficult by adding 0 at the beginning? Add zero after sorting if you really need a 0 there.

Python implements timsort for sorting. Have a look here for various sorting methods and how efficient they are.

Quote:The Timsort Algorithm in Python
The Timsort algorithm is considered a hybrid sorting algorithm because it employs a best-of-both-worlds combination of insertion sort and merge sort. Timsort is near and dear to the Python community because it was created by Tim Peters in 2002 to be used as the standard sorting algorithm of the Python language.

nums = '5 1 3 4 2'
frog_list = [int(x) for x in nums.split()]
move_count = position = direction = 0
sorted_frogs = sorted(frog_list, reverse=True)
              
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(f'{frog_list}, moves = {move_count}, position = {position}, direction = {direction}')

You can see from the output that it works, but the 5 bounces around in the first 6 lines. Fix that if you can.

If you really need 0 do this after sorting:

frog_list.insert(0, 0)

**deanhystad** · (This post was last modified: Mar-27-2024, 07:00 PM by deanhystad.)

@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(

Possibly Related Threads…
Thread		Author	Replies	Views	Last Post
	Next steps for using API data	Rebster	6	2,560	Oct-10-2020, 05:35 PM Last Post: perfringo
	Keep Toggle View through Slider Steps	yourboyjoe	1	1,684	Aug-10-2020, 07:32 PM Last Post: Yoriz
	Files to store configuration and steps for a industrial process control application	Danieru	1	1,803	Aug-03-2020, 05:43 PM Last Post: buran
	Pexpect baby steps	slouw	9	7,954	May-23-2019, 10:21 AM Last Post: heiner55
	Sorting a copied list is also sorting the original list ?	SN_YAZER	3	3,088	Apr-11-2019, 05:10 PM Last Post: SN_YAZER
	first steps with python3	hunnimonstr	5	4,572	Jul-03-2017, 08:49 PM Last Post: hunnimonstr

Sorting Steps

User Panel Messages

Announcements