Mancala to nazwa rodziny gier planszowych, które zwykle obejmują serię kubków wypełnionych koralikami, którymi manipulują gracze. W tym wyzwaniu zostanie zastosowany określony zestaw reguł dla wariantu pasjansa.

Plansza składa się z „kosza” na jednym końcu, po którym znajduje się nieskończona liczba filiżanek, ponumerowanych od 1. Niektóre kubki będą miały w sobie pewną liczbę koralików. Jeśli npuchar zawiera dokładnie nkoraliki, możesz „wysiać” z nich koraliki. Siew oznacza nwyjęcie wszystkich koralików z kubka, a następnie umieszczenie ich pojedynczo w każdej filiżance w kierunku kosza. Ostatni koralik trafi do koszyka. Gracz wygrywa, gdy wszystkie kulki na planszy są w koszu.

Oczywiście istnieje wiele desek, których nie można wygrać, na przykład jeśli w drugim pucharze znajduje się dokładnie jeden koralik. Nie ma legalnej gry, ponieważ nie można zasiać wszystkich filiżanek z 0 koralikami, a drugi puchar nie ma wystarczającej ilości koralików do wysiewu. To oczywiście nie jest fajne, więc Twoim zadaniem będzie stworzenie zwycięskich plansz.

Zadanie

Biorąc pod uwagę dodatnią liczbę całkowitą reprezentującą liczbę wyjściowych kulek, lista nieujemnych liczb całkowitych reprezentujących liczbę kulek, które należy umieścić w każdej filiżance, aby uzyskać zwycięską planszę, jak opisano powyżej. Ta lista nie powinna zawierać żadnych zer końcowych.

Dla dowolnej liczby paciorków zawsze istnieje dokładnie jedna konfigurowalna plansza do wygrania.

Demonstracja

Jest to demonstracja sposobu gry na planszy do wygrania i wkład 4. Planszą do wygrania jest [0, 1, 3]. Zaczynamy od jedynego dostępnego ruchu, wysiewając koraliki z trzeciego kubka, aby je zdobyć [1, 2, 0]. Teraz rzeczywiście mają wyboru, ale tylko jeden jest prawidłowy siewu pierwszego kielicha, uzyskanie: [0, 2, 0]. Następnie zasiewamy drugi kubek, poddając się, [1, 0, 0]i wreszcie siemy pierwszy kubek, aby uzyskać wszystkie puste kubki.

Przypadki testowe:

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]

Ogromne podziękowania dla PeterTaylor za opracowanie programu do generowania przypadków testowych!

CJam (21 bajtów)

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

Demo online

Wyjaśnienie

Niezależnie wyprowadziłem technikę „nieodgrywania” wspomnianą w tym artykule . Udowadniamy przez indukcję, że dla danej liczby kulek jest dokładnie jedna zwycięska plansza.

Podstawa: przy 0 koralikach jedyną zwycięską planszą jest pusta.

Indukcyjny krok: jeśli siejemy z kubka, kto przy następnym ruchu kubek kbędzie pusty, a każda filiżanka bliżej koszyk będzie zawierała co najmniej jedną kulkę. Dlatego możemy znaleźć unikalną zwycięską planszę z nkoralikami z zwycięskiej planszy z n-1koralikami, szukając pustego kubka o najniższym numerze, biorąc jeden koralik z kosza i jeden z każdego kubka poniżej tego pustego kubka i umieszczając je wszystkie w pustym kubku.

Sekcja

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 bajtów

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

JavaScript (ES6), 63 37 bajtów

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

Port odpowiedzi Python na @ orlp. Objaśnienie: Rozważ całkowitą liczbę perełek w ifiliżankach th i wyższych. Każda gra z jednej z tych filiżanek usunie ikoraliki z tej sumy. (Na przykład, jeśli ijest to 3, i grasz z piątego pucharu, zmniejszasz liczbę perełek w tym pucharze o pięć, ale dodajesz także jeden do czwartego i trzeciego pucharu.) Dlatego suma musi być wielokrotnością z i. Teraz i-1puchar nie może zawierać iani więcej koralików, więc aby mógł opuścić ich wielokrotność i, musi zawierać resztę koralików modulo i.

Poprzednie wyjaśnienie (z linku @ xnor): Naiwnym podejściem jest technika „odwrotnego grania”. Wykorzystuje się w tym obserwację, że wykonanie gry opróżnia kubek, więc odtwarzanie odwrotne zbiera koralik z każdego kubka i umieszcza je w pierwszym pustym kubku, tak jak to (63 bajty):

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

Teraz rozważ pierwsze ikubki. W przypadku, gdy jeden z nich jest pusty, odtwarzanie wsteczne zwiększy 1całkowitą liczbę perełek w tych pucharach, natomiast w przypadku, gdy żaden z nich nie będzie pusty, odtwarzanie wsteczne odejmie iod całości, jednak jest to równoważne z dodaniem 1modulo i+1. Po nodtworzeniu wstecznym suma perełek w pierwszych ipucharach będzie zatem równa nmodulo i+1, lub inaczej mówiąc, liczba perełek w ith kubku będzie równa nminus suma perełek w poprzednich pucharach, modulo i+1. Teraz, aby ipuchar mógł być odtwarzany, liczba koralików nie może przekroczyć i, więc w rzeczywistości będzie równa liczbie pozostałych koralików moduloi+1. (Zauważ, że używam, d=i+1ponieważ używa mniej bajtów.)

Rubinowy, 36 bajtów

Port odpowiedzi @ orlp, ponieważ jest to zbyt geniusz, aby wymyślić coś lepszego.

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