Mancala é o nome de uma família de jogos de tabuleiro que geralmente envolve uma série de xícaras cheias de contas que os jogadores manipulam. Esse desafio usará um conjunto de regras específico para uma variante de paciência do jogo.

O tabuleiro consiste em uma "cesta" em uma extremidade, seguida por um número infinito de xícaras, numeradas a partir de 1. Algumas das xícaras terão algum número de contas nelas. Se o ncopo estiver exatamente com ncontas, você pode "semear" as contas. Semear significa tirar todas as ncontas do copo e depositá-las uma de cada vez em cada copo na direção da cesta. A última conta irá para a cesta. O jogador ganha quando todas as contas no tabuleiro estão na cesta.

Claramente, existem muitas pranchas que não podem ser ganhadas, como se houvesse exatamente uma conta no segundo copo. Não há jogos legais porque todos os copos com 0 contas não podem ser semeados, e o segundo copo não tem contas suficientes para serem semeadas. Obviamente, isso não é divertido, então sua tarefa será criar pranchas vencíveis.

Tarefa

Dado um número inteiro positivo representando um número de contas, é apresentada uma lista de números inteiros não negativos que representam o número de contas que devem ser colocadas em cada copo para formar uma placa que pode ser vencida, conforme descrito acima. Esta lista não deve conter zeros à direita.

Para um determinado número de contas, sempre há exatamente uma configuração de placa que pode ser vencida.

Demonstração

Esta é uma demonstração de como jogar o tabuleiro vencível e a entrada de 4. O tabuleiro vencível é [0, 1, 3]. Começamos com o único movimento disponível, semeando as contas do terceiro copo para obter [1, 2, 0]. Agora nós realmente temos uma escolha, mas a única correta é semear o primeiro copo, ficando: [0, 2, 0]. Então semeamos o segundo copo cedendo [1, 0, 0]e finalmente semeamos o primeiro copo novamente para obter todos os copos vazios.

Casos de teste:

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]

Muito obrigado a PeterTaylor por apresentar um programa para gerar casos de teste!

CJam (21 bytes)

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

Demonstração online

Explicação

Eu deduzi independentemente a técnica "não-tocante" mencionada neste artigo . Provamos por indução que existe exatamente um tabuleiro vencedor para um determinado número de contas.

Caixa base: com 0 contas, o único tabuleiro vencedor é o vazio.

Passo indutivo: se semearmos do copo k, no próximo passo o copo kestará vazio e cada copo mais próximo da cesta conterá pelo menos um cordão. Portanto, podemos encontrar o tabuleiro vencedor com ncontas do tabuleiro vencedor n-1, procurando o copo vazio com o menor número, pegando um cordão da cesta e um de cada copo abaixo do copo vazio e colocando-os todos no copo vazio.

Dissecação

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

Porta da resposta Python do @ orlp. Explicação: Considere o número total de contas nos icopos th e superior. Cada jogada de um desses copos removerá as icontas desse total. (Por exemplo, se ifor 3, e você joga a partir do quinto copo, reduz em cinco o número de contas nesse copo, mas também adiciona um ao quarto e ao terceiro copos.) O total deve, portanto, ser múltiplo de i. Agora, o i-1copo não pode conter iou mais contas; portanto, para deixar um múltiplo i, deve conter o restante do módulo de contas i.

Explicação anterior (no link do @ xnor): A abordagem ingênua é a técnica de "reprodução reversa". Isso usa a observação de que fazer uma jogada esvazia uma xícara, então a reprodução inversa coleta uma conta de cada xícara e as coloca no primeiro copo vazio, assim (63 bytes):

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

Agora, considere os primeiros icopos. No caso de uma delas estar vazia, a reprodução reversa aumentará 1o número total de contas nessas xícaras, enquanto que nenhuma delas estiver vazia, a reprodução reversa subtrairá ido total, no entanto, isso equivale à adição de 1módulo i+1. Após as njogadas reversas, a soma das contas nos primeiros icopos será, portanto, equivalente ao nmódulo i+1, ou, dito de outra maneira, o número de contas no quarto icopo será equivalente a nmenos a soma das contas nos copos anteriores, módulo i+1. Agora, para que o icopo seja jogável, o número de contas não pode exceder i, então, na verdade, será igual ao número de contas restantes.i+1. (Observe que eu uso d=i+1, pois usa menos bytes.)

Ruby, 36 bytes

Um exemplo da resposta do @ orlp porque é genial demais para eu pensar em algo melhor.

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