tło

W grze Nim gracze naprzemiennie usuwają „kamienie” z „stosów”: w każdej turze gracz musi usunąć jeden lub wszystkie kamienie z jednego stosu. Celem Nim jest zabranie ostatniego kamienia lub, w wariancie misere, zmusić przeciwnika do zrobienia tego - jednak okazuje się, że strategie są prawie identyczne.

Nim to fajna gra w bar. Możesz użyć zapałek lub monet do „kamieni”, a „stosy” są zazwyczaj ułożone w jednej linii. Poniżej znajduje się klasyczny układ z stosami 1, 3, 5 i 7:

Jeśli nigdy wcześniej nie grałeś w Nima, możesz spróbować swoich sił przed tym wyzwaniem. Oto wersja o nazwie „Perły przed świnią” .

Strategia

Optymalna strategia w Nim jest na tyle trudna, że ​​większość laików przegrywa konsekwentnie z ekspertem, ale jest łatwa do opisania za pomocą binarnej arytmetyki .

Wykonywanie mentalnych binarnych operacji XOR jest jednak trudne, więc na szczęście istnieje równoważny sposób wizualizacji prawidłowej strategii, który jest łatwiejszy do wdrożenia w czasie rzeczywistym, nawet gdy jest pijany.

Istnieją tylko trzy kroki:

1. Mentalnie pogrupuj „kamienie” w każdej linii w podgrupy, których rozmiary to potęgi 2, zaczynając od największego możliwego rozmiaru: 8, 4, 2 i 1 są wystarczające dla większości gier.
2. Spróbuj dopasować każdą grupę do bliźniaka w innej linii, aby każda grupa miała parę.
3. Jeśli nie jest to możliwe, usuń niesparowane „kamienie” z jednej linii (zawsze będzie to możliwe - zobacz link do Wikipedii, dlaczego), aby krok 2. stał się możliwy.

Lub, powiedział inny sposób: „Usuń niektóre kamienie z jednego stosu, tak że jeśli zgrupujesz stosy w potęgi 2, wszystkie grupy mogą zostać sparowane z grupą na innym stosie”. Z zastrzeżeniem, że nie możesz rozbić większych mocy 2 na mniejsze - np. Nie możesz pogrupować linii z 8 kamieniami w dwie grupy po 4.

Na przykład oto jak wizualizujesz tablicę powyżej:

Ta plansza jest idealnie wyważona, więc najpierw chcesz, aby przeciwnik się poruszył.

Wyzwanie

Biorąc pod uwagę listę dodatnich liczb całkowitych reprezentujących rozmiar „stosów” Nima, zwróć wizualizację zwykłego tekstu na tablicy Nim, widzianą przez eksperta.

To, co stanowi prawidłową wizualizację, najlepiej wyjaśnić na przykładzie, ale musisz:

1. Przypisz odrębny znak do każdej „podgrupy potęgi-2” i jej pary (niesparowane podgrupy nie kwalifikują się) i użyj tego znaku do przedstawienia „kamieni” zarówno podgrupy, jak i pary.
2. Reprezentują żadnych niesparowanych „kamienie” (czyli te, ekspert usunęłaby podczas odtwarzania normalny - nie misere - NIM) za pomocą łącznika: -.

Istnieje wiele sposobów na uzyskanie prawidłowej wizualizacji i wszystkie są ważne. Przeanalizujmy niektóre przypadki testowe:

Przypadki testowe

Wejście: 1, 3, 5, 7

Możliwe wyjście 1:

A
BBA
CCCCD
CCCCBBD

Opcjonalnie możesz dołączyć spacje między znakami, a także puste linie między wierszami:

Możliwe wyjście 2:

A

B B A

C C C C D

C C C C B B D

Wejście: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Kolejność i wybór postaci może być dowolna:

Możliwe wyjście 1:

G
E E
E E G
C C C C
C C C C F
B B B B D D
B B B B D D F
H H I - - - - -
A A A A A A A A I
A A A A A A A A H H

Symbole Unicode też są w porządku:

Możliwe wyjście 2:

◎
◈  ◈
◈  ◈  ◎
△  △  △  △
△  △  △  △  ◉
◐  ◐  ◐  ◐  ◀  ◀
◐  ◐  ◐  ◐  ◀  ◀  ◉
▽  ▽  ◒  -  -  -  -  -
▥  ▥  ▥  ▥  ▥  ▥  ▥  ▥  ◒ 
▥  ▥  ▥  ▥  ▥  ▥  ▥  ▥  ▽  ▽  

Wejście: 7

Z zasad wynika, że ​​każdy „pojedynczy stos” musi zostać całkowicie usunięty.

Możliwe wyjście 1:

-------

Możliwe wyjście 2:

- - - - - - -

Wejście: 5, 5

Możliwe wyjście:

A A A A B
A A A A B

Dodatkowe zasady

• To jest golf golfowy ze standardowymi zasadami. Najkrótszy kod wygrywa.
• Dane wejściowe są elastyczne i można je przyjmować w dowolnej dogodnej dla ciebie formie listy.
• Dane wyjściowe są również elastyczne, co ilustrują powyższe przykłady. Dopuszczalne będą najbardziej rozsądne zmiany. Zapytaj, czy czegoś nie wiesz.

Rubin, 169 164 148 bajtów

->a{s=eval a*?^
c=?@
m={}
a.map{|x|z=x-(x^s);[$><<?-*z,x-=z,s=0]if z>0
n=1
eval'x&1>0?[$><<(m[n]||c.next!)*n,m[n]=!m[n]&&c*1]:0;n*=2;x/=2;'*x
puts}}

Wypróbuj online!

Najpierw inicjujemy

• nim-sum z s=eval a*?^(który jest krótszy niż a.reduce:^)
• zmienna c, która przechowuje pierwszy nieużywany unikalny znak
• mapa, mktóra odwzorowuje potęgę dwóch długości na znaki używane do ich reprezentowania

Następnie, zapętlając każdy stos, uruchamiamy następujące czynności:

z=x-(x^s);[$><<?-*z,x-=z,s=0]if z>0

Zgodnie ze strategią Wikipedii , jeśli stos XOR nim-suma jest mniejszy niż stos , powinniśmy usunąć kamienie z tego stosu, aby jego długość stała się stosem XOR nim-suma . Przechowując różnicę w zmiennej z, możemy sprawdzić, czy ta różnica jest dodatnia, a jeśli tak 1.) wydrukuj tyle kresek, 2.) odejmij ją od stosu i 3.) ustaw zmienną nim-sum na zero, aby zapobiec dalszemu usuwaniu kamieni.

n=1
eval'[...];n*=2;x/=2;'*x

Teraz my „pętla” w ciągu każdego bitu i śledzić ich wartości poprzez wielokrotne dzielenie xprzez 2i mnożąc akumulator nprzez 2. Pętla jest tak naprawdę xczasem obliczonym przez ciąg znaków , który jest znacznie większy niż log2(x)czas, gdy jest to konieczne, ale nie wyrządza żadnej szkody (poza nieefektywnością). Dla każdego bitu uruchamiamy następujące polecenie, jeśli bit ma wartość 1 ( x&1>0):

$><<(m[n]||c.next!)*n

Wydrukuj nczasy postaci . Jeśli wydrukowaliśmy już niesparowaną grupę tak wielu kamieni, użyj tej postaci; w przeciwnym razie użyj następnej nieużywanej postaci (awans cna miejscu z powodu !).

m[n]=!m[n]&&c*1

Jeśli m[n]istniał (tzn. Właśnie ukończyliśmy parę), to m[n]jest resetowany. W przeciwnym razie właśnie zaczęliśmy nową parę, więc ustaw m[n]na znak, którego użyliśmy ( *1jest to krótki sposób na zrobienie kopii c).

Python 2 , 150 196 206 bajtów

def f(p):
 c=48;s=[l*'.'for l in p];m=2**len(bin(l))
 while m:
  if sum(m*'.'in l for l in s)>1:
   for i,l in enumerate(s):s[i]=l.replace('.'*m,chr(c)*m,`s`.count(chr(c)*m)<2)
   c+=1
  else:m/=2
 return s

Wypróbuj online!

JavaScript (ES6), 215 bajtów

f=
(a,c=0,x=eval(a.join`^`),i=a.findIndex(e=>(e^x)<e),b=a.map(_=>``),g=e=>(d=e&-e)&&a.map((e,i)=>e&d&&(a[i]-=d,b[i]=(c++>>1).toString(36).repeat(d)+b[i]))&&g(e-d))=>g(eval(a.join`|`),b[i]='-'.repeat(a[i]-(a[i]^=x)))||b

<textarea oninput=o.textContent=/\d/.test(this.value)?f(this.value.match(/\d+/g)).join`\n`:``></textarea><pre id=o>

Wizualizuje tylko do 36 różnych postaci. Ulżyło mi, że to działa 1, 3, 4, 5.

Czysty , 454 bajtów

wciąż gra w golfa

import StdEnv,Text,Data.List
$p=join"\n"[{#toChar c+'-'\\c<-e}\\e<-[take i(e++[0,0..])\\e<-r[[~c\\c<-reverse e,_<-[1..c]]\\e<-hd[q\\q<-foldr(\h t=[[a:b]\\a<-h,b<-t])[[]][[c\\c<-subsequences(takeWhile((>=)k)(iterate((*)2)1))|sum c<=k]\\k<-p]|sum[1\\a<-q&b<-p|sum a<>b]<2&&foldr(bitxor)0(flatten q)==0]]1&i<-p]]
r[]_=[]
r[h:t]n|all((<)0)h=[h:r t n]
#[m:_]=removeDup[e\\e<-h|e<0]
#(a,[x:b])=span(all((<>)m))t
=r([[if(e==m)n e\\e<-k]\\k<-[h:a]++[x]]++b)(n+1)

Wypróbuj online!

Definiuje funkcję $ :: [Int] -> String, przyjmując rozmiary stosu i zwracając ciąg znaków, w którym -oznaczane są kamienie do usunięcia, a grupy są reprezentowane przez znaki ASCII rosnące -. Jeśli potrzeba wystarczającej liczby grup, postacie ostatecznie się zawrócą, a to z powodufoldr tego wymaga więcej niż gigabajta pamięci do uruchomienia drugiego przypadku testowego.

Wcięta wersja gigantycznego zrozumienia:

$p=join"\n"[
    {#
        toChar c+'-'
        \\c<-j
    }
    \\j<-[
        take i(e++[0,0..])
        \\e<-r[
            [
                ~c
                \\c<-reverse e
                ,_<-[1..c]
            ]
            \\e<-hd[
                q
                \\q<-foldr(\h t=[
                    [a:b]
                    \\a<-h
                    ,b<-t
                ])[[]][
                    [
                        c
                        \\c<-subsequences(takeWhile((>=)k)(iterate((*)2)1))
                        |sum c<=k
                    ]
                    \\k<-p
                ]
                |sum[
                    1
                    \\a<-q
                    &b<-p
                    |sum a<>b
                ]<2&&foldr(bitxor)0(flatten q)==0
            ]
        ]1
        &i<-p
    ]
]