Introduzione
A Toyland, i treni sono sempre indaffarati a consegnare tesori in tutta la città, dalle biglie luccicanti ai rari mattoncini da costruzione.
I binari su cui viaggiano sono fatti di colorati pezzi a forma di domino, ognuno contrassegnato da due numeri.
Perché i treni possano muoversi, i domino devono formare una catena perfetta in cui i numeri corrispondono.
Oggi una consegna urgente di giocattoli rari è in sospeso.
Hai ricevuto un set di pezzi di binario da ispezionare.
Se riescono a formare una catena continua, il treno si metterà in viaggio, portando sorrisi in tutto il Toyland.
In caso contrario, il set sarà scartato e se ne proverà un altro.
I giocattoli contano su di te per risolvere questo puzzle.
I domino collegheranno i binari e faranno partire il treno, o il set resterà indietro?
Istruzioni
Crea una catena di domino.
Calcola un modo per ordinare un dato insieme di tessere del domino in modo che formino una catena di domino corretta.
Nella catena, i punti su una metà di una tessera devono corrispondere ai punti sulla metà adiacente di una tessera vicina.
Inoltre, i punti sulle metà delle tessere senza vicini (la prima e l'ultima tessera) devono corrispondere tra loro.
Ad esempio, date le tessere [2|1], [2|3] e [1|3] dovresti calcolare qualcosa
come [1|2] [2|3] [3|1] o [3|2] [2|1] [1|3] o [1|3] [3|2] [2|1] ecc., dove il primo e l'ultimo numero sono uguali.
Per le tessere [1|2], [4|1] e [2|3] la catena risultante non è valida: il primo e l'ultimo numero di [4|1] [1|2] [2|3] non sono uguali.
4 != 3
Alcuni casi di test possono usare tessere duplicate in una soluzione della catena, presupponi che vengano usati più set di domino.
Implementazione
Definisci una singola funzione Go, MakeChain, che accetta una slice di domino e cerca di costruire una catena valida di domino.
MakeChain deve avere la seguente firma:
type Domino [2]int
func MakeChain(input []Domino) (chain []Domino, ok bool)
Il risultato ok di tipo bool indica se la lista di domino fornita in input può essere disposta in una catena valida.
Una lista di input vuota è considerata valida, e anche un singolo domino con i lati uguali è considerato valido.
Il risultato «chain» è una slice di zero o più domino disposti in un ordine che mostra la catena valida.
È accettabile (e previsto) che i domino in «input» possano dover essere ruotati affinché ogni lato corrisponda al domino adiacente nella catena.
Anche i domino all'inizio e alla fine della catena devono corrispondere al loro lato esterno.
Se la slice di domino fornita in input non può essere disposta in una catena valida
MakeChain può restituire nil per il risultato «chain», ma deve restituire false per il risultato ok.
Poiché possono esserci più di una disposizione valida della catena per una data lista di input, quando ok è true, il programma di test controllerà solo la validità della catena.
