Introducción
En Toyland, los trenes siempre están ocupados repartiendo tesoros por toda la ciudad, desde canicas relucientes hasta bloques de construcción poco comunes.
Las vías por las que circulan están hechas de coloridas piezas en 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 coincidan los números.
Hoy, una entrega urgente de juguetes poco comunes está en espera.
Te han dado un conjunto de piezas de vía para que las inspecciones.
Si pueden formar una cadena continua, el tren se pondrá en marcha y llevará sonrisas por todo Toyland.
Si no, el conjunto se descartará y se probará con otro.
Los juguetes cuentan contigo para resolver este puzle.
¿Conectarán las fichas de dominó las vías y pondrán el tren en marcha, o se quedará el conjunto atrás?
Instrucciones
Crea 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 sin vecinas (la primera y la última ficha) deben coincidir entre sí.
Por ejemplo, dadas las fichas [2|1], [2|3] y [1|3], deberías 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
Algunos casos de prueba pueden usar fichas duplicadas en la solución de una cadena; supón que se están usando varios conjuntos de dominó.
Implementación
Define una única función de Go, MakeChain, que acepta un slice de fichas de dominó e intenta construir una cadena válida 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 dada se puede disponer en una cadena válida.
Una lista de entrada vacía se considera válida, y una única ficha de dominó cuyos lados son iguales también se considera válida.
El resultado «chain» es un slice de cero o más fichas de dominó dispuestas en un orden que muestra la cadena válida.
Es aceptable (y de esperar) que las fichas de dominó de «input» tengan que rotarse para que cada lado coincida con la ficha adyacente de la cadena.
Las fichas de dominó al principio y al final de la cadena también deben coincidir entre sí por el lado exterior.
Si el slice de fichas de dominó de entrada dado no se puede disponer en una cadena válida,
MakeChain puede devolver nil como resultado de chain, pero debe devolver false como resultado de ok.
Como puede haber más de una cadena válida posible para una lista de entrada dada, cuando ok es true, el programa de prueba solo comprobará que la cadena sea válida.
