Algorithmus zu finden, Straßen und dieselbe Art in einer Hand

Question

Dies ist eigentlich eine Mahjong-basierte Frage, sondern eine Romme- oder sogar Poker-basierter Hintergrund genügt auch leicht zu verstehen.

In Mahjong 14 Kacheln (tiles sind wie Karten in Poker) mit 4 Sätzen angeordnet, und ein Paar. Eine Straße ( „123“) verwendet immer genau 3 Fliesen, nicht mehr und nicht weniger. Eine Reihe von der gleichen Art ( „111“) besteht aus genau 3 Fliesen, zu. Dies führt zu einer Summe von 3 * 4 + 2 = 14 Fliese.

Es gibt verschiedene Ausnahmen wie Kan oder Dreizehn Orphans, die hier nicht relevant sind. Farben und Wertebereiche (1-9) sind auch nicht wichtig für den Algorithmus.

Ich versuche, wenn eine Hand zu bestimmen, kann in der oben beschriebenen Art und Weise angeordnet werden. Aus bestimmten Gründen soll es nicht nur in der Lage sein, mit 14 zu behandeln, sondern einem beliebigen Anzahl von Fliesen. (Der nächste Schritt wäre, zu erfahren, wie viele Fliesen müssen ausgetauscht werden, um eine Hand zu vervollständigen.)

Beispiele:

11122233344455 -. Leicht genug, 4 Sätze und ein Paar
12345555678999 - 123, 456, 789, 555, 99
11223378888999 - 123, 123, 789, 888, 99
11223344556789 - keine gültige Hand

Meine aktuelle und noch nicht implementiert Idee: Für jede Kachel, versuchen Sie ein machen) eine Straße b) ein Satz c) ein Paar. Falls keine Werke (oder es wären> 1 Paar), zu der vorherige Iteration zurückgehen und versuchen, die nächste Option, oder, falls dies die höchste Stufe ist, scheitern. Else, entfernen Sie die gebrauchten Fliesen aus der Liste der restlichen Fliesen und fahren Sie mit der nächsten Iteration.

Ich glaube, dass dieser Ansatz funktioniert und wäre auch recht schnell sein (Leistung ist ein „netter Bonus“), aber ich bin Ihrer Meinung zu diesem Thema interessiert. Können Sie von alternativen Lösungen denken? Ist dies oder etwas ähnliches bereits vorhanden sein?

(nicht Hausaufgaben, ich lerne Mahjong zu spielen. )

Answer 1

Die Summe der Werte in einer Straße und in einem Satz kann durch 3 geteilt werden:

• n + n + n = 3 n
• (n-1) + n + (n + 1) = 3N

Also, wenn Sie addieren sie alle Zahlen in einem gelösten Hand, würden Sie eine Zahl der Form 3N + 2 M, wo M der Wert der Platte in dem Paar ist. Der Rest der Division durch drei (total % 3) ist, für jeden Wert von M:

total % 3 = 0  -> M = {3,6,9}
total % 3 = 1  -> M = {2,5,8}
total % 3 = 2  -> M = {1,4,7}

Also, statt von neun möglichen Paare zu Test mit, Sie haben nur drei versuchen, basierend auf einer einfachen Addition. Für jedes mögliche Paar, entfernen Sie zwei Fliesen mit diesem Wert und fahren Sie mit dem nächsten Schritt des Algorithmus, um zu bestimmen, ob es möglich ist.

Wenn Sie diese haben, mit dem niedrigsten Wert beginnen. Wenn es weniger als drei Kacheln mit diesem Wert, bedeutet dies, sie sind unbedingt das erste Element einer Straße, so dass die Straße entfernen (wenn Sie nicht können, weil Fliesen n + 1 oder n + 2 fehlt, es bedeutet, die Hand nicht gültig) und bewegen sich auf den nächsten niedrigsten Wert ist.

Wenn es mindestens drei Kacheln mit dem niedrigsten Wert, entfernen Sie sie als Set (wenn Sie fragen, „was ist, wenn sie Teil einer Straße waren?“, Der Ansicht, dass, wenn sie waren, dann gibt es auch drei von Fliesen n + 1 und drei der Fliese n + 2, die ebenfalls in Gruppen umgewandelt werden können) und weiter.

Wenn Sie eine leere Hand zu erreichen, ist die Hand gültig.

Zum Beispiel für Ihre ungültige Hand der Gesamt 60, was bedeutet, M = {3,6,9}:

Remove the 3: 112244556789
 - Start with 1: there are less than three, so remove a street
   -> impossible: 123 needs a 3

Remove the 6: impossible, there is only one

Remove the 9: impossible, there is only one

Mit Ihrem zweiten Beispiel 12345555678999, die insgesamt 78, was bedeutet, M = {3,6,9}:

Remove the 3: impossible, there is only one

Remove the 6: impossible, there is only one

Remove the 9: 123455556789
 - Start with 1: there is only one, so remove a street
   -> 455556789
 - Start with 4: there is only one, so remove a street
   -> 555789
 - Start with 5: there are three, so remove a set
   -> 789
 - Start with 7: there is only one, so remove a street
   -> empty : hand is valid, removals were [99] [123] [456] [555] [789]

Ihr drittes Beispiel 11223378888999 hat auch insgesamt 78, die Rückzieher bewirkt:

Remove the 3: 11227888899
 - Start with 1: there are less than three, so remove a street
   -> impossible: 123 needs a 3

Remove the 6: impossible, there are none

Remove the 9: 112233788889
 - Start with 1: there are less than three, so remove streets
   -> 788889
 - Start with 7: there is only one, so remove a street
   -> 888
 - Start with 8: there are three, so remove a set
   -> empty, hand is valid, removals were : [99] [123] [123] [789] [888]

Answer 2

Es ist ein besonderer Fall, dass Sie benötigen einige Nacharbeiten zu tun, es richtig zu machen. Dies geschieht, wenn eine run-of-drei und ein Paar mit dem gleichen Wert (aber in anderer Farbe).

Lassen b denates Bambus, c schenkt Charakter und d schenkt Punkt, versuchen Sie diese Hand:

b2,b3,b4,b5,b6,b7,c4,c4,c4,d4,d4,d6,d7,d8

d4,d4 should serve as the pair, and c4,c4,c4 should serve as the run-of-3 set.

Aber weil die drei „c4“ Fliesen vor der 2 d4 tiless erscheinen, werden die ersten 2 c4 Fliesen als das Paar aufgenommen werden, eine Waise c4 und 2 d4s verlassen, und diese drei Fliesen keinen gültigen Satz bilden .

In diesem Fall müssen Sie „return“ die 2 c4 Fliesen an der Hand zurück (und halten die Hand sortiert), und für das nächste Kachel suchen, die den Kriterien (Wert == 4) erfüllt. Dazu müssen Sie den Code machen müssen zu „erinnern“, dass es c4 versucht hatte, so in der nächsten Iteration es c4 und sucht nach anderen Fliesen mit Wert überspringen sollte == 4. Der Code wird ein bisschen chaotisch, aber machbar sein.

Answer 3

Ich würde es brechen in 2 Stufen.

1. Figure out mögliche Kombinationen. Ich denke, erschöpfende Prüfung mit diesen Zahlen möglich ist. Das Ergebnis dieses Schrittes ist eine Liste von Kombinationen, wobei jede Kombination hat einen Typen (Set, Straße oder ein Paar) und ein Muster mit den verwendeten Karten (könnte ein Bitmap sein).
2. Bei den vorherigen Informationen bestimmt möglich Sammlungen von Kombinationen. Dies ist, wo ein Bitmap würde sich als nützlich. Mit Bit-Operatoren, Sie bei der Nutzung der gleichen Fliese für verschiedene combinators sehen Überlappungen könnten.

Sie könnten auch einen Schritt tun 1.5, wo Sie überprüfen, nur zu sehen, ob genug von jeder Art zur Verfügung. Dieser Schritt und Schritt 2 wäre, wenn Sie einen allgemeinen Algorithmus erstellen würde. Der erste Schritt wäre schnell das gleiche für alle Zahlen von Fliesen und möglichen Kombinationen sein.