¿Es este un juego válido de Five Up (Dominoes)?

8

Un conjunto de fichas de dominó consiste en fichas con dos números, de modo que se representan todas las combinaciones de enteros del 0 al N. Los ejemplos a continuación se refieren a N = 6 por conveniencia, pero N = 9 y N = 12 también son comunes. La orientación de las baldosas no importa (que se imprimen normalmente con puntos en lugar de dígitos), así [1-6]y [6-1]se refieren a la misma baldosa, de los cuales sólo hay uno en un sistema.

La mayoría de los juegos que se juegan con fichas de dominó implican que los jugadores se turnan para agregar fichas de dominó a una línea de las que ya se jugaron en la mesa, de modo que uno de los números de la nueva ficha de dominó se coloca junto al mismo número en un extremo de la línea de la mesa. Por lo tanto, puede agregar [2-5]a cualquiera de los extremos de una línea existente de [2-3][3-3][3-5]producción [5-2][2-3][3-3][3-5]o [2-3][3-3][3-5][5-2].

Muchos de estos juegos requieren que se coloquen "dobles", fichas de dominó con dos del mismo número, perpendiculares a las otras fichas de dominó conectadas a ellas. Aparte de la puntuación que no nos interesa aquí, esto no tiene ningún efecto, excepto cuando ...

Muchos de esos juegos permiten que la "línea" se bifurque en algunos o en todos los dobles. Five Up es un juego en el que la línea puede bifurcarse en 3 líneas nuevas en cada doble, por lo que los cuatro lados de un doble pueden tener un dominó a juego.

Aquí hay un ejemplo de diseño de dominó de un "doble 6" en un juego de Five Up (donde A | B o AB es un solo dominó):

     4
     -
     0

3|0 0|0 0|2

     0
     -
     1

4|1 1|1 1|6
                3
     1          -
     -          6
     5
                6
6|5 5|5 5|0 0|6 - 6|2 2|1
                6
     5
     -          6
     4          -
                4

Su tarea es tomar una lista de fichas de dominó en el orden en que se agregaron a la tabla y determinar si esta orden representa o no un juego legal de Five Up.

Puede escribir un programa completo que tome la entrada de stdin, o una función que tome la entrada como uno o más parámetros.

La entrada canónica sería una lista o conjunto de dos tuplas de enteros. Una lista de listas, una matriz de matrices, un vector de tuplas, etc., son todas formas válidas en las que se pueden ingresar datos, como lo sería una cadena que representara cualquiera de las anteriores, o múltiples cadenas. La entrada solo contendrá pares de enteros no negativos, fichas de dominó válidas.

La salida debe ser un valor verdadero o falso, para juegos válidos e inválidos respectivamente.

Su código debe aceptar números de dominó arbitrariamente grandes, dentro de las capacidades de los valores enteros máximos de su idioma.

Ejemplos:

  • 0-6 es válido, como lo es cualquier otro dominó
  • 0-6 6-0no es válido, solo hay un 0-6dominó en un conjunto
  • 6-6 6-5 5-3 3-0 es válido, un arreglo lineal simple
  • 6-6 6-5 3-0 5-3no es válido, no hay 3o está 0en juego para que el tercer dominó se conecte antes de 5-3ser jugado
  • 1-1 1-2 1-3 1-4 1-5 1-6no es válido, los cuatro 1extremos abiertos se utilizan sin dejar ningún lugar para conectar el1-6
  • 1-1 1-2 1-3 1-4 1-5 3-6 1-6 es válido, el 3-6 se conecta al 1-3, luego el 1-6 puede conectarse al 3-6
  • 5-5 5-4 5-0 0-6 6-6 6-4 6-2 2-1 6-3 5-1 1-1 1-6 4-1 1-0 0-0 2-0 3-0 0-4 es válido, el ejemplo ilustrado arriba
  • 12-12 12-1 3-12 3-1 1-2 3-3 es válido, utiliza fichas de dominó más grandes y tiene una ubicación ambigua

NOTA: La función requerida aquí no es una verificación perfecta para juegos válidos de Five Up. Estamos ignorando aquí las reglas sobre qué dominó se juega primero, lo que requeriría más información sobre la variante del juego y el número de jugadores, y descalificaría a una minoría significativa de entradas.

Sparr
fuente
¿Necesitamos tener en cuenta las restricciones geométricas en la colocación, es decir, la cadena de dominó chocando contra sí misma?
xnor
@xnor no lo haces. Olvidé mencionar la convención común de que la "línea" puede doblarse arbitrariamente por conveniencia en cualquier juego de dominó. también es bueno para evitar los bordes de la mesa :)
Sparr
Creo que podría ser posible producir un orden de juego patológico con un juego doble de 12 fichas de dominó que no puedan evitar la auto intersección. Definitivamente es posible con conjuntos más grandes. Ignoremos esos casos. En el peor de los casos, se pueden resolver doblando la línea en 3D :)
Sparr
¿Realmente necesitamos poder manejar fichas de dominó que tienen valores> 6? Si es así, ¿podría aclarar eso en la especificación y tal vez agregar un caso de prueba? De lo contrario, sin embargo, buen desafío - +1 de mi parte.
Shaggy
@Shaggy agregó un caso de prueba para un dominó más grande
Sparr el

Respuestas:

1

Haskell , 188 174 168 bytes

f(p:r)=[p]!r$p?p
(s!(p:r))o|b<-[p,reverse p]=or[(q:s)!r$q%o|q<-b,elem(q!!0)o,all(`notElem`s)b]
(s!_)o=1<3
p@[x,y]?r=[c|x==y,c<-p]++r
p@[x,y]%(a:r)|a/=x=a:p%r|z<-y:r=p?z

Pruébalo en línea! Ejemplo de uso: f [[6,6],[6,5],[5,3],[3,0]]rendimientos True.

Sin golf:

f :: [[Int]] -> Bool
f (p:r) = check [p] (double p p) r

check :: [[Int]] -> [Int] -> [[Int]] -> Bool
check seen open [] = True
check seen open ([x,y]:r) = 
	  notElem [x,y] seen
   && notElem [y,x] seen
   && (elem x open && check ([x,y]:seen) (update [x,y] open) r 
   ||  elem y open && check ([y,x]:seen) (update [y,x] open) r)

double :: [Int] -> [Int] -> [Int]
double [x,y] rest = 
    if x==y 
    then [x,y] ++ rest 
    else rest

update :: [Int] -> [Int] -> [Int]
update [x,y] (a:rest) = 
    if x==a 
    then double [x,y] (y:rest) 
    else a : update [x,y] rest

Pruébalo en línea!

Laikoni
fuente
0

R , 224 bytes

function(L,x=c(),y=c()){o=T
z=length
if(z(L)){p=sort(L[1:2])
w=rep(p,2-(p[2]>p[1]))
x=rbind(p,x)
if(z(y)){m=match(p,y,0)
v=which.max(m)
if(m[v]>0){y=y[-m[v]]
w=w[-v]}}
y=c(y,w)
L=L[-1:-2]
o=o&f(L,x,y)&!sum(duplicated(x))}
o}

Pruébalo en línea!

El código recibe las piezas como una lista ordenada y devuelve VERDADERO o FALSO según las especificaciones. La función escanea recursivamente cada pieza, agrega la pieza a un índice para verificar la ausencia de duplicados y realiza un seguimiento de los puntos de inserción disponibles para verificar que la pieza se pueda agregar efectivamente a la pila. El manejo de las conexiones de piezas (por ejemplo, uniendo un 1-2 por el 1 o por el 2) se realiza de manera codiciosa, por lo que no es del todo imposible que algunas configuraciones extrañas puedan explotar.

NofP
fuente
desafortunadamente la avaricia no es lo suficientemente buena. considere 6-6 6-3 6-2 2-3que necesita poder manejar esto con 2-_o 3-_después porque 2-3podría haberse colocado en cualquier extremo.
Sparr
Le echaré un vistazo.
NofP