Longest domino chain

Question

Challenge description

Dominoes is a game played with tiles with two values on it - one on the left, one on the right, for example [2|4] or [4|5]. Two tiles can be joined together if they contain a common value. The two tiles above can be joined like this:

[2|4][4|5]

We'll call a sequence of n joined tiles a chain of length n. Of course, tiles can be rotated, so tiles [1|2], [1|3] and [5|3] can be rearranged into a chain [2|1][1|3][3|5] of length 3.

Given a list of pairs of integers, determine the length of the longest chain that can be formed using these tiles. If the list is empty, the correct answer is 0 (note that you can always form a chain of length 1 from a non-empty list of tiles).

Sample input / output

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

Answer 1

Brachylog, 23 bytes

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

Try it online!

Explanation

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.

So in other words, for input like [[1:2]:[1:3]:[5:3]], we try to rearrange it into a valid chain [[2:1]:[1:3]:[3:5]], then flatten/behead/unkknife to produce [1:1:3:3:5:_] (where _ represents an unknown). The combination of ~c and :{…l2}a effectively splits this into groups of 2 elements, and we ensure that all the groups are equal. As we flattened (doubling the length), removed one element from the start and added one at the end (no change), and grouped into pairs (halving the length), this will have the same length as the original chain of dominoes.

The "behead" instruction will fail if there are no dominoes in the input (actually, IIRC the :pa will also fail; a dislikes empty lists), so we need a special case for 0. (One big reason we have the asymmetry between b and ~k is so that we don't also need a special case for 1.)

Answer 2

Brachylog, 29 bytes

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

Try it online!

Pretty sure this is awfully long, but whatever. This is also awfully slow.

Explanation

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)

The reason this will find the biggest one is because s - subset generates choice points from the biggest to the smallest subset.

Answer 3

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

Can be golfed a fair bit, I'm sure. But basically the same algorithm as in Fatalize's Brachylog answer, with a slightly different test at the end.

Answer 4

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

Try it online! New approach turned out to be both shorter and more efficient. Instead of all possible permutations only all valid chains are build.

Edit: The 117 byte version is much slower again, but still faster than the brute-force.

---

Old brute-force method:

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

This is a brute-force implementation which tries all possible permutations (The number of possible permutations seems to be given by A000165, the "double factorial of even numbers"). Try it online barely manages inputs up to length 7 (which is kind of impressive as 7 corresponds to 645120 permutations).

Usage:

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

Answer 5

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 is the last value, or undefined for the initial invocation. l-n is therefore a falsy value if the domino can be played.
• d is the domino under consideration.
• n is the end of the domino under consideration for chaining to the previous domino. The other end may readily be calculated as d[0]+d[1]-n.
• 0, simply handles the base case of no playable dominoes.

Answer 6

Python 2, 279 bytes

Golfed:

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

Try it online!

Same thing with some comments:

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

I'm posting because I didn't see any python answers...someone will see my answer and, in disgust, be forced to post something much shorter and efficient.

Answer 7

Clojure, 198 183 bytes

Update: Better handling of "maximum of possibly empty sequence"

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

Earlier version:

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

Calling convention and test cases:

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

F returns elements of list C without the element a, M returns the max of input ingerers or 1.

L is the main function, when called with a single argument it generates all possible starting pieces and finds the max length for each of them. When called with two arguments the l is the first element of the sequence to which the next piece must match and R is rest of the pieces.

Generating permutations and "choose one element and split to rest" were quite tricky to implement succinctly.