Introdução
Em Toyland, os comboios andam sempre ocupados a entregar tesouros por toda a cidade, desde berlindes brilhantes a blocos de construção raros.
Os carris por onde circulam são feitos de peças coloridas em forma de dominó, cada uma marcada com dois números.
Para que os comboios se movam, os dominós têm de formar uma cadeia perfeita em que os números coincidem.
Hoje, uma entrega urgente de brinquedos raros está em espera.
Deram-te um conjunto de peças de carril para inspecionares.
Se conseguirem formar uma cadeia contínua, o comboio segue viagem, levando sorrisos por toda a Toyland.
Caso contrário, o conjunto é descartado e tenta-se outro.
Os brinquedos contam contigo para resolveres este puzzle.
Será que os dominós vão ligar os carris e pôr o comboio a andar, ou será que o conjunto fica para trás?
Instruções
Constrói uma cadeia de dominós.
Calcula uma forma de ordenar um conjunto de pedras de dominó para que formem uma cadeia de dominós válida. Na cadeia, os pontos de uma metade de uma pedra têm de corresponder aos pontos da metade vizinha de uma pedra adjacente. Além disso, os pontos das metades das pedras sem vizinhos (a primeira e a última pedra) têm de corresponder entre si.
Por exemplo, dadas as pedras [2|1], [2|3] e [1|3], deves 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 cadeia 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 numa solução de cadeia; assume que estão a ser usados vários conjuntos de dominós.
Implementação
Define uma única função Go, MakeChain, que aceita um slice de dominós e tenta construir uma cadeia válida de dominós.
A função MakeChain deve ter a seguinte assinatura:
type Domino [2]int
func MakeChain(input []Domino) (chain []Domino, ok bool)
O resultado ok, do tipo bool, indica se a lista de dominós fornecida pode ser disposta numa 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' é um slice de zero ou mais dominós dispostos numa ordem que mostra a cadeia válida.
É aceitável (e esperado) que os dominós em 'input' tenham de ser rodados para que cada lado corresponda ao dominó adjacente na cadeia.
Os dominós no início e no fim da cadeia também têm de fazer coincidir os respetivos lados exteriores.
Se o slice de dominós fornecido não puder ser disposto numa cadeia válida,
a função MakeChain pode devolver nil para o resultado 'chain', mas tem de devolver false para o resultado ok.
Como pode haver mais do que uma disposição válida da cadeia para uma dada lista de entrada, quando ok for verdadeiro, o programa de teste verifica apenas a validade da cadeia.
