# Chaotic Number Shuffling

You have a deck of cards, consisting of cards with non-negative numbers on them, and you haven't shuffled it yet, and no player trusts the other players to be fair at shuffling. You devise a way to shuffle the deck that is completely deterministic, but chaotic enough that the other players are okay with using it. Here's how you perform a single shuffle:

1. Start with the deck face down. There are a series of M empty piles (where M is the maximum number in the deck) labeled as the 1st, 2nd, 3rd, ... ,Mth pile, and there is also an empty storage pile.

2. While the deck is not empty, do the following: Take the first card off the top of the deck, let N be its number and put the card face down on the top of the storage pile. If there are at least N cards left in the deck, deal the top N cards face down such that the top card goes in the 1st pile, the second card from the top goes in the 2nd pile, etc. until the Nth card gets put in the Nth pile. If there are fewer than N cards in the deck, deal all of them.

3. Construct the new deck by putting the first pile on the storage pile, then the second pile on the new pile, then the third pile on that new pile, then the fourth pile on that one, until all piles are in your deck.

This method is pretty intuitive when doing by hand, but after a few games some players want a computer to do it, due to the deep-seated mistrust within the group and a few lucky draws. They refuse to use other deck shuffling programs that would work better. Write a program that takes as input a list of non-negative integers (in some format you specify) and shuffles it once using this method, outputting the result. You may assume the integers and the length of the list are less than 2^16.

Here are some worked-out examples (layout is deck|storage|1st|2nd|3rd|...|Mth, cards go from bottom to top):

9,8,7,6,5,4,3,2,1,0|||||||||||
9,8,7,6,5,4,3,2,1|0||||||||||
9,8,7,6,5,4,3|0,1|2|||||||||
9,8,7|0,1,3|2,4|5|6|||||||
|0,1,3,7|2,4,8|5,9|6|||||||
0,1,3,7,2,4,8,5,9,6||||||||||| (starting another iteration)
0,1,3|6|9|5|8|4|2|7||||
|6,3|9,1|5,0|8|4|2|7||||
6,3,9,1,5,0,8,4,2,7|||||||||||


Here is a long string of successive shuffles:

[9,8,7,6,5,4,3,2,1,0]->[0,1,3,7,2,4,8,5,9,6]->[6,3,9,1,5,0,8,4,2,7]->
[7,3,2,6,4,8,0,5,1,9]->[9,1,5,0,8,4,6,2,3,7]->[7,1,3,9,2,6,4,8,0,5]->
[5,9,0,3,8,1,4,7,6,2]->[2,4,9,6,1,5,7,8,3,0]->[0,3,1,9,8,6,4,7,2,5]->
[5,9,2,1,7,3,4,0,6,8]->[8,5,6,0,4,3,7,1,2,9]->[9,2,1,7,3,4,0,6,5,8]


Another few:

[1,0,1,0]->[0,1,1,0]->[0,1,0,1]->[1,1,0,0]->[0,0,1,1]->[1,0,0,1]->[1,0,1,0]
[1,1,1,0]->[0,1,1,1]->[1,1,1,0]
[1,0,1,1]->[1,0,1,1]
[4,3,2,1]->[1,3,2,4]->[4,2,3,1]->[1,2,3,4]->[4,3,2,1]
[1,2,1,2,1,2]->[2,1,1,1,2,2]->[2,1,2,2,1,1]->[1,2,2,1,2,1]->[1,1,2,2,2,1]


# Perl 5, 81 bytes

A naive approach (just shuffling per the specs). Doubtless someone will find a shorter way to do it (even in Perl 5, I mean).

{while(@_){for(1..($.=pop)){push@{$a[$_]},pop}push@{$a[0]},$.}$,=$/;say@$_ for@a}


This is a subroutine, but what it prints (not returns) is the shuffled deck. It requires -M5.01 (which is free).

$perl -M5.01 -e'sub{while(@_){for(1..($.=pop)){push@{$a[$_]},pop}push@{$a[0]},$.}$,=$/;say@\$_ for@a}->(9,8,7,6,5,4,3,2,1,0)'
0
1
3
7
2
4
8
5
9
6


It also adds extra newlines in various places (depending on the deck), but there's… well, nothing technically in the specs forbidding that. :-)

# Ruby, 91 bytes

There is probably a better way to create an array of arrays. There's probably a shorter way to do all the shuffling, too. We'll see what future answers and comments bring to the table and all golfing suggestions are welcome.

->d{z=(1..d.size).map{[]};([d[-1]+1,d.size].min.times{|i|z[i]<<d.pop})while d[0];z.flatten}


Ungolfing:

def shuffle(deck)
# an array of arrays
z = (1..deck.size).map{[]}

# while there are still cards in the deck
while deck[0]
# if we're almost out of cards, use how many are left
# else, put in deck[-1] + 1 in the piles (that is, including deck[-1])
card = [deck[-1] + 1, deck.size].min
card.times do |i|
z[i] << deck.pop
end
end

# flatten all of those arrays done and return
return z.flatten
end