Description du défi

Dominoes est un jeu joué avec des tuiles avec deux valeurs dessus - une à gauche, une à droite, par exemple [2|4]ou [4|5]. Deux tuiles peuvent être jointes si elles contiennent une valeur commune. Les deux tuiles ci-dessus peuvent être jointes comme ceci:

[2|4][4|5]

Nous appellerons une séquence de ntuiles jointes une chaîne de longueur n. Bien sûr, les tuiles peuvent être tournées, donc les tuiles [1|2], [1|3]et [5|3]peuvent être réarrangées en une chaîne [2|1][1|3][3|5]de longueur 3.

À partir d'une liste de paires d'entiers, déterminez la longueur de la chaîne la plus longue pouvant être formée à l'aide de ces tuiles. Si la liste est vide, la bonne réponse est 0(notez que vous pouvez toujours former une chaîne de longueur à 1partir d'une liste de tuiles non vide).

Exemple d'entrée / sortie

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

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

Essayez-le en ligne!

Explication

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 d'autres termes, pour une entrée comme [[1:2]:[1:3]:[5:3]], nous essayons de la réorganiser en une chaîne valide [[2:1]:[1:3]:[3:5]], puis d'aplatir / décapiter / détacher pour produire [1:1:3:3:5:_](où _représente une inconnue). La combinaison de ~cet :{…l2}adivise efficacement cela en groupes de 2 éléments, et nous nous assurons que tous les groupes sont égaux. Au fur et à mesure que nous aplatissons (doublons la longueur), supprimons un élément du début et en ajoutons un à la fin (pas de changement), et regroupés en paires (divisant par deux la longueur), cela aura la même longueur que la chaîne de dominos d'origine.

L'instruction "behead" échouera s'il n'y a pas de dominos dans l'entrée (en fait, IIRC :paéchouera également; an'aime pas les listes vides), donc nous avons besoin d'un cas spécial pour 0. (Une grande raison pour laquelle nous avons l'asymétrie entre bet ~kest si que nous n'avons pas besoin d'un cas spécial pour 1.)

Brachylog , 29 octets

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

Essayez-le en ligne!

Je suis sûr que c'est terriblement long, mais peu importe. C'est aussi terriblement lent.

Explication

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 raison pour laquelle il trouvera le plus grand est parce qu'il s - subsetgénère des points de choix du plus grand au plus petit sous-ensemble.

Mathematica, 191 octets

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

Peut être joué un peu au golf, j'en suis sûr. Mais fondamentalement le même algorithme que dans la réponse Brachylog de Fatalize , avec un test légèrement différent à la fin.

JavaScript (Firefox 30-57), 92 octets

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

• lest la dernière valeur, ou undefinedpour l'invocation initiale. l-nest donc une valeur fausse si le domino peut être joué.
• d est le domino considéré.
• nest la fin du domino envisagé pour l'enchaînement au domino précédent. L'autre extrémité peut facilement être calculée comme d[0]+d[1]-n.
• 0, gère simplement le cas de base des dominos non jouables.

Haskell , 180 134 131 131 117 octets

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

Essayez-le en ligne! La nouvelle approche s'est avérée à la fois plus courte et plus efficace. Au lieu de toutes les permutations possibles, seules toutes les chaînes valides sont construites.

Edit: La version 117 octets est encore beaucoup plus lente, mais toujours plus rapide que la force brute.

Ancienne méthode de force brute:

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

Il s'agit d'une implémentation par force brute qui essaie toutes les permutations possibles (le nombre de permutations possibles semble être donné par A000165 , la " double factorielle des nombres pairs "). L'essayer en ligne gère à peine les entrées jusqu'à la longueur 7 (ce qui est assez impressionnant car 7 correspond à 645120 permutations).

Usage:

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

Python 2, 279 octets

Golfé:

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

Essayez-le en ligne!

Même chose avec quelques commentaires:

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

Je poste parce que je n'ai vu aucune réponse en python ... quelqu'un verra ma réponse et, dégoûté, sera forcé de publier quelque chose de beaucoup plus court et efficace.

Clojure, 198 183 octets

Mise à jour: meilleure gestion du "maximum de séquence éventuellement vide"

(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 précédente:

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

Convention d'appel et cas de test:

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

Fretourne les éléments de la liste Csans l'élément a, Mretourne le maximum de chiffres d'entrée ou 1.

Lest la fonction principale, lorsqu'elle est appelée avec un seul argument, elle génère toutes les pièces de départ possibles et trouve la longueur maximale pour chacune d'elles. Lorsqu'il est appelé avec deux arguments, le lest le premier élément de la séquence auquel le morceau suivant doit correspondre et Rest le reste des morceaux.

Générer des permutations et "choisir un élément et le diviser pour se reposer" était assez difficile à mettre en œuvre de manière succincte.