Sorting Steps

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