Opis wyzwania

Domino to gra z kafelkami z dwiema wartościami - jedną po lewej, drugą po prawej, na przykład [2|4]lub [4|5]. Dwa kafelki można połączyć, jeśli zawierają wspólną wartość. Dwie powyższe płytki można połączyć w następujący sposób:

[2|4][4|5]

Nazwiemy sekwencję npołączonych płytek łańcuchem o długości n. Oczywiście płytki mogą się obracać, tak płytek [1|2], [1|3]i [5|3]mogą zostać zmienione do łańcucha [2|1][1|3][3|5]o długości 3.

Biorąc pod uwagę listę par liczb całkowitych, określ długość najdłuższego łańcucha, który można utworzyć za pomocą tych płytek. Jeśli lista jest pusta, poprawną odpowiedzią jest 0(pamiętaj, że zawsze możesz utworzyć łańcuch długości 1z niepustej listy płytek).

Przykładowe wejście / wyjście

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

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

Wypróbuj online!

Wyjaśnienie

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.

Innymi słowy, w przypadku danych wejściowych [[1:2]:[1:3]:[5:3]]próbujemy zmienić układ w prawidłowy łańcuch [[2:1]:[1:3]:[3:5]], a następnie spłaszczyć / ściąć głowę / unkknife, aby wytworzyć [1:1:3:3:5:_](gdzie _reprezentuje nieznane). Połączenie ~ci :{…l2}askutecznie dzieli to na grupy 2 elementów, a my zapewniamy, że wszystkie grupy są równe. Gdy spłaszczymy (podwojenie długości), usunęliśmy jeden element od początku i dodaliśmy jeden na końcu (bez zmian) i pogrupowaliśmy w pary (zmniejszenie długości o połowę), będzie on miał taką samą długość jak oryginalny łańcuch domina.

W „ściąć” instrukcja nie powiedzie się, jeśli nie ma w domino wejścia (faktycznie, IIRC :parównież nie powiedzie, anie lubi pustych list), więc potrzebny jest specjalny przypadek na 0. (jeden duży powodu mamy asymetrię pomiędzy bi ~kjest tak że nie potrzebujemy również specjalnego przypadku dla 1.)

Brachylog , 29 bajtów

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

Wypróbuj online!

Jestem pewien, że jest to okropnie długie, ale cokolwiek. Jest to również bardzo powolne.

Wyjaśnienie

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)

Powodem, dla którego znajdzie największy, jest to, że s - subsetgeneruje punkty wyboru od największego do najmniejszego podzbioru.

Mathematica, 191 bajtów

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

Jestem pewien, że można w nią grać w golfa. Ale w zasadzie ten sam algorytm jak w odpowiedzi Brachylog Fatalize , z nieco innym testem na końcu.

JavaScript (Firefox 30-57), 92 bajty

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

• ljest ostatnią wartością lub undefineddla pierwszego wywołania. l-njest zatem wartością falsy, jeśli można grać w domino.
• d jest rozważanym domino.
• njest końcem rozważanego domina do połączenia z poprzednim domino. Drugi koniec można łatwo obliczyć jako d[0]+d[1]-n.
• 0, po prostu obsługuje podstawowy przypadek braku grywalnych domino.

Haskell , 180 134 131 117 bajtów

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

Wypróbuj online! Nowe podejście okazało się zarówno krótsze, jak i bardziej wydajne. Zamiast wszystkich możliwych permutacji budowane są tylko wszystkie prawidłowe łańcuchy.

Edycja: Wersja 117-bajtowa jest znowu znacznie wolniejsza, ale wciąż szybsza niż brutalna siła.

Stara metoda brutalnej siły:

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

Jest to implementacja brute-force, która wypróbowuje wszystkie możliwe permutacje (liczba możliwych permutacji wydaje się podawana przez A000165 , „ podwójną silnię liczb parzystych ”). Wypróbuj online, ledwo zarządza danymi wejściowymi o długości do 7 (co jest imponujące, ponieważ 7 odpowiada permutacjom 645120 ).

Stosowanie:

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

Python 2, 279 bajtów

Gra w golfa:

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

Wypróbuj online!

To samo z niektórymi komentarzami:

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

Publikuję, ponieważ nie widziałem żadnych odpowiedzi w Pythonie ... ktoś zobaczy moją odpowiedź i, z odrazą, będzie zmuszony opublikować coś znacznie krótszego i wydajniejszego.

Clojure, 198 183 bajtów

Aktualizacja: Lepsza obsługa „maksymalnej możliwej pustej sekwencji”

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

Wcześniejsza wersja:

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

Konwencja wywoływania i przypadki testowe:

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

Fzwraca elementy listy Cbez elementu a, Mzwraca maksymalną liczbę wejściowych argumentów lub 1.

Lto główna funkcja, wywołana jednym argumentem, generuje wszystkie możliwe elementy początkowe i określa maksymalną długość każdego z nich. Po wywołaniu z dwoma argumentami ljest to pierwszy element sekwencji, do którego musi pasować następny element i Rjest on resztą elementów.

Generowanie permutacji i „wybierz jeden element i podziel na odpoczynek” było dość trudne do zwięzłego wdrożenia.