Algoritmo per trovare strade e stesso tipo in una mano

Question

Questo è in realtà una domanda Mahjong-based, ma un Romme- o addirittura sfondo Poker-based sarà anche facilmente sufficiente per capire.

In Mahjong 14 tessere (piastrelle sono come le carte nel Poker) sono disposte a 4 set e un paio. Una strada ( "123") utilizza sempre esattamente 3 piastrelle, non più e non meno. Una serie dello stesso tipo ( "111") consiste di esattamente 3 piastrelle, anche. Questo porta ad una somma di 3 * 4 + 2 = 14 tessere.

Ci sono varie eccezioni, come Kan o tredici orfani che non sono rilevanti qui. Colori e intervalli di valori (1-9) non sono inoltre importanti per l'algoritmo.

Sto cercando di determinare se una mano può essere organizzato nel modo descritto sopra. Per alcune ragioni, non solo dovrebbe essere in grado di trattare con 14, ma qualsiasi numero di tessere. (Il passo successivo sarebbe quello di trovare quante tessere devono essere scambiati per essere in grado di completare una mano.)

Esempi:

11122233344455 -. Abbastanza facile, 4 set e un paio
12345555678999 - 123, 456, 789, 555, 99
11223378888999 - 123, 123, 789, 888, 99
11223344556789 - non una mano valida

Il mio attuale e non ancora implementato idea è questa: per ogni tessera, provare a fare a) una strada b) un insieme c) una coppia. Se nessuna opere (o non ci sarebbe> 1 coppia), tornare alla precedente iterazione e provare l'opzione successiva, o, se questo è il livello più alto, fallire. Altrimenti, rimuovere le piastrelle utilizzate dalla lista delle tessere rimanenti e continuare con l'iterazione successiva.

Credo che questo approccio funziona e sarebbe anche abbastanza veloce (performance è un "bonus"), ma mi interessa la vostra opinione su questo. Riuscite a pensare a soluzioni alternative? Questo o qualcosa di simile già esiste?

(Non compiti, sto imparando a giocare a Mahjong. )

Answer 1

La somma dei valori in una strada e in un set può essere diviso per 3:

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

Quindi, se si aggiunge insieme tutti i numeri in una mano risolto, si otterrebbe un numero di forma 3N + 2M dove M è il valore della piastrella nella coppia. Il resto della divisione per tre (total % 3) è, per ogni valore di M:

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

Così, invece di dover prova nove possibili coppie, devi solo provare a tre sulla base di una semplice aggiunta. Per ogni possibile coppia, rimuovere due tessere con tale valore e passare alla fase successiva del algoritmo per determinare se è possibile.

Una volta fatto questo, inizia con il valore più basso. Se ci sono meno di tre piastrelle con quel valore, significa che sono necessariamente il primo elemento di una strada, in modo da rimuovere quella strada (se non è possibile, perché le piastrelle n + 1 o N + 2 manca, significa che la mano non è valido) e passare al successivo valore più basso.

Se ci sono almeno tre tessere con il valore più basso, rimuoverli come un insieme (se si chiede "che cosa se fossero parte di una strada?" Ritengono che se lo fossero, poi ci sono anche tre delle piastrelle di n + 1 e tre di piastrelle n + 2, che può anche essere trasformato in set) e continuare.

Se si raggiunge una mano vuota, la mano è valida.

Ad esempio, per la vostra mano non valida il totale è di 60, il che significa che 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

Con il secondo esempio 12345555678999, il totale è 78, il che significa 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]

Il terzo esempio 11223378888999 ha anche un totale di 78, che provoca backtracking:

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

C'è un caso particolare che è necessario fare un po 'ri-lavoro per farlo bene. Questo avviene quando v'è un run-of-tre ed una coppia con lo stesso valore (tranne nel seme differente).

Sia B denates bambù, c dona carattere e d dona dot, provare questa mano:

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.

Ma perché le 3 tessere "C4" compaiano davanti alla tiless 2 d4, i primi 2 tessere C4 sarà preso come la coppia, lasciando un c4 orfani e 2 D4S, e questi 3 tessere non si formerà un insieme valido .

In questo caso, avrete bisogno di "ritorno" delle 2 tessere C4 indietro alla mano (e mantenere la mano allineati), e la ricerca per il prossimo mattonelle che soddisfa i criteri (valore == 4). Per fare ciò è necessario per rendere il codice "ricordare" che aveva cercato c4 così in prossima iterazione dovrebbe saltare c4 e cerca altre tessere con valore == 4. Il codice sarà un po 'disordinato, ma fattibile.

Answer 3

Vorrei scomposizione in 2 passi.

1. Figura su combinazioni possibili. Credo che il controllo esaustivo è fattibile con questi numeri. Il risultato di questa fase è un elenco di combinazioni, dove ogni combinazione contiene un tipo (set, strada, o coppia) e un pattern con le carte utilizzate (potrebbe essere un bitmap).
2. Con le informazioni precedenti, a determinare le possibili collezioni di combinazioni. Questo è dove una bitmap sarebbe venuto in aiuto. Uso degli operatori bit a bit, si poteva vedere sovrapposizioni nell'uso dello stesso tegola per i diversi combinatori.

Si potrebbe anche fare un passo di 1,5 dove basta controllare per vedere se un numero sufficiente di ogni tipo è disponibile. Questo passo e la fase 2 sarebbe dove si sarebbe in grado di creare un algoritmo generale. Il primo passo sarebbe la stessa per tutti i numeri di piastrelle e le possibili combinazioni in modo rapido.