Hintergrund

Im Spiel von Nim entfernen die Spieler abwechselnd "Steine" von "Stapeln": In jeder Runde muss ein Spieler zwischen einem und allen Steinen von einem einzelnen Stapel entfernen . Das Ziel von Nim ist es, den letzten Stein zu nehmen oder in der Misere-Variante Ihren Gegner dazu zu zwingen - es stellt sich jedoch heraus, dass die Strategien nahezu identisch sind.

Nim macht ein lustiges Barspiel. Sie können Streichhölzer oder Münzen für die "Steine" verwenden, und die "Stapel" sind normalerweise in einer Linie angeordnet. Unten sehen Sie ein klassisches Setup mit Stapeln von 1, 3, 5 und 7:

Wenn Sie noch nie zuvor Nim gespielt haben, können Sie es versuchen, bevor Sie diese Herausforderung versuchen. Hier ist eine Version namens "Pearls Before Swine" .

Strategie

Die optimale Strategie in Nim ist schwierig genug, dass die meisten Laien konsequent gegen einen Experten verlieren, aber mit binärer Arithmetik einfach zu beschreiben sind .

Das Ausführen von mentalen binären XOR-Operationen ist jedoch schwierig. Glücklicherweise gibt es eine gleichwertige Möglichkeit, die richtige Strategie zu visualisieren, die auch in betrunkenem Zustand in Echtzeit einfacher zu implementieren ist.

Es gibt nur drei Schritte:

1. Gruppieren Sie die "Steine" in jeder Zeile mental in Untergruppen, deren Größe Potenzen von 2 ist, beginnend mit der größtmöglichen Größe: 8, 4, 2 und 1 sind für die meisten Spiele ausreichend.
2. Versuchen Sie, jede Gruppe mit einem Zwilling in einer anderen Zeile abzugleichen, sodass jede Gruppe ein Paar hat.
3. Wenn dies nicht möglich ist, entfernen Sie ungepaarte "Steine" aus einer einzelnen Zeile (dies ist immer möglich - siehe Wikipedia-Link, warum), damit Schritt 2 möglich wird.

Oder anders gesagt: "Entfernen Sie einige Steine ​​von einem einzelnen Stapel, sodass alle Gruppen mit einer Gruppe in einem anderen Stapel gepaart werden können, wenn Sie die Stapel dann zu Zweiergruppen gruppieren." Mit der Einschränkung, dass Sie größere Zweierpotenzen nicht in kleinere aufteilen können - z. B. können Sie eine Linie mit 8 Steinen nicht in zwei 4er-Gruppen gruppieren.

So würden Sie beispielsweise das obige Board visualisieren:

Dieses Brett ist perfekt ausbalanciert, sodass Sie möchten, dass sich Ihr Gegner zuerst bewegt.

Die Herausforderung

Geben Sie bei einer Liste positiver Ganzzahlen, die die Größe der Nim- "Stapel" darstellen, eine Klartext-Visualisierung des Nim-Boards zurück, die von einem Experten gesehen wird.

Was eine gültige Visualisierung ausmacht, lässt sich am besten anhand eines Beispiels erklären. Sie müssen jedoch:

1. Weisen Sie jeder "Power-of-2-Untergruppe" und ihrem Paar ein eigenes Zeichen zu (ungepaarte Untergruppen sind nicht qualifiziert), und verwenden Sie dieses Zeichen, um die "Steine" sowohl in der Untergruppe als auch im Paar darzustellen.
2. Stellen Sie alle ungepaarten "Steine" (dh diejenigen, die ein Experte beim Spielen von normalem - nicht misere - Nim entfernen würde) mit einem Bindestrich dar : -.

Es gibt mehrere Möglichkeiten, eine gültige Visualisierung zu erzielen, und alle sind gültig. Lassen Sie uns einige Testfälle durcharbeiten:

Testfälle

Eingabe: 1, 3, 5, 7

Mögliche Ausgabe 1:

A
BBA
CCCCD
CCCCBBD

Sie können optional Leerzeichen zwischen den Zeichen sowie Leerzeilen zwischen den Zeilen einfügen:

Mögliche Ausgabe 2:

A

B B A

C C C C D

C C C C B B D

Eingabe: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Die Reihenfolge und Auswahl der Zeichen kann beliebig sein:

Mögliche Ausgabe 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

Unicode-Symbole sind auch in Ordnung:

Mögliche Ausgabe 2:

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

Eingabe: 7

Aus den Regeln folgt, dass jeder "einzelne Stapel" vollständig entfernt werden muss.

Mögliche Ausgabe 1:

-------

Mögliche Ausgabe 2:

- - - - - - -

Eingabe: 5, 5

Mögliche Ausgabe:

A A A A B
A A A A B

Zusätzliche Regeln

• Dies ist Code Golf mit Standardregeln. Der kürzeste Code gewinnt.
• Die Eingabe ist flexibel und kann in jeder für Sie geeigneten Listenform erfolgen.
• Die Ausgabe ist ebenfalls flexibel, wie die obigen Beispiele zeigen. Die meisten vernünftigen Abweichungen sind zulässig. Fragen Sie, ob Sie sich bei etwas nicht sicher sind.

Ruby, 169 164 148 Bytes

->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}}

Probieren Sie es online aus!

Zuerst initialisieren wir

• die Nim-Summe mit s=eval a*?^(die kürzer ist als a.reduce:^)
• Die Variable c, in der das erste nicht verwendete eindeutige Zeichen gespeichert ist
• Eine Karte m, die Zweierpotenzlängen auf Zeichen abbildet, mit denen sie dargestellt werden

Dann laufen wir über jeden Stapel und führen Folgendes aus:

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

Gemäß der Strategie von Wikipedia sollten wir Steine ​​von diesem Stapel entfernen , wenn der Nim-Sum-XOR-Stapel kleiner als der Stapel ist , sodass seine Länge zum Nim-Summen-XOR-Stapel wird . Durch Speichern der Differenz in der Variablen zkönnen wir testen, ob diese Differenz positiv ist, und wenn ja, 1.) so viele Striche drucken, 2.) vom Stapel subtrahieren und 3.) die Nim-Summenvariable auf setzen Null, um eine weitere Steinentfernung zu verhindern.

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

Wir „loop“ jetzt über jedes Bit und behalten ihre Werte durch wiederholtes Dividieren xdurch 2und Multiplizieren des Akkumulators ndurch 2. Die Schleife ist eigentlich eine Zeichenfolge, die xmal ausgewertet wird, was weitaus größer ist als die log2(x)Zeiten, die erforderlich sind, aber es wird kein Schaden angerichtet (abgesehen von Ineffizienz). Für jedes Bit führen wir Folgendes aus, wenn das Bit 1 ( x&1>0) ist:

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

Drucken Sie ein Zeichen nmal. Wenn wir bereits eine ungepaarte Gruppe dieser vielen Steine ​​gedruckt haben, verwenden Sie dieses Zeichen. Verwenden Sie andernfalls das nächste nicht verwendete Zeichen (das caufgrund von an Ort und Stelle voranschreitet !).

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

Wenn m[n]vorhanden (dh wir haben gerade ein Paar abgeschlossen), m[n]wird es zurückgesetzt. Ansonsten haben wir gerade ein neues Paar gestartet, also m[n]auf das Zeichen eingestellt , das wir verwendet haben (dies *1ist eine kurze Möglichkeit, eine Kopie davon zu erstellen c).

Python 2 , 150 196 206 Bytes

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

Probieren Sie es online aus!

JavaScript (ES6), 215 Byte

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>

Visualisiert nur bis zu 36 verschiedene Zeichen. Ich bin erleichtert, dass dies funktioniert 1, 3, 4, 5.

Sauber , 454 Bytes

immer noch Golf spielen

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)

Probieren Sie es online aus!

Definiert die Funktion $ :: [Int] -> String, nimmt die Stapelgrößen und gibt eine Zeichenfolge zurück -, in der zu entfernende Steine ​​angegeben sind, und Gruppen werden durch aufsteigende ASCII-Zeichen dargestellt -. Wenn genügend Gruppen benötigt werden, werden die Zeichen irgendwann wieder umbrochen, und aufgrund dessen foldrwird mehr als ein Gigabyte Speicher benötigt, um den zweiten Testfall auszuführen.

Eingedrückte Version des Riesenverständnisses:

$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
    ]
]