Introducción
En Toyland, los trenes siempre están ocupados entregando tesoros por toda la ciudad, desde canicas brillantes hasta bloques de construcción poco comunes.
Las vías por las que circulan están hechas de piezas coloridas con forma de dominó, cada una marcada con dos números.
Para que los trenes avancen, las fichas de dominó deben formar una cadena perfecta en la que los números coincidan.
Hoy, una entrega urgente de juguetes raros está detenida.
Te han entregado un conjunto de piezas de vía para que las revises.
Si logran formar una cadena continua, el tren seguirá su camino y llevará sonrisas por todo Toyland.
Si no, el conjunto se descartará y se probará con otro.
Los juguetes cuentan contigo para resolver este rompecabezas.
¿Lograrán las fichas de dominó conectar las vías y poner el tren en marcha, o el conjunto quedará abandonado?
Instrucciones
Arma una cadena de dominó.
Calcula una forma de ordenar un conjunto dado de fichas de dominó para que formen una cadena de dominó correcta.
En la cadena, los puntos de una mitad de una ficha deben coincidir con los puntos de la mitad vecina de una ficha adyacente.
Además, los puntos de las mitades de las fichas que no tienen vecinos (la primera y la última ficha) deben coincidir entre sí.
Por ejemplo, dadas las fichas [2|1], [2|3] y [1|3], debes calcular algo
como [1|2] [2|3] [3|1] o [3|2] [2|1] [1|3] o [1|3] [3|2] [2|1], etc., donde el primer y el último número son iguales.
Para las fichas [1|2], [4|1] y [2|3] la cadena resultante no es válida: el primer y el último número de [4|1] [1|2] [2|3] no son iguales.
4 != 3
Es posible que algunos casos de prueba usen fichas duplicadas en la solución de una cadena; asume que se están usando varios juegos de dominó.
Implementación
Define una sola función de Go, MakeChain, que recibe un slice de fichas de dominó e intenta construir una cadena legal de fichas de dominó.
MakeChain debe tener la siguiente firma:
type Domino [2]int
func MakeChain(input []Domino) (chain []Domino, ok bool)
El resultado ok de tipo bool indica si la lista de fichas de dominó de entrada se puede ordenar en una cadena legal.
Una lista de entrada vacía se considera legal, y una sola ficha de dominó cuyos lados son iguales también se considera legal.
El resultado 'chain' es un slice de cero o más fichas de dominó ordenadas de una forma que muestra la cadena legal.
Es aceptable (y se espera) que las fichas de dominó de 'input' tengan que rotarse para que cada lado coincida con la ficha de dominó adyacente en la cadena.
Las fichas de dominó al inicio y al final de la cadena también deben coincidir por su lado exterior.
Si el slice de fichas de dominó de entrada no se puede ordenar en una cadena legal,
MakeChain puede devolver nil como resultado de la cadena, pero debe devolver false para el resultado ok.
Como puede haber más de una forma legal de ordenar una lista de entrada dada, cuando ok es true, el programa de pruebas solo verificará la validez de la cadena.
