5
$\begingroup$

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.

enter image description here

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?

enter image description here

$\endgroup$
2

1 Answer 1

6
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.