Order the cards

[bonanova]

You have three cards in front of you labeled in some order 1, 2 and 3, and three card-sized bins labeled with a letter that signifies Left, Middle and Right, in the order shown. The cards, all of which remain face up, have been placed at random in one or more bins, in such a way that, if any cards are stacked, only the top card is visible. And, if only two cards are visible, one cannot tell which bin holds the hidden card.

      +-----+   +-----+   +-----+
      |     |   |     |   |     |
  +---|  L  |---|  M  |---|  R  |---+
  |   |     |   |     |   |     |   |
  |   +-----+   +-----+   +-----+   |
  +---------------------------------+
You are to devise an algorithm that ends with all cards in the L bin with 1 on top and 3 on the bottom, in a bounded number of moves. Each move in the algorithm consists of taking a single card from the top of one pile and placing it on the top of another (possibly empty) pile. An independent observer will keep track of things and will signal completion.

Your algorithm, on the other hand, may not keep track of things. Each move it makes must take its cues only from the visible information at each point in the process. Specifically, a move cannot depend on any invisible cards, its previous move or the number of moves it has made. Further, it must be able to begin from a random starting point. A move might take the form "If a 2 is visible, move it one bin to the right." In that case, the 2 card would move to L if it happened to start in R. In that sense, the configuration functons as ring, with "move to the right" meaning CW, and "move to the left" meaning CCW.

To restate: For any configuration with one, two or three visible cards, distributed in any order in L, M and R, your algorithm must specify the next move to make. And since your algorithm can't distinguish an L stack of 1 2 3 from 1 3 2, it will be told when it has (successfully) completed.

[plasmid]

The four laws of card shifting

Spoiler

1. If you see [2] [Empty] [1], then move card 1 onto card 2.
2. If you see any empty slot(s), move the card to the left of the empty slot into the empty slot, unless doing so would conflict with law 1.
3. If there are no empty slots and card 3 is in the far left slot, then move card 2 onto card 3.
4. If there are no empty slots and card 3 in NOT in the far left slot, then move card 3 one slot to the right.

Edited February 5, 2018 by bonanova
Gold Star

[plasmid]

Any stipulation for what would make one algorithm superior to another -- fewest / simplest number of commands, or fewest maximum number of moves to reach the goal?
I believe I can do it with four fairly simple commands that will take a maximum of 12 moves.

[bonanova]

1 hour ago, plasmid said:

Any stipulation for what would make one algorithm superior to another -- fewest / simplest number of commands, or fewest maximum number of moves to reach the goal?
I believe I can do it with four fairly simple commands that will take a maximum of 12 moves.

Sounds like a solution.

[CaptainEd]

Good job!

[bonanova]

On 2/2/2018 at 10:08 AM, plasmid said:

The four laws of card shifting

  Hide contents

1. If you see [2] [Empty] [1], then move card 1 onto card 2.
2. If you see any empty slot(s), move the card to the left of the empty slot into the empty slot, unless doing so would conflict with law 1.
3. If there are no empty slots and card 3 is in the far left slot, then move card 2 onto card 3.
4. If there are no empty slots and card 3 in NOT in the far left slot, then move card 3 one slot to the right.

 

Start with this

Spoiler

[ 2 ]  [ - ]  [ 1/3 ]. Invoke Rule 1.
[ 1/2 ]  [ - ]  [ 3 ]. Invoke Rule 2.
[ 2 ]  [ 1 ]  [ 3 ].  Invoke Rule 4.
[ 3/2 ]  [ 1 ]  [ - ]. Invoke Rule 2.
[ 3/2 ]  [ - ]  [ 1 ]. Invoke Rule 2.
[ 2 ]  [ 3 ]  [ 1 ]. Invoke Rule 4.
[ 2 ]  [ - ]  [ 3/1 ]. Invoke Rule 2.
[ - ]  [ 2 ]  [ 3/1 ]. Invoke Rule 2.
[ 3 ]  [ 2 ]  [ 1 ]. Invoke Rule 3.
[ 2/3 ]  [ - ]  [ 1 ]. Invoke Rule 1.
[ 1/2/3 ]  [ - ]  [ - ]. FTW

Nice.