Stack the deck!

Question

Alice and Bob like to play a card game, with a deck of cards numbered with consecutive nonnegative integers.

Alice has a very particular way of shuffling the deck, though. First, she takes the top card from the deck and puts it at the bottom of the deck. Then she removes the next card, and starts a pile with it. Then, again she cycles the top card to the bottom, and puts the new top card onto the pile. She repeats this process until she's emptied the deck, at which point the pile is the new deck.

  deck     |  pile
-----------+-----------
 3 1 4 0 2 | 
 1 4 0 2 3 | 
 4 0 2 3   |         1
 0 2 3 4   |         1
 2 3 4     |       0 1
 3 4 2     |       0 1
 4 2       |     3 0 1
 2 4       |     3 0 1
 4         |   2 3 0 1
           | 4 2 3 0 1
 4 2 3 0 1 | 

^{Figure 1: Alice performs her shuffle on the 5-card deck "3, 1, 4, 0, 2". The backs of the cards are all facing left.}

One day, Bob announces he's taking a week's vacation. Alice, having nobody to play the game with, enlists her friend Eve. Now, Eve is a shameless cheater, so when she sees Alice's peculiar shuffle, she realizes that she can stack the deck beforehand to her advantage!

When Eve gets home after the first day, she does some analysis on the game and figures out that her best odds are when the cards are in the order 0, 1, 2, 3, 4, 5, ... She didn't catch how many cards were in the deck, though, so she hatches a harebrained scheme to write some code on her arm that, when run, takes the size of the deck and displays the order Eve needs to put the cards in, so that when Alice shuffles the deck, the final deck is in the order 0, 1, 2, 3, ...

It doesn't really matter to Eve what language the code is in (she knows them all), or whether the code is a function taking an integer argument and returning an array, or a full program taking input via a command line argument or STDIN and writing the results to STDOUT. She does, however, need the code as short as possible, to minimize the chance of Alice seeing it and catching her.

Immoral as it might be, can you guys help Eve out?

Example inputs and outputs:

in  out
 1  0
 2  0 1
 5  2 4 0 3 1
10  2 9 4 8 0 7 3 6 1 5
52  6 51 25 50 12 49 24 48 1 47 23 46 11 45 22 44 5 43 21 42 10 41 20 40 2 39 19
    38 9 37 18 36 4 35 17 34 8 33 16 32 0 31 15 30 7 29 14 28 3 27 13 26

Answer 1

GolfScript, 15 14 13 bytes

])~,{\+)\+}/`

Try it online.

Example

$ golfscript alice.gs <<< 10
[2 9 4 8 0 7 3 6 1 5]

How it works

])    # Collect the stack into an array and pop. This leaves [] below the input string.
~     # Interpret the input string.
,     # For input “N”, push the array [ 0 … N-1 ] (the pile).
{     # For each card on the pile:
  \+  # Put the card on top of the deck.
  )   # Remove a card from the bottom of the deck.
  \+  # Put the card on top of the deck.
}/    #
`     # Convert the deck into a string.

Answer 2

Julia, 83

u(n)=(a=[n-1:-1:0];l=Int[];[push!(l,shift!(push!(l,pop!(a)))) for i=1:length(a)];l)

The last element in the returned vector is the top of the deck.

Answer 3

Mathematica, 92 77 46 bytes

Expects the input in variable n:

l={};(l=RotateRight[{#-1}~Join~l])&/@Range@n;l

It's just literally playing the shuffle backwards, by moving over a card and then putting the bottom card on top.

EDIT: No need to keep track of the output stack, just iterate through the integers.

Answer 4

Python 2.7 - 57

d=[0]
for j in range(1,input()):d=[d.pop()]+[j]+d
print d

Nice and simple, just invert the shuffle. Fairly close to how Golfscript does it.

Answer 5

J (13 chars) and K (9)

As it turns out, it's a simple process to undo the shuffle, and APL-likes have the fold adverb / to help them out in making this as short as possible.

J takes 13 char with (_1|.,)/@i.@-, while K only needs 9: |(1!,)/!:. APL would be similarly terse.

Here's a step-by-step trace of the J version.

(_1|.,)/@i.@- 4                  NB. recall that J is right-associative
(_1|.,)/@i. - 4                  NB. u@v y  is  u v y
(_1|.,)/@i. _4                   NB. monad - is Negate
(_1|.,)/ i. _4                   NB. @
(_1|.,)/ 3 2 1 0                 NB. monad i. is Integers, negative arg reverses result
3 (_1|.,) 2 (_1|.,) 1 (_1|.,) 0  NB. u/ A,B,C  is  A u B u C
3 (_1|.,) 2 (_1|.,) _1 |. 1 , 0  NB. x (M f g) y  is  M f x g y
3 (_1|.,) 2 (_1|.,) _1 |. 1 0    NB. dyad , is Append
3 (_1|.,) 2 (_1|.,) 0 1          NB. dyad |. is Rotate
3 (_1|.,) _1 |. 2 , 0 1          NB. repeat ad nauseam
3 (_1|.,) _1 |. 2 0 1
3 (_1|.,) 1 2 0
_1 |. 3 , 1 2 0
_1 |. 3 1 2 0
0 3 1 2

You might notice that in the J, we reverse the array of integers first, but in the K we do it afterwards: this is because the K fold is more like a foldl, compared to the J's foldr.