Algoritmo para encontrar calles y mismo tipo en una mano

Question

Esto es en realidad una pregunta basada en Mahjong, pero un Romme- o incluso de fondo a base de Poker también será suficiente fácil de entender.

En Mahjong 14 azulejos (azulejos son como tarjetas en Poker) están dispuestos para 4 juegos y un par. Una calle ( "123") siempre utiliza exactamente 3 azulejos, ni más ni menos. Un conjunto de la misma clase ( "111") consiste en exactamente 3 azulejos, también. Esto conduce a una suma de 3 * 4 + 2 = 14 azulejos.

Hay varias excepciones como Kan o trece huérfanos que no son relevantes aquí. Los colores y los rangos de valores (1-9) también no son importantes para el algoritmo.

Estoy tratando de determinar si una mano se pueden organizar de la forma descrita anteriormente. Por ciertas razones que no sólo debe ser capaz de tratar con 14 pero cualquier número 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 no ha implementado es la siguiente: Para cada baldosa, tratar de hacer a) una calle b) un conjunto c) un par. Si ninguno funciona (o no serían> 1 par), volver a la iteración anterior y tratar la siguiente opción, o, si este es el nivel más alto, fallar. Si no, quitar los azulejos usados ??en la lista de fichas restantes y continuar con la siguiente iteración.

Creo que este enfoque funciona y también sería razonablemente rápido (rendimiento es un "buen bono"), pero estoy interesado en su opinión al respecto. ¿Puede pensar en soluciones alternativas? ¿Esto o algo similar ya existe?

(No es tarea, Estoy aprendiendo a jugar al 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 se agrega a todos los números en una mano resuelto, se llega a un número de la forma 3N + 2 M, donde M es el valor de la baldosa 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 prueba de nueve pares posibles, es suficiente para tratar tres basado en una simple adición. Para cada par posible, eliminar dos baldosas con ese valor y pasar a la siguiente etapa del algoritmo para determinar si es posible.

Una vez que tenga esto, comenzar con el valor más bajo. Si hay menos de tres piezas con ese valor, significa que están necesariamente el primer elemento de una calle, por lo que eliminar esa calle (si usted no puede porque los azulejos n + 1 o n + 2 no aparece, significa que la mano no es válida) y pasar al siguiente valor más bajo.

Si hay al menos tres fichas con el valor más bajo, eliminarlos como un conjunto (si se le pregunta "¿y si fueran parte de una calle?" Consideran que si lo fueran, entonces hay también tres de baldosas n + 1 y tres de baldosas de n + 2, que también se puede convertir en sets) y continuar.

Si usted 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

Hay un caso especial que se necesita hacer algunas re-trabajo para hacerlo bien. Esto sucede cuando hay una carrera de tres y un par con el mismo valor (pero en el juego diferente).

Sea b denates bambú, c dona carácter, y dona d dot, trate de 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.

Sin embargo, debido a que las baldosas 3 "C4" se presentan ante el Tiless 2 d4, las 2 primeras baldosas c4 será recogido como el par, dejando un c4 huérfano y 2 D4S, y estos 3 azulejos no se formará un conjunto válido .

En este caso, tendrá que "retorno" de las baldosas 2 c4 atrás a la mano (y mantener la mano ordenadas), y la búsqueda de azulejo siguiente que cumpla con los criterios (valor == 4). Para ello tendrá que hacer el código "recordar" que había tratado c4 por lo que en la próxima iteración se debe omitir C4 y busca otras fichas con valor == 4. El código será un desordenado poco, pero factible.

Answer 3

Me dividirlo en 2 pasos.

1. Figura posibles combinaciones. Creo que la comprobació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 (set, calle, o par) y un patrón con las tarjetas utilizadas (podría ser un mapa de bits).
2. Con la información anterior, determinar posibles colecciones de combinaciones. Este es un mapa de bits, donde sería muy útil. El uso de operadores de bits, se podía ver solapamientos en el uso de la misma baldosa para diferentes combinadores.

También podría hacer un paso 1.5 en el que sólo comprueba para ver si lo suficiente de cada tipo está disponible. Este paso y el paso 2 estarían donde usted sería capaz de crear un algoritmo general. El primer paso sería la misma para todos los números de baldosas y las posibles combinaciones rápidamente.