Algoritmo para encontrar calles y el mismo tipo en una mano

Question

Esto es realmente una pregunta basada en Mahjong, pero un fondo basado en Romme o incluso Poker también será suficiente para entender.

En Mahjong 14 fichas (las fichas son como cartas en el Póker) se organizan en 4 series y un par. Una calle ("123") siempre usa exactamente 3 fichas, ni más ni menos. Un conjunto del mismo tipo ("111") consta exactamente de 3 fichas, también. Esto lleva a una suma de 3 * 4 + 2 = 14 fichas.

Existen varias excepciones como Kan o Trece Huérfanos que no son relevantes aquí. Los colores y los rangos de valores (1-9) tampoco son importantes para el algoritmo.

Estoy tratando de determinar si una mano se puede organizar de la manera descrita anteriormente. Por ciertas razones, no solo debería poder tratar con 14 sino con cualquier cantidad de fichas. (El siguiente paso sería encontrar cuántos azulejos necesitan ser intercambiados para poder completar una mano.)

Ejemplos:

11122233344455 - bastante fácil, 4 juegos y un par.
12345555678999 - 123, 456, 789, 555, 99
11223378888999 - 123, 123, 789, 888, 99
11223344556789 - no es una parte válida

Mi idea actual y todavía no se ha implementado es la siguiente: Para cada azulejo, intente hacer a) una calle b) un conjunto c) un par. Si ninguno funciona (o hubiera> 1 par), regrese a la iteración anterior y pruebe la siguiente opción, o, si este es el nivel más alto, falle. De lo contrario, elimine las fichas usadas de la lista de fichas restantes y continúe con la siguiente iteración.

Creo que este enfoque funciona y también sería razonablemente rápido (el rendimiento es una "bonificación agradable"), pero me interesa su opinión al respecto. ¿Puedes pensar en soluciones alternativas? ¿Esto o algo similar ya existe?

(No es tarea, I'm learning to play Mahjong.)

Answer 1

La suma de los valores en una calle y en un conjunto se puede dividir por 3:

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

Por lo tanto, si suma todos los números en una mano resuelta, obtendría un número de la forma 3N + 2M donde M es el valor de la ficha en el par. El resto de la división por tres (total % 3) es, para cada valor de M:

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

Así, en lugar de tener que probar nueve pares posibles, es suficiente para tratar tres basado en una simple adición. Para cada par posible, elimine dos fichas con ese valor y continúe con el siguiente paso del algoritmo para determinar si es posible.

Una vez que tenga esto, comience con el valor más bajo. Si hay menos de tres fichas con ese valor, significa que son necesariamente el primer elemento de una calle, por lo tanto, elimine esa calle (si no puede porque faltan las fichas n + 1 o n + 2, significa que la mano no es válido) y pasar al siguiente valor más bajo.

Si hay al menos tres fichas con el valor más bajo, elimínelas como un conjunto (si pregunta "¿y si fueran parte de una calle?" Considere que si lo fueran, entonces también hay tres +1 y tres de mosaico n + 2, que también se pueden convertir en conjuntos) y continuar.

Si llega a una mano vacía, la mano es válida.

Por ejemplo, para su mano no válido el total es de 60, lo que 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 su segundo ejemplo 12345555678999, el total es 78, lo que 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] 

Su tercer ejemplo 11223378888999 también tiene un total de 78, lo que provoca el retroceso:

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

Me dividirlo en 2 pasos.

1. Calcule las posibles combinaciones. Creo que la verificación exhaustiva es factible con estos números. El resultado de este paso es una lista de combinaciones, donde cada combinación tiene un tipo (conjunto, calle o par) y un patrón con las tarjetas utilizadas (podría ser un mapa de bits).
2. Con la información anterior, determine las posibles colecciones de combinaciones. Aquí es donde un mapa de bits sería útil. Usando operadores bit a bit, podría ver superposiciones en el uso de la misma ficha para diferentes combinadores.

También puede hacer un paso 1.5 donde simplemente verifique si hay suficiente de cada tipo disponible. Este paso y el paso 2 serían donde podría crear un algoritmo general. El primer paso sería el mismo para todos los números de fichas y posibles combinaciones rápidamente.

Answer 3

Hay un caso especial en el que necesita volver a trabajar para hacerlo bien. Esto sucede cuando hay un run-of-three y un par con el mismo valor (pero con un palo diferente).

al B denates bambú, c dona carácter, y d dona punto, tratar esta 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. 

Pero debido a que el 3 "C4" azulejos aparecen antes de la Tiless 2 d4, las 2 c4 primeros azulejos se ser recogido como el par, dejando un huérfano c4 y 2 d4s, y estas 3 fichas no formarán un conjunto válido.

En este caso, tendrá que "devolver" las 2 fichas de c4 a la mano (y mantener la mano ordenada), y buscar la siguiente ficha que cumpla con los criterios (valor == 4). Para hacer eso necesitarás hacer que el código "recuerde" que había intentado c4, así que en la próxima iteración debería saltear c4 y buscar otras fichas con valor == 4. El código será un poco desordenado, pero factible.