Introduction
À Toyland, les trains sont toujours occupés à livrer des trésors à travers la ville, des billes brillantes aux rares blocs de construction.
Les voies sur lesquelles ils circulent sont faites de pièces colorées en forme de dominos, chacune marquée de deux nombres.
Pour que les trains avancent, les dominos doivent former une chaîne parfaite où les nombres correspondent.
Aujourd'hui, une livraison urgente de jouets rares est en attente.
On t'a confié un ensemble de pièces de voie à inspecter.
Si elles peuvent former une chaîne continue, le train se mettra en route, apportant des sourires dans tout Toyland.
Sinon, l'ensemble sera mis au rebut et on en essaiera un autre.
Les jouets comptent sur toi pour résoudre ce casse-tête.
Les dominos parviendront-ils à relier les voies et à faire rouler le train, ou l'ensemble sera-t-il laissé de côté ?
Instructions
Crée une chaîne de dominos.
Calcule une façon d'ordonner un ensemble donné de dominos pour qu'ils forment une chaîne de dominos correcte.
Dans la chaîne, les points d'une moitié d'un domino doivent correspondre aux points de la moitié voisine d'un domino adjacent.
De plus, les points des moitiés des dominos sans voisin (le premier et le dernier domino) doivent correspondre entre eux.
Par exemple, avec les dominos [2|1], [2|3] et [1|3], tu devrais obtenir quelque chose comme [1|2] [2|3] [3|1] ou [3|2] [2|1] [1|3] ou [1|3] [3|2] [2|1] etc., où le premier et le dernier nombre sont identiques.
Pour les dominos [1|2], [4|1] et [2|3], la chaîne obtenue n'est pas valide : le premier et le dernier nombre de [4|1] [1|2] [2|3] ne sont pas identiques.
4 != 3
Certains cas de test peuvent utiliser des dominos en double dans une solution de chaîne ; considère que plusieurs jeux de dominos sont utilisés.
Implémentation
Définis une seule fonction Go, MakeChain, qui prend une slice de dominos et tente de construire une chaîne valide de dominos.
MakeChain doit avoir la signature suivante :
type Domino [2]int
func MakeChain(input []Domino) (chain []Domino, ok bool)
Le résultat booléen ok indique si la liste de dominos fournie en entrée a pu être disposée en une chaîne valide.
Une liste d'entrée vide est considérée comme valide, et un domino dont les deux côtés sont identiques l'est aussi.
Le résultat « chain » est une slice contenant zéro ou plusieurs dominos, disposés dans un ordre qui forme la chaîne valide.
Il est normal (et attendu) de devoir retourner les dominos de « input » afin que chaque côté corresponde à celui du domino adjacent dans la chaîne.
Les dominos situés au début et à la fin de la chaîne doivent eux aussi correspondre par leur côté extérieur.
Si la slice de dominos fournie en entrée ne peut pas être disposée en une chaîne valide, MakeChain peut renvoyer nil pour le résultat « chain », mais doit renvoyer false pour le résultat ok.
Comme il peut y avoir plusieurs dispositions valides possibles pour une même liste d'entrée, lorsque ok vaut true, le programme de test ne vérifie que la validité de la chaîne.
