Алиса и Боб любят играть в карточную игру с колодой карт, пронумерованных последовательными неотрицательными целыми числами.

У Алисы есть особый способ перетасовать колоду. Сначала она берет верхнюю карту из колоды и кладет ее на дно колоды. Затем она удаляет следующую карту и начинает с нее колоду. Затем она снова переключает верхнюю карту на нижнюю и кладет новую верхнюю карту в колоду. Она повторяет этот процесс до тех пор, пока не опустошит колоду, и в этот момент колода является новой колодой.

  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 | 

^{Рисунок 1: Алиса выполняет перетасовку в колоде из 5 карт «3, 1, 4, 0, 2». Оборотные стороны карточек обращены влево.}

Однажды Боб объявляет, что он берет отпуск на неделю. Алиса, не имея никого, кто мог бы сыграть в эту игру, завербовала свою подругу Еву. Теперь, Ева - бесстыдный мошенник, поэтому, когда она видит своеобразную перетасовку Алисы, она понимает, что может заранее сложить колоду в свою пользу!

Когда Ева возвращается домой после первого дня, она делает некоторый анализ игры и выясняет, что ее лучшие шансы, когда карты в порядке 0, 1, 2, 3, 4, 5, ... Она не сделала поймать, сколько карт было в колоде, поэтому она вынашивает заумную схему, чтобы написать на руке какой-то код, который при запуске принимает размер колоды и отображает порядок, в котором Ева должна положить карты, чтобы, когда Алиса тасует колоду, последняя колода имеет порядок 0, 1, 2, 3, ...

Ева на самом деле не имеет значения, на каком языке написан код (она знает их все), или является ли код функцией, принимающей целочисленный аргумент и возвращающей массив, или полной программой, принимающей ввод через аргумент командной строки или STDIN и запись результатов в STDOUT. Однако ей нужен максимально короткий код, чтобы минимизировать вероятность того, что Алиса увидит его и поймает ее.

Аморально, как это может быть, вы, ребята, можете помочь Еве?

Пример входов и выходов:

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

GolfScript, 15 14 13 байт

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

Попробуйте онлайн.

пример

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

Как это устроено

])    # 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.

Юлия, 83

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

Последний элемент в возвращаемом векторе - это верх колоды.

Mathematica, 92 77 46 байтов

Ожидает ввод в переменную n:

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

Это просто буквальное воспроизведение шаффла задом наперед, перемещая карту и кладя верхнюю карту сверху.

РЕДАКТИРОВАТЬ: не нужно отслеживать выходной стек, просто итерации по целым числам.

Python 2.7 - 57

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

Красиво и просто, просто переверните шаффл. Довольно близко к тому, как это делает Golfscript.

J (13 символов) и K (9)

Как выясняется, отменить перемешивание - это простой процесс, и у APL-лайков есть складное наречие, /которое поможет им сделать это как можно короче.

J занимает 13 полукокса с (_1|.,)/@i.@-, а К нужно только 9: |(1!,)/!:. APL будет так же кратко.

Вот пошаговая трассировка версии J.

(_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

Вы можете заметить , что в J, мы поменяем массив целых чисел первого, но в K мы делаем это впоследствии: это потому , что K складка больше как foldl, по сравнению с J - х foldr.