15
\$\begingroup\$

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
\$\endgroup\$
  • 3
    \$\begingroup\$ Lovely phrasing, I'll get cracking. \$\endgroup\$ – ɐɔıʇǝɥʇuʎs May 21 '14 at 18:15
  • \$\begingroup\$ It's slightly confusing that your stacks are aligned at the top. And stating the order of the stack explicitly would also help clarify the question a bit. \$\endgroup\$ – Martin Ender May 21 '14 at 18:29
  • \$\begingroup\$ The same goes for the deck. \$\endgroup\$ – Martin Ender May 21 '14 at 18:39
  • \$\begingroup\$ Also: are you trying to trick us by having a sample of length 5? Without wishing to spoil: shuffle(shuffle(range(5))) == range(5)... \$\endgroup\$ – ɐɔıʇǝɥʇuʎs May 21 '14 at 18:40
  • \$\begingroup\$ @Synthetica I guess it so happens that Alice's shuffle on a 5-card deck is an involution. I didn't really think about it when posting because it doesn't hold in general. \$\endgroup\$ – algorithmshark May 21 '14 at 18:48
5
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ You might use {}/ instead of the map operator to save a char. \$\endgroup\$ – Howard May 22 '14 at 7:19
  • \$\begingroup\$ Thanks! I wanted an array, so I used map. Force of habit... \$\endgroup\$ – Dennis May 22 '14 at 13:19
  • 1
    \$\begingroup\$ ]( as the first two chars effectively puts an empty array under the input, saving you a later []\ . \$\endgroup\$ – Peter Taylor May 22 '14 at 13:27
  • \$\begingroup\$ Thanks! It took me way too long to figure out why this wasn't working with the online interpreter. Forgot to clear the stack... \$\endgroup\$ – Dennis May 22 '14 at 13:47
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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