Mancala ist der Name einer Familie von Brettspielen, bei denen es sich normalerweise um eine Reihe von Tassen handelt, die mit Perlen gefüllt sind, die die Spieler manipulieren. Diese Herausforderung verwendet einen bestimmten Regelsatz für eine Solitaire-Variante des Spiels.

Das Brett besteht aus einem "Korb" an einem Ende, gefolgt von einer unendlichen Anzahl von Bechern, die ab 1 nummeriert sind. Einige der Becher enthalten eine bestimmte Anzahl von Perlen. Wenn die ndritte Tasse genau nPerlen enthält, können Sie die Perlen daraus "säen". Säen bedeutet, alle nPerlen aus der Tasse zu nehmen und sie dann einzeln in jeder Tasse in Richtung Korb abzulegen. Die letzte Perle wird in den Korb gelegt. Der Spieler gewinnt, wenn sich alle Perlen auf dem Brett im Korb befinden.

Natürlich gibt es viele Bretter, die nicht gewinnbar sind, zum Beispiel, wenn genau eine Perle in der zweiten Tasse ist. Es gibt keine legalen Spiele, da nicht alle Tassen mit 0 Perlen gesät werden können und die zweite Tasse nicht genügend Perlen zum Säen hat. Dies macht offensichtlich keinen Spaß, daher besteht Ihre Aufgabe darin, gewinnbare Boards zu erstellen.

Aufgabe

Bei einer positiven Ganzzahl, die eine Anzahl von Perlen darstellt, wird eine Liste von nicht negativen Ganzzahlen ausgegeben, die die Anzahl der Perlen darstellen, die in jede Tasse gegeben werden sollten, um ein gewinnbares Brett wie oben beschrieben herzustellen. Diese Liste sollte keine nachgestellten Nullen enthalten.

Für eine bestimmte Anzahl von Perlen gibt es immer genau eine gewinnbare Board-Konfiguration.

Demonstration

Dies ist eine Demonstration, wie man das gewinnbare Brett für und die Eingabe von 4 spielt. Das gewinnbare Brett ist [0, 1, 3]. Wir beginnen mit dem einzigen verfügbaren Zug und säen die Perlen aus der dritten Tasse, um sie zu erhalten [1, 2, 0]. Jetzt haben wir tatsächlich eine Wahl, aber die einzig richtige ist, die erste Tasse zu säen und zu bekommen : [0, 2, 0]. Dann säen wir die zweite Tasse nachgiebig [1, 0, 0]und schließlich säen wir die erste Tasse erneut, um alle leeren Tassen zu erhalten.

Testfälle:

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]

Vielen Dank an PeterTaylor für die Entwicklung eines Programms zur Erstellung von Testfällen!

CJam (21 Bytes)

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

Online-Demo

Erläuterung

Ich habe unabhängig die in diesem Artikel erwähnte "Unplaying" -Technik abgeleitet . Wir beweisen durch Induktion, dass es für eine bestimmte Anzahl von Perlen genau ein Gewinnbrett gibt.

Basisfall: Mit 0 Perlen ist das einzige Gewinnbrett das leere.

Induktiver Schritt: Wenn wir aus der Tasse säen, ist die Tasse kbeim nächsten Zug kleer und jede Tasse, die sich näher am Korb befindet, enthält mindestens eine Perle. Daher können wir das einzigartige Gewinnbrett mit nPerlen aus dem Gewinnbrett mit n-1Perlen finden, indem wir nach der leeren Tasse mit der niedrigsten Nummer suchen, eine Perle aus dem Korb und eine aus jeder Tasse unter dieser leeren Tasse nehmen und alle in die leere Tasse legen.

Präparation

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 Byte

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

Port der Python-Antwort von @ orlp. Erläuterung: Berücksichtigen Sie die Gesamtzahl der Perlen in der ith und höheren Tasse. Bei jedem Spiel aus einer dieser Tassen werden iPerlen aus dieser Summe entfernt. (Wenn zum Beispiel i3 ist und Sie ab der fünften Tasse spielen, reduzieren Sie die Anzahl der Perlen in dieser Tasse um fünf, aber Sie addieren auch eine zur vierten und dritten Tasse.) Die Summe muss daher ein Vielfaches sein von i. Jetzt kann die i-1dritte Tasse nicht imehr Perlen enthalten. Damit ein Vielfaches idavon übrig bleibt, muss der Rest der Perlen modulo enthalten sein i.

Vorherige Erklärung (aus dem Link von @ xnor): Der naive Ansatz ist die "Reverse Playing" -Technik. Dies verwendet die Beobachtung, dass ein Spiel eine Tasse leert, so dass beim umgekehrten Spielen eine Perle aus jeder Tasse gesammelt und wie folgt in die erste leere Tasse gelegt wird (63 Byte):

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

Betrachten Sie jetzt nur die ersten iTassen. In dem Fall, dass einer von ihnen leer ist, erhöht das umgekehrte Spielen 1die Gesamtzahl der Perlen in diesen Bechern, während in dem Fall, dass keine von ihnen leer ist, das umgekehrte Spielen ivon der Gesamtzahl abgezogen wird. Dies entspricht jedoch dem Hinzufügen von 1Modulo i+1. Nach numgekehrten Spielen entspricht die Summe der Perlen in den ersten iBechern daher nModulo i+1, oder anders ausgedrückt, die Anzahl der Perlen in der idritten Tasse entspricht nminus der Summe der Perlen in den vorhergehenden Bechern, Modulo i+1. Damit die idritte Tasse spielbar ist, kann die Anzahl der Perlen nicht überschritten werden i, sodass sie tatsächlich der Anzahl der verbleibenden Modulo-Perlen entsprichti+1. (Beachten Sie, dass ich d=i+1weniger Bytes verwende.)

Ruby, 36 Bytes

Eine Portierung der Antwort von @ orlp, weil es viel zu genial ist, als dass ich mir etwas Besseres vorstellen könnte.

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