Herausforderungsbeschreibung
Dominoes ist ein Spiel, bei dem Kacheln mit zwei Werten gespielt werden - einer auf der linken Seite, einer auf der rechten Seite, zum Beispiel [2|4]
oder [4|5]
. Zwei Kacheln können zusammengefügt werden, wenn sie einen gemeinsamen Wert enthalten. Die beiden obigen Kacheln können wie folgt verbunden werden:
[2|4][4|5]
Wir bezeichnen eine Folge n
verbundener Kacheln als Kette der Länge n. Natürlich können Kacheln gedreht, also Kacheln [1|2]
, [1|3]
und [5|3]
zu einer Kette [2|1][1|3][3|5]
der Länge 3 umgeordnet werden .
Bestimmen Sie anhand einer Liste von Ganzzahlpaaren die Länge der längsten Kette, die mit diesen Kacheln gebildet werden kann. Wenn die Liste leer ist, lautet die richtige Antwort 0
(beachten Sie, dass Sie 1
aus einer nicht leeren Liste von Kacheln immer eine Längenkette bilden können ).
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)
quelle
O(n!)
I guess it's P
Antworten:
Brachylog , 23 Bytes
Probieren Sie es online!
Erläuterung
Mit anderen Worten, für Eingaben wie
[[1:2]:[1:3]:[5:3]]
versuchen wir, es in eine gültige Kette[[2:1]:[1:3]:[3:5]]
umzuordnen und dann zu produzieren[1:1:3:3:5:_]
(wobei_
ein Unbekannter dargestellt wird). Durch die Kombination~c
und:{…l2}a
effektive Aufteilung in Gruppen von 2 Elementen wird sichergestellt, dass alle Gruppen gleich sind. Wenn wir die Länge reduzieren (verdoppeln), ein Element vom Anfang entfernen und eines am Ende hinzufügen (keine Änderung) und in Paare gruppieren (die Länge halbieren), hat dies die gleiche Länge wie die ursprüngliche Dominokette.Die „enthauptet“ Anweisung wird scheitern , wenn es keine Dominosteine im Eingang sind (eigentlich IIRC die
:pa
auch fehlschlagen,a
Abneigungen leere Listen), so dass wir einen Sonderfall für 0. (Ein wichtigen Grund brauchen wir haben die Asymmetrie zwischenb
und~k
so ist dass wir für 1.) auch keinen Sonderfall brauchenquelle
Brachylog , 29 Bytes
Probieren Sie es online!
Ich bin mir ziemlich sicher, dass das furchtbar lang ist, aber was auch immer. Das ist auch furchtbar langsam.
Erläuterung
Der Grund, warum dies die größte findet, liegt darin, dass
s - subset
Auswahlpunkte von der größten bis zur kleinsten Teilmenge generiert werden.quelle
Mathematica, 191 Bytes
Kann ein gutes Stück Golf spielen, da bin ich mir sicher. Aber im Grunde derselbe Algorithmus wie in Fatalizes Brachylog-Antwort , mit einem etwas anderen Test am Ende.
quelle
Differences/@Rest@Flatten@#~Partition~2
Differences/@Partition[Rest@Flatten@#,2]
Infix
Map
JavaScript (Firefox 30-57), 92 Byte
l
ist der letzte Wert oderundefined
für den ersten Aufruf.l-n
ist daher ein falscher Wert, wenn das Domino gespielt werden kann.d
ist der zu betrachtende Domino.n
ist das Ende des Dominos, das für die Verkettung mit dem vorherigen Domino in Betracht gezogen wird. Das andere Ende kann leicht berechnet werden alsd[0]+d[1]-n
.0,
behandelt einfach den Basisfall ohne spielbare Dominosteine.quelle
Haskell ,
180 134131117 BytesProbieren Sie es online! Der neue Ansatz erwies sich als kürzer und effizienter. Anstelle aller möglichen Permutationen werden nur alle gültigen Ketten erstellt.
Bearbeiten: Die 117-Byte-Version ist wieder viel langsamer, aber immer noch schneller als die Brute-Force.
Alte Brute-Force-Methode:
Dies ist eine Brute-Force-Implementierung, bei der alle möglichen Permutationen ausprobiert werden (Die Anzahl der möglichen Permutationen scheint in A000165 , der " doppelten Fakultät von geraden Zahlen ", angegeben zu sein). Online ausprobieren verwaltet kaum Eingaben bis zu einer Länge von 7 (was beeindruckend ist, da 7 645120 Permutationen entspricht).
Verwendung:
quelle
Python 2, 279 Bytes
Golf gespielt:
Probieren Sie es online!
Gleiches mit einigen Kommentaren:
Ich poste, weil ich keine Python-Antworten gesehen habe ... jemand wird meine Antwort sehen und, angewidert, gezwungen sein, etwas viel Kürzeres und Effizienteres zu posten.
quelle
Clojure,
198183 BytesUpdate: Besserer Umgang mit "Maximum an möglicherweise leerer Sequenz"
Frühere Version:
Aufruf von Konventionen und Testfällen:
F
gibt Elemente der ListeC
ohne das Element zurücka
,M
gibt die maximale Anzahl von Eingaben ingerers oder 1 zurück.L
ist die Hauptfunktion, wenn sie mit einem einzigen Argument aufgerufen wird, werden alle möglichen Startstücke generiert und die maximale Länge für jedes von ihnen ermittelt. Bei einem Aufruf mit zwei Argumentenl
ist das das erste Element der Sequenz, zu dem das nächste Stück passen muss, und derR
Rest der Stücke.Das Generieren von Permutationen und das "Auswählen eines Elements und Aufteilen zum Ausruhen" war recht schwierig, um es kurz und bündig umzusetzen.
quelle