Descripción del desafío

Dominoes es un juego que se juega con fichas con dos valores: uno a la izquierda, otro a la derecha, por ejemplo [2|4]o [4|5]. Se pueden unir dos mosaicos si contienen un valor común. Los dos mosaicos anteriores se pueden unir así:

[2|4][4|5]

Llamaremos a una secuencia de nmosaicos unidos una cadena de longitud n. Por supuesto, las fichas se pueden rotar, por lo que las fichas [1|2], [1|3]y [5|3]se pueden reorganizar en una cadena [2|1][1|3][3|5]de longitud 3.

Dada una lista de pares de enteros, determine la longitud de la cadena más larga que se puede formar con estos mosaicos. Si la lista está vacía, la respuesta correcta es 0(tenga en cuenta que siempre puede formar una cadena de longitud a 1partir de una lista no vacía de mosaicos).

Entrada / salida de muestra

[(0, -1), (1, -1), (0, 3), (3, 0), (3, 1), (-2, -1), (0, -1), (2, -2), (-1, 2), (3, -3)] -> 10
([-1|0][0|-1][-1|2][2|-2][-2|-1][-1|1][1|3][3|0][0|3][3|-3])

[(17, -7), (4, -9), (12, -3), (-17, -17), (14, -10), (-6, 17), (-16, 5), (-3, -16), (-16, 19), (12, -8)] -> 4
([5|-16][-16|-3][-3|12][12|-8])

[(1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1)] -> 7
([1|1][1|1][1|1][1|1][1|1][1|1][1|1])

[(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11)] -> 1
(any chain of length 1)

[] -> 0
(no chain can be formed)

Brachylog , 23 bytes

s:papcb~k~c:{#=l2}al|,0

Pruébalo en línea!

Explicación

s:papcb~k~c:{#=l2}al|,0
s                         Check subsets of the input (longest first).
 :pa                      Check all permutations inside the input's elements
    p                     and all permutations /of/ the input's elements.
     c                    Flatten the result;
      b                   delete the first element;
       ~k                 find something that can be appended to the end so that
         ~c               the result can be unflattened into
           :{    }a       a list whose elements each have the property:
             #=             all the elements are equal
               l2           and the list has two elements.
                   l      If you can, return that list's length.
                    |,0   If all else fails, return 0.

En otras palabras, para entradas como [[1:2]:[1:3]:[5:3]], tratamos de reorganizarlo en una cadena válida [[2:1]:[1:3]:[3:5]], luego aplanar / decapitar / desenredar para producir [1:1:3:3:5:_](donde _representa un desconocido). La combinación de ~cy :{…l2}aefectivamente divide esto en grupos de 2 elementos, y nos aseguramos de que todos los grupos sean iguales. A medida que aplanamos (duplicamos la longitud), eliminamos un elemento desde el principio y agregamos uno al final (sin cambios), y lo agrupamos en pares (reduciendo a la mitad la longitud), esto tendrá la misma longitud que la cadena original de dominó.

La instrucción "decapitar" fallará si no hay fichas de dominó en la entrada (en realidad, IIRC :patambién fallará; no ale gustan las listas vacías), por lo que necesitamos un caso especial para 0. (Una gran razón por la que tenemos la asimetría entre by ~kes que tampoco necesitamos un caso especial para 1.)

Brachylog , 29 bytes

v0|sp:{|r}aLcbk@b:{l:2%0}a,Ll

Pruébalo en línea!

Estoy bastante seguro de que esto es terriblemente largo, pero lo que sea. Esto también es muy lento.

Explicación

v0                               Input = [], Output = 0
  |                              Or
   sp:{|r}aL                     L (a correct chain) must be a permutation of a subset of the
                                   Input with each tile being left as-is or reversed
           Lcbk                  Concatenate L into a single list and remove the first and
                                   last elements (the two end values don't matter)
               @b                Create a list of sublists which when concatenated results in
                                   L, and where each sublist's elements are identical
                 :{     }a,      Apply this to each sublist:
                   l:2%0           It has even length
                           Ll    Output = length(L)

La razón por la que esto encontrará el más grande es porque s - subset genera puntos de elección del subconjunto más grande al más pequeño.

Mathematica, 191 bytes

If[#=={},0,Max[Length/@Select[Flatten[Rest@Permutations[#,∞]&/@Flatten[#,Depth[#]-4]&@Outer[List,##,1]&@@({#,Reverse@#}&/@#),1],MatchQ[Differences/@Partition[Rest@Flatten@#,2],{{0}...}]&]]]&

Se puede jugar al golf un poco, estoy seguro. Pero básicamente el mismo algoritmo que en la respuesta Brachylog de Fatalize , con una prueba ligeramente diferente al final.

JavaScript (Firefox 30-57), 92 bytes

(a,l)=>Math.max(0,...(for(d of a)for(n of d)if(!(l-n))1+f(a.filter(e=>e!=d),d[0]+d[1]-n)))

• les el último valor, o undefinedpara la invocación inicial.l-nes, por lo tanto, un valor falso si se puede jugar al dominó.
• d es el dominó bajo consideración.
• nes el final del dominó bajo consideración para encadenar al dominó anterior. El otro extremo puede calcularse fácilmente comod[0]+d[1]-n .
• 0, simplemente maneja el caso base de dominó no jugable.

Haskell , 180 134 131 117 bytes

p d=maximum$0:(f[]0d=<<d)
f u n[]c=[n]
f u n(e@(c,d):r)a@(_,b)=f(e:u)n r a++(f[](n+1)(r++u)=<<[e|b==c]++[(d,c)|b==d])

Pruébalo en línea! El nuevo enfoque resultó ser más corto y más eficiente. En lugar de todas las permutaciones posibles, solo se crean todas las cadenas válidas.

Editar: La versión de 117 bytes es mucho más lenta nuevamente, pero aún más rápida que la fuerza bruta.

Viejo método de fuerza bruta:

p(t@(a,b):r)=[i[]t,i[](b,a)]>>=(=<<p r)
p e=[e]
i h x[]=[h++[x]]
i h x(y:t)=(h++x:y:t):i(h++[y])x t
c%[]=[0]
c%((_,a):r@((b,_):_))|a/=b=1%r|c<-c+1=c:c%r
c%e=[c]
maximum.(>>=(1%)).p

Esta es una implementación de fuerza bruta que intenta todas las permutaciones posibles (el número de permutaciones posibles parece ser dado por A000165 , el " factorial doble de números pares "). Pruébelo en línea apenas administra entradas de hasta 7 (lo cual es impresionante ya que 7 corresponde a 645120 permutaciones).

Uso:

Prelude> maximum.(>>=(1%)).p $ [(1,2),(3,2),(4,5),(6,7),(5,5),(4,2),(0,0)]
4

Python 2, 279 bytes

Golfizado:

l=input()
m=0
def f(a,b):
 global m
 l=len(b)
 if l>m:m=l
 for i in a:
  k=a.index(i)
  d=a[:k]+a[k+1:]
  e=[i[::-1]]
  if not b:f(d,[i])
  elif i[0]==b[-1][1]:f(d,b+[i])
  elif i[0]==b[0][0]:f(d,e+b)
  elif i[1]==b[0][0]:f(d,[i]+b)
  elif i[1]==b[-1][1]:f(d,b+e)
f(l,[])
print m

Pruébalo en línea!

Lo mismo con algunos comentarios:

l=input()
m=0
def f(a,b):
 global m
 l=len(b)
 if l>m:m=l                      # if there is a larger chain
 for i in a:
  k=a.index(i)
  d=a[:k]+a[k+1:]                # list excluding i
  e=[i[::-1]]                    # reverse i
  if not b:f(d,[i])              # if b is empty
                                 # ways the domino can be placed:
  elif i[0]==b[-1][1]:f(d,b+[i]) # left side on the right
  elif i[0]==b[0][0]:f(d,e+b)    # (reversed) left side on the left
  elif i[1]==b[0][0]:f(d,[i]+b)  # right side on left
  elif i[1]==b[-1][1]:f(d,b+e)   # (reversed) right side on the right
f(l,[])
print m

Estoy publicando porque no vi ninguna respuesta de Python ... alguien verá mi respuesta y, disgustado, se verá obligado a publicar algo mucho más corto y eficiente.

Clojure, 198183 bytes

Actualización: Mejor manejo del "máximo de secuencia posiblemente vacía"

(defn F[a C](remove(fn[i](identical? i a))C))(defn M[C](apply max 0 C))(defn L([P](M(for[p P l p](L l(F p P)))))([l R](+(M(for[r R[i j][[0 1][1 0]]:when(=(r i)l)](L(r j)(F r R))))1)))

Version anterior:

(defn F[a C](remove(fn[i](identical? i a))C))(defn M[C](apply max 1 C))(defn L([P](if(empty? P)0(M(for[p P l p](L l(F p P))))))([l R](M(for[r R[i j][[0 1][1 0]]:when(=(r i)l)](+(L(r j)(F r R))1)))))

Convenciones de convocatoria y casos de prueba:

(L [])
(L [[2 4] [3 2] [1 4]])
(L [[3, 1] [0, 3], [1, 1]])
(L [[17 -7] [4 -9] [12 -3] [-17 -17] [14 -10] [-6 17] [-16 5] [-3 -16] [-16 19] [12 -8]])
(L [[0 -1] [1 -1] [0 3] [3 0] [3 1] [-2 -1] [0 -1] [2 -2] [-1 2] [3 -3]])
(L [[1 1] [1 1] [1 1] [1 1] [1 1] [1 1] [1 1]])

Fdevuelve elementos de la lista Csin el elemento a, Mdevuelve el máximo de ingerers de entrada o 1.

Les la función principal, cuando se llama con un solo argumento, genera todas las piezas iniciales posibles y encuentra la longitud máxima para cada una de ellas. Cuando se llama con dos argumentos, les el primer elemento de la secuencia con el que debe coincidir la siguiente pieza y Res el resto de las piezas.

Generar permutaciones y "elegir un elemento y dividir para descansar" fue bastante difícil de implementar de manera sucinta.