Finden Sie den optimalen Nim-Move

8

Das Spiel

Nim ist ein mathematisches Strategiespiel, bei dem 2 Spieler abwechselnd Gegenstände von verschiedenen Haufen nehmen. Wenn Sie an der Reihe sind, müssen Sie mindestens einen Gegenstand nehmen, und Sie können so viele nehmen, wie Sie möchten, vorausgesetzt, Sie nehmen nur einen Haufen. Der Spieler, der den letzten Gegenstand nimmt, gewinnt! Dies ist ein gelöstes Spiel. Bevor ich auf die Strategie eingehe, können Sie sie hier online spielen .

Die Strategie

Die Gewinnstrategie wird hier unter diesem Link sehr klar und einfach erklärt . Ich werde es mit etwas mehr technischen Begriffen erklären. Der Weg, um dieses Spiel zu gewinnen, besteht darin, immer so viele Gegenstände wie möglich zu nehmen, so dass die binär-digitale Summe immer 0 ist. Betrachten Sie das folgende Brett:

         *
       * *
     * * *
   * * * *
 * * * * *
 1 2 3 4 5

Um die binär-digitale Summe dieser Karte zu finden, müssen Sie:

  1. Konvertieren Sie die Zahl in jeder Zeile in eine Binärzahl. Wir haben also 001, 010, 011, 100 und 101.

  2. Addiere alle Zahlen und ignoriere jegliches Tragen.

     001
 010
 011
 100
+101
----
 001

    Sie können auch jede Zahl bitweise x-xieren, wodurch das gleiche Ergebnis erzielt wird.

Wenn die Summe in dieser aktuellen Konfiguration 001 ist, ist dies (noch) kein Gewinnbrett. Aber Sie können es zu einem Gewinnbrett machen! Wenn wir einen Gegenstand aus den Spalten 1, 3 oder 5 entfernen, ist die Summe 0. Dies ist ein Gewinnbrett, was bedeutet, dass der nächste Spieler, der sich bewegt, verliert, sofern Sie keinen Fehler machen. Sie müssen Ihren Zug also immer mit einem Gewinnbrett beenden. Nehmen wir an, Sie nehmen einen Gegenstand aus Spalte 5. Jetzt sieht die Tafel so aus:

       * *
     * * *
   * * * *
 * * * * *
 1 2 3 4 5

Solange Sie es nicht vermasseln, haben Sie einen garantierten Gewinn. Es gibt nichts, was dein Gegner tun kann, um dich aufzuhalten. Nehmen wir an, er nimmt alle Gegenstände aus Spalte 5.

       *
     * *
   * * *
 * * * *
 1 2 3 4 5

Wohin würdest du als nächstes gehen? Scrollen Sie noch nicht nach unten und versuchen Sie es selbst herauszufinden.

Im Moment ist die Summe 100. Der beste Zug (und der einzige Gewinnzug) wäre, alles aus Spalte 4 zu nehmen. Das würde das Brett so verlassen:

     * 
   * * 
 * * * 
 1 2 3 4 5

und die Summe so

 001
 010
+011
----
 000

das bedeutet, dass Sie in einem Gewinnbrett sind! Yay!

Die Herausforderung

Sie müssen ein Programm oder eine Funktion schreiben, die bei einem Nim-Board einen Gewinnzug oder einen False- Wert zurückgibt , wenn es keinen Gewinnzug gibt.

Deine Eingabe:

  • Wird das native Listenformat Ihrer Sprache sein, wobei jedes Element in der Liste der Anzahl der Elemente in einer bestimmten Spalte entspricht. Beispielsweise entspricht die Eingabe {4, 2, 1, 0, 3} der folgenden NIM-Karte:

    *
*           *
*  *        *
*  *  *     *
1, 2, 3, 4, 5

  • (optional) Die Anzahl der Zeilen. (Für Sprachen wie C / C ++, bei denen dies aus der Liste selbst nicht bekannt ist.)

Ihre Ausgabe:

  • Kann zu STDOUT gehen oder von der Funktion zurückgegeben werden

  • Muss aus zwei Zahlen bestehen: 1) der Spalte, aus der wir entfernen (denken Sie daran, dass die Spalten 0-indiziert sind) und 2) der Anzahl der Elemente, die aus dieser Zeile entfernt werden sollen. Dies kann ein Array mit zwei Elementen, eine Zeichenfolge aus zwei Zahlen usw. sein. Beachten Sie, dass die Antwort möglicherweise länger als zwei Ziffern ist. Die Rückgabe der Zeichenfolge "111" ist daher nicht gültig, da nicht klar ist, ob dies der Fall ist bedeutet "Ein Element aus Spalte 11 entfernen" oder "Elf Elemente aus Spalte 1 entfernen". "1,11" oder "11,1" wären beide akzeptabel.

  • Wenn keine Antwort erfolgt, geben Sie einen falschen Wert zurück oder drucken Sie ihn aus. Wenn Ihre Sprache nur einen Variablentyp zurückgeben kann (wieder wie C / C ++), wäre eine negative Zahl für die Spalte oder 0 oder weniger für die zu entfernende Zahl akzeptable False-Werte.

  • Wenn die zu entfernende Spaltennummer oder Nummer zu groß ist, wird dies als ungültige Ausgabe angesehen.

Beispiel Ein- / Ausgänge

[1, 2, 3, 4, 5]---> [0, 1]oder [4, 1]oder[2, 1]

[1, 3, 5, 6]---> [0, 1]oder [1, 1]oder[2, 1]

[1, 2, 0, 0, 5] ---> [4, 2]

[1, 2, 3] ---> ERROR

Wenn Sie eine Funktion anstelle eines vollständigen Programms ausführen möchten, müssen Sie ein vollständiges Programm schreiben, um die Funktion in Aktion zu demonstrieren. Dies wird nicht für Ihre volle Punktzahl angerechnet. Außerdem wird erwartet, dass Programme in angemessener Zeit ausgeführt werden. Ich habe nicht vor, übermäßig große Eingaben einzugeben. Solange Ihr Programm keine Brute-Force-Suche über den gesamten Spielbaum durchführt, sollte es Ihnen gut gehen.

Wie üblich ist dies Code-Golf, daher gelten Standard-Lücken und Antworten werden in Bytes gezählt .

Bestenliste

Hier ist ein Stack-Snippet, mit dem Sie sowohl eine reguläre Rangliste als auch eine Übersicht der Gewinner nach Sprache erstellen können.

Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift unter Verwendung der folgenden Markdown-Vorlage:

# Language Name, N bytes

Wo Nist die Größe Ihrer Einreichung? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Code-Snippet anzeigen

code-golf game James
quelle
Können wir annehmen, dass die Eingabeliste mindestens eine positive Zahl enthält?
Jakube
@ Jakube ja, das kannst du.
James
Verwandte -ish?
FryAmTheEggman

Antworten:

3

Pyth, 33 22 21 20 19 Bytes

eS.e*<JxxFQbb,k-bJQ

Sie können es hier im Online-Compiler ausprobieren.

Vielen Dank an Jakube für das Entfernen von 12 Bytes und Maltysen für das Entfernen eines zusätzlichen Bytes!

Dies druckt einen Gewinnzug von der aktuellen Position. Wenn es keine Gewinnzüge gibt, wird nichts gedruckt.

Ich habe den Algorithmus auf Wikipedia verwendet . Hier ist die Aufschlüsselung:

  .e              Q    While enumerating every element in the input:
      J                    Assign variable J to:
        xFQ                 Every element of the input bitwise xor'ed together,
       x   b                bitwise xor'ed with the current element of the input
             ,             Create a tuple containing:
              k             The index of the current element, and
               -bJ          the difference between the current element and J
    *<J     b              Put that tuple into a list if J < b, otherwise put an empty tuple
 S                     Sort the list
e                      Print the last element of the list
Mike Bufardeci
quelle
3

Pyth, 23 Bytes

eSs.em*,kd!xxxFQb-bdSbQ

Probieren Sie es online aus: Demonstration

Dies durchläuft alle möglichen Bewegungen und führt sogar eine Sortierung durch. Daher hat es eine Zeitkomplexität von O(N*log(N))und eine Speicherkomplexität von O(N), wobei Ndie Summe der Eingabeliste oder die Anzahl von Elementen ist.

Aufgrund der schlechten Zeitkomplexität ist dies möglicherweise keine gültige Antwort. Obwohl es alle Spiele löst, können Sie sofort im realen Leben mit realen Objekten spielen.

Erläuterung:

                          implicit: Q = input list
   .e                 Q   map each (index k, item b) of Q to:
     m              Sb      map each d of [1, 2, ..., b] to:
       ,kd                      the pair (k, d)
      *                       multiplied by
             xFQ                xor of all numbers in Q
            x   b               xor with b
           x     -bd            xor with b-d
          !                     not (1 if xor==0 else 0)

So the input [1, 2, 0, 0, 5] gives [[[]], [[], []], [], [], [[], [4, 2], [], [], []]]

  s                       add all lists to one big list
 S                        sort

Now it looks like this: [[], [], [], [], [], [], [], [4, 2]]

e                         pick the last element and print
Jakube
quelle
3

CJam, 21 20 Bytes

Im Vergleich zur Originalversion wurde ein Byte gespeichert, und die Fehlerbehandlung funktioniert jetzt auch:

l~__:^f^.-_:g1#_@=S\

Probieren Sie es online aus

Die Eingabe ist ein CJam-Array, z.

[1 2 3 4 5]

Wenn keine Lösung gefunden wird, wird gedruckt -1 0, was meinem Verständnis der Ausgabeanforderungen entspricht.

Erläuterung:

l~      Get input.
__      Make two copies for following operations.
:^      Reduce with xor operator, producing xor of all columns.
f^      xor all input values with the result. For each column, this calculates
        the value that the column would have to change to make the overall
        xor zero. Consider this the "target values".
.-      Subtract the target values from the input values.
_:g     Per element signum of difference between target value and input value.
1#      Find index with value 1, which is the first positive value.
_@=     Get the value at the index.
S\      Put a space between index and value.
Reto Koradi
quelle
1

Ruby, 95

->(a){r=[false,c=0]
a.each{|e|c^=e}
a.each_index{|i|(n=a[i]-(c^a[i]))>0&&n>r[1]?(r=[i,n]):0}
r}

Ich habe 2 separate anonyme Funktionen geschrieben. Die erste, die fim folgenden Programm zugewiesen ist , druckt alle Lösungen, und die zweite g(entsprechend der obigen Bewertung, da sie kürzer ist und der Spezifikation besser entspricht) gibt nur die Lösung zurück, bei der die größte Anzahl entfernt werden muss.

In beiden Fällen wird die Ziffernsumme in summiert c. Dann wird das Array durchlaufen und der Ausdruck n=a[i]-(c^a[i])wird verwendet, um die Anzahl der zu entfernenden Zähler zu berechnen (dies kann natürlich nur durchgeführt werden, wenn es Null überschreitet).

in fwerden alle möglichen Lösungen gedruckt (wenn cfestgestellt wird 0, errorwird gedruckt , ohne Looping.) war ich überrascht zu sehen , dass die verschiedenen Pfähle können ganz unterschiedliche Anzahl von Zählern erforderlich entfernt werden.

im gAusgabearray rwird nur aktualisiert, wenn die Anzahl der zu entfernenden Zähler die vorherige Anzahl überschreitet. Das Array r = [pile index, number to be removed]wird zurückgegeben. Wenn es keine Lösung gibt, ist die Anzahl der zu entfernenden Zähler immer Null, rbleibt unverändert und der Anfangswert von r = [false,0]wird zurückgegeben.

Geringe Einsparungen sind möglich, wenn falsesie beispielsweise geändert werden können "!"und wenn eine gültige Lösung anstelle der größten zurückgegeben werden kann (durch Löschen &&n>r[1]).

Im Testprogramm formatiert

f=->(a){
  c=0
  a.each{|e|c^=e}
  c<1?(p "error"):(a.each_index{
     |i|(n=a[i]-(c^a[i]))>0?(p"#{i},#{n}"):0
   })
}

g=->(a){
  r=[false,c=0]
  a.each{|e|c^=e}
  a.each_index{
     |i|(n=a[i]-(c^a[i]))>0&&n>r[1]?(r=[i,n]):0
  }
  r
}

#Change the following two lines according to the number of values youj want to use for testing.
t=[rand(15),rand(15),rand(15),rand(15)] #Generate some random numbers for testing.
t=[gets.to_i,gets.to_i,gets.to_i]       #User input. Delete this line if you want to test with random numbers.
print t,"\n"

f.call(t)
puts g.call(t)
Level River St.
quelle
Eigentlich, weil r[1]immer mindestens Null ist, denke ich, >0&&n>r[1]kann auf>r[1]
Level River St
0

Mathematica, 73 Bytes

{f=BitXor;p=Position[#,x_/;BitAnd[x,a=f@@#]==a][[1,1]],(n=#[[p]])-n~f~a}&
user202729
quelle
1
Was. Mathematica hat dafür kein eingebautes?
Draco18s vertraut SE nicht mehr
0

JavaScript (ES6), 54 Byte

Gibt entweder das Paar [column, number]oder false zurück

a=>a.some((n,i)=>r=(n-=n^eval(a.join`^`))>0&&[i,n])&&r

Probieren Sie es online aus!

Kommentiert

a =>                        // a[] = input array
  a.some((n, i) =>          // for each value n at position i in a[]:
    r = (                   //   save the result of the iteration in r
      n -=                  //   subtract from n:
        n ^ eval(a.join`^`) //     n XOR (all values in a[] XOR'ed together)
    ) > 0                   //   if the above value is positive:
    && [i, n]               //     yield the solution [i, n] and exit the some() loop
                            //   (otherwise: yield false and go on with the next value)
  ) && r                    // end of some(); return r
Arnauld
quelle