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:
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.
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.
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]
[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]