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ę n
połą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 1
z 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)
code-golf
combinatorics
path-finding
dominoes
shooqie
źródło
źródło
O(n!)
jak chceszI guess it's P
Odpowiedzi:
Brachylog , 23 bajty
Wypróbuj online!
Wyjaśnienie
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~c
i:{…l2}a
skutecznie 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
:pa
również nie powiedzie,a
nie lubi pustych list), więc potrzebny jest specjalny przypadek na 0. (jeden duży powodu mamy asymetrię pomiędzyb
i~k
jest tak że nie potrzebujemy również specjalnego przypadku dla 1.)źródło
Brachylog , 29 bajtów
Wypróbuj online!
Jestem pewien, że jest to okropnie długie, ale cokolwiek. Jest to również bardzo powolne.
Wyjaśnienie
Powodem, dla którego znajdzie największy, jest to, że
s - subset
generuje punkty wyboru od największego do najmniejszego podzbioru.źródło
Mathematica, 191 bajtów
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.
źródło
Differences/@Rest@Flatten@#~Partition~2
zamiastDifferences/@Partition[Rest@Flatten@#,2]
(Infix
ma wyższy priorytet niżMap
)JavaScript (Firefox 30-57), 92 bajty
l
jest ostatnią wartością lubundefined
dla pierwszego wywołania.l-n
jest zatem wartością falsy, jeśli można grać w domino.d
jest rozważanym domino.n
jest końcem rozważanego domina do połączenia z poprzednim domino. Drugi koniec można łatwo obliczyć jakod[0]+d[1]-n
.0,
po prostu obsługuje podstawowy przypadek braku grywalnych domino.źródło
Haskell ,
180 134131117 bajtówWypró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:
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:
źródło
Python 2, 279 bajtów
Gra w golfa:
Wypróbuj online!
To samo z niektórymi komentarzami:
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.
źródło
Clojure,
198183 bajtówAktualizacja: Lepsza obsługa „maksymalnej możliwej pustej sekwencji”
Wcześniejsza wersja:
Konwencja wywoływania i przypadki testowe:
F
zwraca elementy listyC
bez elementua
,M
zwraca maksymalną liczbę wejściowych argumentów lub 1.L
to 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 argumentamil
jest to pierwszy element sekwencji, do którego musi pasować następny element iR
jest on resztą elementów.Generowanie permutacji i „wybierz jeden element i podziel na odpoczynek” było dość trudne do zwięzłego wdrożenia.
źródło