Mancala es el nombre de una familia de juegos de mesa que generalmente implican una serie de tazas llenas de cuentas que los jugadores manipulan. Este desafío utilizará un conjunto de reglas específicas para una variante de solitario del juego.

El tablero consiste en una "canasta" en un extremo, seguido de un número infinito de tazas, numeradas a partir del 1. Algunas de las tazas tendrán cierto número de cuentas. Si la ncopa tiene exactamente ncuentas, puede "sembrarlas". Sembrar significa sacar todas las ncuentas de la taza, luego depositarlas una a la vez en cada taza hacia la canasta. La última cuenta irá a la canasta. El jugador gana cuando todas las cuentas en el tablero están en la canasta.

Claramente, hay muchas tablas que no se pueden ganar, como si hubiera exactamente una cuenta en la segunda copa. No hay jugadas legales porque no se pueden sembrar todas las copas con 0 cuentas, y la segunda copa no tiene suficientes cuentas para sembrar. Obviamente, esto no es divertido, por lo que su tarea será crear tableros ganables.

Tarea

Dado un número entero positivo que representa una cantidad de cuentas, se obtiene una lista de números enteros no negativos que representan la cantidad de cuentas que se deben colocar en cada taza para formar un tablero que se pueda ganar como se describió anteriormente. Esta lista no debe contener ceros finales.

Para cualquier número de cuentas, siempre hay exactamente una configuración de tablero que se puede ganar.

Demostración

Esta es una demostración de cómo jugar el tablero ganable y la entrada de 4. El tablero ganable es [0, 1, 3]. Comenzamos con el único movimiento disponible, sembrando las cuentas de la tercera copa para obtener [1, 2, 0]. Ahora tenemos realmente una opción, pero la única correcta es la siembra de la primera taza, consiguiendo: [0, 2, 0]. Luego sembramos la segunda copa [1, 0, 0]y finalmente sembramos la primera copa nuevamente para obtener todas las tazas vacías.

Casos de prueba:

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]

¡ Muchas gracias a PeterTaylor por crear un programa para generar casos de prueba!

CJam (21 bytes)

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

Demostración en línea

Explicación

Obtuve independientemente la técnica de "reproducción" mencionada en este artículo . Probamos por inducción que hay exactamente una tabla ganadora para un número dado de cuentas.

Caso base: con 0 cuentas, el único tablero ganador es el vacío.

Paso inductivo: si sembramos desde la copa k, en el próximo movimiento la copa kestará vacía y cada copa más cerca de la canasta contendrá al menos una cuenta. Por lo tanto, podemos encontrar el tablero ganador único con ncuentas del tablero ganador con n-1cuentas buscando la taza vacía con el número más bajo, tomando una cuenta de la canasta y una de cada taza debajo de esa taza vacía, y colocándolas todas en la taza vacía.

Disección

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

Python, 42 41 bytes

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

JavaScript (ES6), 63 37 bytes

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

Puerto de la respuesta Python de @ orlp. Explicación: Considere el número total de cuentas en las icopas th y superiores. Cada jugada de una de estas tazas eliminará las icuentas de ese total. (Por ejemplo, si ies 3 y juegas desde la quinta copa, reduces el número de cuentas en esa copa en cinco, pero también agregas una a las copas cuarta y tercera). Por lo tanto, el total debe ser un múltiplo de i. Ahora la i-1copa no puede contener io más cuentas, por lo que para que salga un múltiplo idebe contener el resto del módulo de cuentas i.

Explicación previa (del enlace de @ xnor): El enfoque ingenuo es la técnica de "juego inverso". Esto utiliza la observación de que hacer una jugada vacía una copa, por lo que el juego inverso recoge una cuenta de cada copa y las coloca en la primera copa vacía, así (63 bytes):

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

Ahora, solo considera las primeras itazas. En el caso de que uno de ellos esté vacío, el juego inverso se sumará 1al número total de cuentas en esas tazas, mientras que en el caso de que ninguno de ellos esté vacío, el juego inverso se restará idel total, sin embargo, esto es equivalente a agregar un 1módulo i+1. Después de que los njuegos inversos la suma de las cuentas en las primeras icopas será, por lo tanto, equivalente al nmódulo i+1, o dicho de otro modo, el número de cuentas en la icopa th será equivalente a nmenos la suma de las cuentas en las tazas anteriores, módulo i+1. Ahora, para que la icopa sea jugable, el número de cuentas no puede exceder i, por lo que de hecho será igual al número de cuentas restantes móduloi+1. (Tenga en cuenta que lo uso d=i+1ya que usa menos bytes).

Ruby, 36 bytes

Un puerto de la respuesta de @ orlp porque es demasiado genial para mí pensar en algo mejor.

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