Algoritmo per trovare strade e lo stesso tipo in una mano

Question

Questa è in realtà una domanda basata su Mahjong, ma anche uno sfondo basato su Romme o su Poker sarà facilmente sufficiente a capire.

In Mahjong 14 tessere (le tessere sono come carte in Poker) sono disposte a 4 set e una coppia. Una strada ("123") usa sempre esattamente 3 tessere, non di più e non di meno. Un set dello stesso tipo ("111") è composto esattamente da 3 tessere. Ciò porta a una somma di 3 * 4 + 2 = 14 tessere.

Ci sono varie eccezioni come Kan or Thirteen Orphans che non sono rilevanti qui. Anche i colori e gli intervalli di valori (1-9) non sono importanti per l'algoritmo.

Sto provando a determinare se una mano può essere disposta nel modo descritto sopra. Per determinati motivi dovrebbe non solo essere in grado di gestire 14 ma un numero qualsiasi 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 insiemi e un accoppiamento.
12345555678999-123, 456, 789, 555, 99
11223378888999 - 123, 123, 789, 888, 99
11223344556789 - non una mano valida

La mia idea attuale e non ancora implementato è questo: per ogni tessera, prova a fare a) una strada b) una serie c) una coppia. Se nessuno funziona (o ci sarebbe> 1 coppia), torna alla precedente iterazione e prova l'opzione successiva, oppure, se questo è il livello più alto, fallisci. Altrimenti, rimuovere le tessere usate dall'elenco delle tessere rimanenti e continuare con l'iterazione successiva.

Credo che questo approccio funzioni e sarebbe anche ragionevolmente veloce (le prestazioni sono un "bel bonus"), ma sono interessato alla tua opinione su questo. Puoi pensare a soluzioni alternative? Questo o qualcosa di simile esiste già?

(Non compiti a casa, I'm learning to play Mahjong.)

Answer 1

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

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

Quindi, se si sommano tutti i numeri in una mano risolta, si otterrà un numero del modulo 3N + 2M dove M è il valore della tessera 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 verificare nove possibili coppie, basta provare tre basato su una semplice addizione. Per ogni coppia possibile, rimuovi due tessere con quel valore e vai al prossimo passo dell'algoritmo per determinare se è possibile.

Una volta ottenuto, iniziare con il valore più basso. Se ci sono meno di tre tessere con quel valore, significa che sono necessariamente il primo elemento di una strada, quindi rimuovi quella strada (se non puoi perché mancano le tessere n + 1 o n + 2, significa la mano non è valido) e passare al valore più basso successivo.

Se ci sono almeno tre tessere con il valore più basso, rimuoverle come set (se chiedi "e se facessero parte di una strada?", Considera che se lo fossero, allora ci sono anche tre di piastrelle n +1 e 3 di tile n + 2, che possono anche essere trasformati in insiemi) e continuare.

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

Ad esempio, per la mano valido il totale è 60, il che significa 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, 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] 

tuo terzo esempio 11.223.378,888999 millions 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

avrei scomposizione in 2 fasi.

1. Calcolare le possibili combinazioni. Penso che un controllo esaustivo sia fattibile con questi numeri. Il risultato di questo passaggio è un elenco di combinazioni, in cui ogni combinazione ha un tipo (set, street o pair) e un pattern con le carte utilizzate (potrebbe essere una bitmap).
2. Con le informazioni precedenti, determinare le possibili raccolte di combinazioni. Questo è dove una bitmap sarebbe utile. Utilizzando operatori bit a bit, è possibile vedere sovrapposizioni nell'utilizzo della stessa tessera per combinatori diversi.

È anche possibile eseguire un passaggio 1.5 in cui è sufficiente verificare se è disponibile una quantità sufficiente di ciascun tipo. Questo passaggio e il passaggio 2 sarebbero dove si sarebbe in grado di creare un algoritmo generale. Il primo passo sarebbe lo stesso per tutti i numeri di tessere e possibili combinazioni rapidamente.

Answer 3

Esiste un caso speciale per cui è necessario eseguire alcune modifiche per farlo correttamente. Questo succede quando c'è un run-of-three e una coppia con lo stesso valore (ma in seme diverso).

Let b denates bambù, c dona carattere e d dona punto, 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 piastrelle del 3 "C4" compaiano davanti alla tiless 2 d4, i primi 2 c4 piastrelle saranno essere raccolti come la coppia, lasciando un orfano c4 e 2 d4, e queste 3 tessere non formeranno un set valido.

In questo caso, dovrai "restituire" le 2 tessere c4 alla mano (e mantenere la mano in ordine), e cercare la tessera successiva che soddisfi i criteri (valore == 4). Per far ciò dovrai fare in modo che il codice "ricordi" di aver provato c4 così nella successiva iterazione dovresti saltare c4 e cercare altre tessere con valore == 4. Il codice sarà un po 'disordinato, ma fattibile.