Winnable Solitaire Mancala Boards

Question

Mancala is the name of a family of board games that usually involve a series of cups filled with beads that the players manipulate. This challenge will use a specific rule set for a solitaire variant of the game.

The board consists of a "basket" at one end, followed by an infinite number of cups, numbered starting from 1. Some of the cups will have some number of beads in them. If the nth cup has exactly n beads in it, you may "sow" the beads from it. Sowing means to take all n beads out of the cup, then deposit them one at a time in each cup towards the basket. The last bead will go into the basket. The player wins when all of the beads on the board are in the basket.

Clearly, there are many boards which are not winnable, such as if there is exactly one bead in the second cup. There are no legal plays because all the cups with 0 beads cannot be sown, and the second cup does not have enough beads to be sown. This is obviously no fun, so your task will be to create winnable boards.

Task

Given a positive integer representing a number of beads output a list of non-negative integers representing the number of beads that should be put in each cup to make a winnable board as described above. This list should not contain any trailing zeroes.

For any given number of beads, there is always exactly one winnable board configuration.

Demonstration

This is a demonstration of how to play the winnable board for and input of 4. The winnable board is [0, 1, 3]. We start with the only available move, sowing the beads from the third cup to get [1, 2, 0]. Now we actually have a choice, but the only correct one is sowing the first cup, getting: [0, 2, 0]. Then we sow the second cup yielding [1, 0, 0] and finally we sow the first cup again to get all empty cups.

Test cases:

1 => [1]
2 => [0, 2]
3 => [1, 2]
4 => [0, 1, 3]
5 => [1, 1, 3]
6 => [0, 0, 2, 4]
7 => [1, 0, 2, 4]
8 => [0, 2, 2, 4]
9 => [1, 2, 2, 4]
10 => [0, 1, 1, 3, 5]
11 => [1, 1, 1, 3, 5]
12 => [0, 0, 0, 2, 4, 6]
13 => [1, 0, 0, 2, 4, 6]
14 => [0, 2, 0, 2, 4, 6]
15 => [1, 2, 0, 2, 4, 6]
16 => [0, 1, 3, 2, 4, 6]
17 => [1, 1, 3, 2, 4, 6]
18 => [0, 0, 2, 1, 3, 5, 7]
19 => [1, 0, 2, 1, 3, 5, 7]
20 => [0, 2, 2, 1, 3, 5, 7]

Big thanks to PeterTaylor for coming up with a program to generate test cases!

Answer 1

CJam (21 bytes)

M{_0+0#_Wa*\)+.+}ri*`

Online demo

Explanation

I independently derived the "unplaying" technique mentioned in this paper. We prove by induction that there is exactly one winning board for a given number of beads.

Base case: with 0 beads, the only winning board is the empty one.

Inductive step: if we sow from cup k then at the next move cup k will be empty and every cup nearer the basket will contain at least one bead. Therefore we can find the unique winning board with n beads from the winning board with n-1 beads by looking for the lowest numbered empty cup, taking one bead from the basket and one from each cup below that empty cup, and placing them all in the empty cup.

Dissection

M           e# Start with an empty board
{           e# Loop
  _0+0#     e#   Find position of first 0 (appending to ensure that there is one)
  _Wa*      e#   Make array of that many [-1]s
  \)+       e#   Append the index plus 1 (since board is 1-indexed)
  .+        e#   Pointwise addition
}
ri*         e# Read integer from stdin and execute loop that many times
`           e# Format for display

Answer 2

Python, 42 41 bytes

m=lambda n,i=2:n*[1]and[n%i]+m(n-n%i,i+1)

Answer 3

JavaScript (ES6), 63 37 bytes

f=(n,d=2)=>n?[n%d,...f(n-n%d,d+1)]:[]

Port of @orlp's Python answer. Explanation: Consider the total number of beads in the ith and higher cups. Each play from one of these cups will remove i beads from that total. (For instance, if i is 3, and you play from the fifth cup, you reduce the number of beads in that cup by five, but you also add one to both the fourth and the third cups.) The total must therefore be a multiple of i. Now the i-1th cup cannot contain i or more beads, so in order for it to leave a multiple of i it must contain the remainder of the beads modulo i.

Previous explanation (from @xnor's link): The naive approach is the "reverse playing" technique. This uses the observation that making a play empties a cup, so reverse playing collects a bead from each cup and puts them in the first empty cup, like so (63 bytes):

f=n=>n?[...a=f(n-1),0].some((m,i)=>(m?a[i]--:a[i]=i+1)>m)&&a:[]

Now, just consider the first i cups. In the case that one of them is empty, reverse playing will add 1 to the total number of beads in those cups, while in the case that none of them is empty, reverse playing will subtract i from the total, however this is equivalent to adding 1 modulo i+1. After n reverse plays the sum of the beads in the first i cups will therefore be equivalent to n modulo i+1, or put it another way, the number of beads in the ith cup will be equivalent to n minus the sum of the beads in the preceding cups, modulo i+1. Now for the ith cup to be playable the number of beads cannot exceed i, so in fact it will equal the number of remaining beads modulo i+1. (Note that I use d=i+1 as it uses fewer bytes.)

Answer 4

Ruby, 36 bytes

A port of @orlp's answer because it's far too genius for me to think of anything better.

m=->n,i=2{n>0?[n%i]+m[n-n%i,i+1]:[]}