Stack Exchanging

Question

Problem

Say you have N stacks named S₁ through S_N, where each S_k (k = 1 to N) contains N copies of the number k.

For example, when N = 3 the stacks looks like this:

1  2  3  <- top of stack
1  2  3
1  2  3  <- bottom of stack
=======
1  2  3  <- stack index

^{Here there are 3 stacks indexed as 1, 2, and 3, and each one contains N instances of its own index.}

The goal is to rearrange the N stacks such that each of them identically contains the numbers 1 through N in order from top to bottom.

e.g. for N = 3 the goal is to rearrange the stacks into:

1  1  1
2  2  2
3  3  3
=======
1  2  3

The only action you can perform with the stacks is taking the top number from one of the stacks (popping) then immediately placing it on top of a different stack (pushing). This is subject to these stipulations:

• A number can only be pushed onto a stack if it is less than or equal to the top number on that stack.

  • e.g. a 1 can be pushed onto a stack with a 1, 2, or 3 at the top, but a 2 can only be pushed onto a stack with a 2 or 3 (or higher) at the top.

  • This has the effect that stacks are always monotonically increasing from top to bottom.

• Any nonempty stack may be popped from, and, assuming the previous bullet is satisfied, any stack may be pushed to.

• Any number may be pushed onto an empty stack.

• Stacks have no maximum height limit.

• Stacks cannot be created or destroyed, there are always N of them.

This challenge is about deciding which pops and pushes to do in order to complete the stack exchange, not necessarily in the fewest moves, but in a surefire way.

(Practicing with a deck of cards is a good way to get a feel for the problem.)

Challenge

Write a program or function that takes in a positive integer N, guaranteed to be 3 or above. Print or return a string that denotes all the pop-push actions required to rearrange the stacks from the initial state:

1  2  3  4  5
1  2  3  4  5
1  2  3  4  5
1  2  3  4  5
1  2  3  4  5
=============
1  2  3  4  5

^{(N = 5 case)}

To the final state:

1  1  1  1  1
2  2  2  2  2
3  3  3  3  3
4  4  4  4  4
5  5  5  5  5
=============
1  2  3  4  5

Every line in your output must contain two numbers separated by a space. The first number is the index of the stack to pop from and the second number is the index of the stack to push to. Performing the actions of all the lines in order should arrange the stacks correctly without breaking any rules.

For example, here is a potential valid output for the N = 3 case:

1 2  [move the top number on stack 1 to the top of stack 2]
1 2  [repeat]
1 2  [repeat]
3 1  [move the top number on stack 3 to the top of stack 1]
2 3  [etc.]
2 3
2 3
2 1
2 1
2 1
3 1
3 1
3 1
3 2
1 2
1 2
1 2
1 3
2 3
2 3
2 3
1 2
3 2
3 1

Notes

• Your output does not need to be optimal, only correct. i.e. you do not need to minimize the number of pops and pushes.

  • So it would be alright if, say, some move were repeatedly made and immediately reversed.
  • Popping and pushing to the same stack in one move, e.g. 2 2, is allowed as well (though of course pointless).

• Your output does need to be deterministic and finite.

• Remember that stacks have 1-based indexing. 0-based indexing is not allowed.

• N greater than 9 should of course work just as well as single digit N.

• If desired you may use any two distinct, non-digit printable ASCII characters in place of spaces and newlines. A trailing newline (or newline substitute) in the output is fine.

Scoring

The shortest code in bytes wins. Tiebreaker is higher voted answer.

Valueless brownie points if you can show your algorithm is optimal.

Answer 1

Pyth 96 94 bytes

Mt*Q+++bGdHM|%+y_GHQQg1 2++Qd1g2 3g2 1g3 1++Qd2Vr3QgNtN++QdN;g1QVStQVStQI<NHgnNHnNtH)++nN0dnNH

Try it here

How does it work?

This explanation will be using N=5.

Part 1: Create the bottom layer on every stack

The reason why this is needs a separate piece of code is because every stack needs to be used: the first 4 need a 5 to be put beneath them, and the last stack must provide the 5s. This means that we can't just move all the 4s somewhere, put a 5 there, and move the 4s back.

Visualization: (parentheses mean what will be moved)

     _
11111 |
22222 |_ Can't move 4s here, not monotonically increasing
33333_|
(44444)------------??? Where to put the 4s?
55555 <- Must supply the 5 that will be moved

Instead, to do this first exchange, we will first move all the 1s over to to the second stack, move a 5 to the first stack (which is now empty), move the 1s to the third stack, move the 2s to the first stack, move the 1s back to the first stack, and finally move a 5 to the second stack.

(11111)-----.
2222211111<-'
===============================
5<---------.
2222211111 : (from stack 5)
===============================
5
22222(11111)-.
3333311111<--'
===============================
522222<-.
(22222)-'
3333311111
===============================
52222211111<-.
             |
33333(11111)-'
===============================
52222211111
5<-----.
33333  |
44444  |
555(5)-'

Now that we have a free space to move stacks into (stack 2, which only contains a 5 that is placed in the right spot), we can move all the 3s to stack 2 and place a 5 in stack 3. We can then repeat the same thing for stack 4, and now we get all the 5s in the right place! And just one more thing: we will move all the 1s to stack 5 so that we get a nice setup for the next stack exchange.

522222(11111)-.
533333        |
544444        |
5             |
511111<-------'

Part 2: Do everything else :)

This is much easier now, because now we will always have a free stack to move other numbers we need to juggle around into. So, first we figure out where the 4 is. A bit of examination will show that it will always be 1 up from where it started, or 2 above the last stack. Now, we just keep going down the stacks, placing a 4 in the stack if it's free, or moving the other numbers up 1 stack if it's not. Now we have all the 4s in place.

522222<------.
533333<----. |
544444-.-.-'-'
5<-----' |
511111<--'
===============================
5433333
54
54
5411111
5422222

Now, we realize that the 3s are 2 stacks above where the 4s where. This means that we can do the exact same thing we did with the 4s! And as it turns out, we can keep doing this as long as we wrap the stack index around to the other side.

5433333-'wrap around 543
54                   543
54                   54311111
5411111 .----------->54322222
5422222 |2 stacks up 543

And so, we can keep doing this until we have exchanged all the stacks.

Code explanation:

First of all: The (important) predefined variables.

Q: Evaluated input.
b: The newline character, '\n'
d: A space, ' '

There are 2 lambda definitions.

M           | g(G)(H), used for moving Q numbers at a time.
            | We will call these Q numbers a "(number) block"
 t          | Tail, used to remove beginning newline
  *Q        | Repeat the following Q times
    +++bGdH | '\n' + G + ' ' + H. Just a whole bunch of concatenating.
            |
M           | n(G)(H), used for figuring out which stacks to move from
 |       Q  | If the following code is 0 (false), then use Q instead
  %     Q   | Mod Q
   +   H    | Add H
    y       | Multiply by 2
     _G     | Negate (remember in the explanation part 2? Always 2 stacks above?)

The stack exchanging: part 1

g1 2                       | Move the 1 block to stack 2
    ++Qd1                  | Move a Q to stack 1
         g2 3              | Move the 1 block to stack 3
             g2 1          | Move the 2 block to stack 1
                 g3 1      | Move the 1 block back to stack 1
                     ++Qd2 | Move a Q to stack 2
 v---Code-continuation---' |I don't have enough room!!!
Vr3Q                       | For N in range(3, Q)
    gNtN                   | Move the number block in stack N up 1
        ++QdN              | Move a Q to stack N
             ;g1Q          | End for loop; move the 1 block to the last stack

The stack exchanging: part 2

VStQ                           | For N in [1, 2, ..., Q - 1]
    VStQ                       | For H in [1, 2, ..., Q - 1]
        I<NH                   | If N < H
            g                  | Number block move
             nNH               |  (find number block)
                nNtH           |  (find the previous stack)
                    )          | End "For H"
                     ++nN0dnNH | Find start, move number to next location down

I already know I'm not getting brownie points, cuz I can see many more efficient and more complicated methods :(