Introdução
Em Toyland, os trens estão sempre ocupados entregando tesouros pela cidade, de bolinhas de gude brilhantes a blocos de montar raros.
Os trilhos por onde eles passam são feitos de peças coloridas em forma de dominó, cada uma marcada com dois números.
Para que os trens se movam, as peças de dominó precisam formar uma corrente perfeita, em que os números combinem.
Hoje, uma entrega urgente de brinquedos raros está parada.
Você recebeu um conjunto de peças de trilho para inspecionar.
Se elas conseguirem formar uma corrente contínua, o trem seguirá viagem, levando sorrisos por toda a Toyland.
Se não conseguirem, o conjunto será descartado e outro será testado.
Os brinquedos contam com você para resolver este quebra-cabeça.
Será que as peças de dominó vão conectar os trilhos e fazer o trem partir, ou o conjunto vai ficar para trás?
Instruções
Monte uma corrente de dominós.
Calcule uma forma de ordenar um conjunto de pedras de dominó para que elas formem uma corrente de dominó válida.
Na corrente, os pontos de uma metade de uma pedra devem corresponder aos pontos da metade vizinha de uma pedra adjacente.
Além disso, os pontos das metades das pedras sem vizinhas (a primeira e a última pedra) devem corresponder entre si.
Por exemplo, dadas as pedras [2|1], [2|3] e [1|3], você deve calcular algo
como [1|2] [2|3] [3|1] ou [3|2] [2|1] [1|3] ou [1|3] [3|2] [2|1] etc., em que o primeiro e o último número são iguais.
Para as pedras [1|2], [4|1] e [2|3], a corrente resultante não é válida: o primeiro e o último número de [4|1] [1|2] [2|3] não são iguais.
4 != 3
Alguns casos de teste podem usar pedras duplicadas em uma solução de corrente; considere que vários conjuntos de dominó estão sendo usados.
Implementação
Defina uma única func do Go, MakeChain, que aceita uma slice de dominós e tenta construir uma cadeia válida de dominós.
MakeChain deve ter a seguinte assinatura:
type Domino [2]int
func MakeChain(input []Domino) (chain []Domino, ok bool)
O resultado bool ok indica se a lista de dominós de entrada pode ser organizada em uma cadeia válida.
Uma lista de entrada vazia é considerada válida, e um único dominó cujos lados são iguais também é considerado válido.
O resultado 'chain' é uma slice de zero ou mais dominós organizados em uma ordem que mostra a cadeia válida.
É aceitável (e esperado) que os dominós em 'input' precisem ser rotacionados para que cada lado corresponda ao dominó adjacente na cadeia.
Os dominós no início e no fim da cadeia também devem corresponder ao seu lado externo.
Se a slice de dominós de entrada não puder ser organizada em uma cadeia válida,
MakeChain pode retornar nil para o resultado da cadeia, mas deve retornar false para o resultado ok.
Como pode haver mais de uma cadeia válida para uma determinada lista de entrada, quando ok for true, o programa de teste verificará apenas a validade da cadeia.
