Optimale Strategie für ein abstraktes Spiel

Ich habe in einem Interview das folgende Problem erhalten (das ich bereits nicht gelöst habe und nicht versucht habe, mich vorbeizuschleichen): Das Spiel beginnt mit einer positiven Ganzzahl . (ZB A 0 = 1234. ) Diese Zahl wird in eine binäre Darstellung umgewandelt, und N ist die Anzahl der auf 1 gesetzten Bits . (ZB A 0 = b 100 1101 0010 , N = 5 )$A_0$$A_0 = 1234$$N$$1$$A_0 = b100\ 1101\ 0010$$N = 5.$

Spieler 1 wählt eine Nummer kleiner als A 0 ist . Für B 0 darf nur ein Bit auf 1 gesetzt sein. (Beispiel: B 0 = b 10 0000 0000 = 512. ) Sei A 1 = A 0 - B 0 . (ZB A 1 = 1234 - 512 = 722 = b 10 1101 0010. ) Ein Zug ist gültig, wenn B $B_0$$A_0$$B_0$$B_0 = b10\ 0000\ 0000 = 512$$A_1 = A_0 - B_0$$A_1 = 1234-512 = 722 = b10 1101 0010$$B_0$erfüllt die vorherigen Bedingungen, und wenn die Anzahl der in gesetzten Bits immer noch gleich N ist .$A_1$

Spieler 2 fährt von indem er ein gültiges B 1 wählt , dann fährt Spieler 1 von A 2 fort und so weiter. Ein Spieler verliert, wenn er keine gültigen Züge mehr hat.$A_1$$B_1$$A_2$

Unter der Annahme, dass beide Spieler optimal spielen, bestimmen Sie den Gewinner mit einer einigermaßen effizienten Methode. (In meiner Problemdefinition bestand die Einschränkung darin, dass das Programm eine Lösung für einige Millionen eingegebene Zahlen liefern muss, die in eine vorzeichenbehaftete 32-Bit-Ganzzahl passen.) Das heißt, die Lösung muss nicht vorhanden sein voll analytisch.

Mein persönliches Interesse ist es, herauszufinden, ob die Erwartung, in den 120 Minuten, die ich erhalten habe, die richtige Lösung gefunden und umgesetzt zu haben, ohne dass eine Rückmeldung zur Richtigkeit möglich war, vernünftig war. oder ob dies eine der Fragen war, bei denen "Mal sehen, ob sie dieses Rätsel schon einmal gesehen haben".

Ich war gescheitert, weil ich mich für die Implementierung einer vernünftigen Strategie entschieden hatte, die mir korrekte Ergebnisse für die wenigen Testfälle lieferte, die ich im Vorfeld erhalten hatte, zu viel Zeit verschwendete, um dies schnell laufen zu lassen, und schließlich falsche Ergebnisse einreichte volle Ausgabe als meine Zeit abgelaufen ist.

Im Nachhinein hätte ich eine Brute-Force-Suche durchführen und Teillösungen für kleine Startnummern auswendig lernen sollen, aber im Nachhinein ist das immer 20/20. Ich bin jedoch gespannt, ob es einen anderen gemeinsamen Ansatz gibt, der mir als Betrügerin entgangen ist.

$01$$10$$01$

$10 \rightarrow 01$

Der einzige entscheidende Faktor in einem Spiel ist also, wie viele Swaps erforderlich sind, um zu dem Zustand zu gelangen, in dem sich alle auf der rechten Seite befinden, und es gibt keine Gewinn- oder Verluststrategie. Die Parität der Anzahl der erforderlichen Swaps ist der einzige bestimmende Faktor.

$1$

$i$$1$$1$$0$$1$$k$$k - i$

i = 0
k = 0
total = 0
while n > 0:
    if n & 1:
       total += k - i
       i += 1
    n >>= 1
    k += 1

total$O(\log n)$

Ein Weg, um ein solches Problem zu lösen, ist wie folgt:

• Finden Sie die Lösung für ein paar einfache Werte mit dem von Ihnen vorgeschlagenen "Memoized Brute Force" -Ansatz.

• Errate die Antwort (welche Positionen gewinnen und welche verlieren).

• Versuchen Sie, Ihre Antwort zu beweisen. Wenn Sie erfolgreich sind, großartig. Versuchen Sie andernfalls, ein Gegenbeispiel zu finden, und verwenden Sie es, um eine andere Antwort zu erraten. Hier könnte es hilfreich sein, noch ein paar Fälle zu lösen.

Es ist wirklich schwer zu sagen, wie viel Zeit das kostet. In Interviews wird jedoch nicht unbedingt erwartet, dass Sie die Lösung finden. Vielmehr wollen die Interviewer wissen , wie Sie näherten Lösung des Problems, und welche Fortschritte Sie es geschafft zu machen.

Beachten Sie aus der Antwort von @ orlp, dass wir die Parität der Summe der Verschiebungen von der Startposition zur Endposition wollen. Lassen Sie uns dies kommentieren:

       9876543210
       9 76 4  1    (positions at start)
start: 1011010010
end:   0000011111
            43210   (positions at end)

Also wollen wir

  ((1 - 0) + (4 - 1) + (6 - 2) + (7 - 3) + (9 - 4)) & 1
= ((1 + 4 + 6 + 7 + 9) - (0 + 1 + 2 + 3 + 4)) & 1
= ((1 + 0 + 0 + 1 + 1) - (0 + 1 + 0 + 1 + 0)) & 1

Der erste Teil ist nur die Parität der Anzahl von Bits in den ungeraden Positionen. Sie können dies maskieren, indem Sie die maximale Ganzzahl ohne Vorzeichen verwenden, durch 0b11 dividieren und negieren.

= (bitcount(x & ~(UINT_MAX / 0b11)) ^ (0 + 1 + 0 + 1 + 0)) & 1

Der zweite Teil ist die Parität der halben Anzahl von Bits in x.

= (bitcount(x & ~(UINT_MAX / 0b11)) ^ (bitcount(x) >> 1)) & 1

bitcountkann entweder den Hardwarebefehl verwenden popcntoder manuell implementiert werden, indem nur das letzte oder vorletzte Bit benötigt wird, mit schnellen Reduzierungen wie diesen .