# Sorting five plates

You have a stack of 5 plates of different sizes as shown in the left figure below. In each move you can pick up the top k plates (k is from 1 to 5) and flip them over. For example, if you do this with the top 3 plates you will get the result shown in the right figure below.

What is the least number of moves needed to reverse the order of the plates, while keeping them the right way up, as shown in the following figure?

9 moves by reversing 4, 5, 4, 5, 4, 5, 4, 5, 4 plates respectively.

Denoting the plates as 1, 2, 3, 4, 5 right way up and as 1R, 2R, 3R, 4R, 5R when upside down, after each operation we get these configurations:
4R 3R 2R 1R 5
5R 1 2 3 4
3R 2R 1R 5 4
4R 5R 1 2 3
2R 1R 5 4 3
3R 4R 5R 1 2
1R 5 4 3 2
2R 3R 4R 5R 1
5 4 3 2 1

My approach was to consider every possible arrangement of plates as a state, then we can have no more than 10x8x6x4x2 = 3840 possible states, then use breadth first search to find shortest path to the desired state. Code

Edit:

For any n > 1 number of starting plates, we can reverse the order of plates using 2n-1 steps: flip n-1, n, n-1, n, ..., n-1, n, n-1 plates. This appears to be the minimal answer.

• Beautiful code. Jan 8, 2023 at 13:12
• Nice to know about the generalization! Jan 8, 2023 at 13:49