Descrição do Desafio

Dominó é um jogo jogado com peças com dois valores: um à esquerda, outro à direita, por exemplo [2|4]ou [4|5]. Duas peças podem ser unidas se elas contiverem um valor comum. Os dois blocos acima podem ser unidos assim:

[2|4][4|5]

Vamos chamar uma sequência de nblocos unidos de uma cadeia de comprimento n. Claro, telhas pode ser rodado, de modo que as telhas [1|2], [1|3]e [5|3]podem ser reorganizados em uma cadeia [2|1][1|3][3|5]de comprimento 3.

Dada uma lista de pares de números inteiros, determine o comprimento da cadeia mais longa que pode ser formada usando esses blocos. Se a lista estiver vazia, a resposta correta é 0(observe que você sempre pode formar uma cadeia de comprimento a 1partir de uma lista não vazia de blocos).

Entrada / saída de amostra

[(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)

Braquilog , 23 bytes

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

Experimente online!

Explicação

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.

Portanto, em outras palavras, para entradas como [[1:2]:[1:3]:[5:3]], tentamos reorganizá-la em uma cadeia válida e [[2:1]:[1:3]:[3:5]], em seguida, aplainamos / decapitamos / retire a faca para produzir [1:1:3:3:5:_](onde _representa um desconhecido). A combinação ~ce :{…l2}aefetivamente divide isso em grupos de 2 elementos, e garantimos que todos os grupos sejam iguais. À medida que aplainamos (dobrando o comprimento), removemos um elemento do início e adicionamos um no final (sem alteração) e agrupamos em pares (diminuindo pela metade), este terá o mesmo comprimento que a cadeia original de dominó.

A instrução "decapitar" falhará se não houver dominó na entrada (na verdade, o IIRC :patambém falhará; anão gosta de listas vazias); portanto, precisamos de um caso especial para 0. (Um grande motivo pelo qual temos a assimetria entre be ~ké tão que também não precisamos de um caso especial para 1.)

Braquilog , 29 bytes

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

Experimente online!

Certamente isso é muito longo, mas tanto faz. Isso também é muito lento.

Explicação

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)

A razão pela qual essa será a maior é porque s - subsetgera pontos de escolha do maior ao menor subconjunto.

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}...}]&]]]&

Pode ser jogado um pouco, tenho certeza. Mas basicamente o mesmo algoritmo da resposta Brachylog de Fatalize , com um teste ligeiramente diferente no 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)))

• lé o último valor ou undefinedpara a chamada inicial. l-né, portanto, um valor falso se o dominó puder ser jogado.
• d é o dominó em consideração.
• né o fim do dominó em consideração para encadeamento com o dominó anterior. A outra extremidade pode ser facilmente calculada como d[0]+d[1]-n.
• 0, simplesmente lida com o gabinete básico de nenhum dominó jogável.

Haskell , 180 134 131 117 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])

Experimente online! A nova abordagem acabou sendo mais curta e mais eficiente. Em vez de todas as permutações possíveis, apenas todas as cadeias válidas são construídas.

Edit: A versão de 117 bytes é muito mais lenta novamente, mas ainda mais rápida que a força bruta.

Método antigo de força 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 é uma implementação de força bruta que tenta todas as permutações possíveis (o número de permutações possíveis parece ser dado por A000165 , o " fatorial duplo dos números pares "). Experimente on-line mal consegue entradas de comprimento 7 (o que é impressionante, pois 7 corresponde a 645120 permutações).

Uso:

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

Python 2, 279 bytes

Golfe:

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

Experimente online!

A mesma coisa com alguns comentários:

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

Estou postando porque não vi nenhuma resposta em python ... alguém verá minha resposta e, com nojo, será forçado a postar algo muito mais curto e eficiente.

Clojure, 198 183 bytes

Atualização: Melhor manipulação de "máximo de sequência possivelmente vazia"

(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)))

Versão 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)))))

Chamando convenções e casos de teste:

(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]])

Fretorna elementos da lista Csem o elemento a, Mretorna o máximo de ingerers de entrada ou 1.

Lé a função principal, quando chamada com um único argumento, gera todas as peças iniciais possíveis e encontra o comprimento máximo para cada uma delas. Quando chamado com dois argumentos, lé o primeiro elemento da sequência à qual a próxima peça deve corresponder e Ré o restante das peças.

Gerar permutações e "escolher um elemento e dividir para descansar" foi bastante complicado de implementar de forma sucinta.