Einführung
In Toyland sind die Züge ständig damit beschäftigt, Schätze quer durch die Stadt zu liefern, von glänzenden Murmeln bis hin zu seltenen Bausteinen.
Die Schienen, auf denen sie fahren, bestehen aus bunten Teilen in Dominoform, und jedes davon trägt zwei Zahlen.
Damit sich die Züge bewegen können, müssen die Dominosteine eine perfekte Kette bilden, bei der die Zahlen zueinander passen.
Heute wartet eine dringende Lieferung seltener Spielzeuge.
Du hast eine Reihe von Schienenteilen bekommen, die du prüfen sollst.
Wenn sie eine durchgehende Kette bilden können, kann der Zug losfahren und Lächeln durch ganz Toyland bringen.
Wenn nicht, wird das Set verworfen und ein anderes ausprobiert.
Die Spielzeuge zählen auf dich, um dieses Rätsel zu lösen.
Werden die Dominosteine die Schienen verbinden und den Zug ins Rollen bringen, oder bleibt das Set zurück?
Anleitung
Bilde eine Kette aus Dominosteinen.
Finde eine Reihenfolge für eine gegebene Menge von Dominosteinen, sodass sie eine gültige Dominokette bilden.
In der Kette müssen die Punkte auf der einen Hälfte eines Steins zu den Punkten auf der angrenzenden Hälfte eines benachbarten Steins passen.
Außerdem müssen die Punkte auf den Hälften der Steine ohne Nachbarn (der erste und der letzte Stein) zueinander passen.
Zum Beispiel solltest du für die Steine [2|1], [2|3] und [1|3] etwas wie [1|2] [2|3] [3|1] oder [3|2] [2|1] [1|3] oder [1|3] [3|2] [2|1] usw. finden, wobei die erste und die letzte Zahl gleich sind.
Für die Steine [1|2], [4|1] und [2|3] ist die resultierende Kette nicht gültig: Die erste und die letzte Zahl von [4|1] [1|2] [2|3] sind nicht gleich.
4 != 3
Einige Testfälle verwenden möglicherweise doppelte Steine in einer Kettenlösung; geh davon aus, dass mehrere Dominosets verwendet werden.
Implementierung
Definiere eine einzelne Go-Funktion, MakeChain, die ein Slice von Dominosteinen entgegennimmt und versucht, daraus eine gültige Kette von Dominosteinen zu bilden.
MakeChain sollte die folgende Signatur haben:
type Domino [2]int
func MakeChain(input []Domino) (chain []Domino, ok bool)
Das boolesche Ergebnis ok zeigt an, ob sich die gegebene Eingabeliste von Dominosteinen zu einer gültigen Kette anordnen lässt.
Eine leere Eingabeliste gilt als gültig, und ein einzelner Dominostein, dessen beide Seiten gleich sind, gilt ebenfalls als gültig.
Das Ergebnis 'chain' ist ein Slice aus null oder mehr Dominosteinen, die in einer Reihenfolge angeordnet sind, die die gültige Kette zeigt.
Es ist in Ordnung (und wird erwartet), dass Dominosteine in 'input' gedreht werden müssen, damit jede Seite zu ihrem benachbarten Dominostein in der Kette passt.
Auch die Dominosteine am Anfang und am Ende der Kette müssen mit ihrer Außenseite übereinstimmen.
Lässt sich das gegebene Eingabe-Slice von Dominosteinen nicht zu einer gültigen Kette anordnen,
darf MakeChain für das Ergebnis 'chain' nil zurückgeben, muss aber für das Ergebnis ok falsch zurückgeben.
Da es für eine gegebene Eingabeliste mehr als eine gültige Kettenanordnung geben kann, prüft das Testprogramm die Kette nur dann auf Gültigkeit, wenn ok wahr ist.
