はじめに
おもちゃの国では、汽車がいつも忙しく走り回り、街じゅうに宝物を届けています。ぴかぴかのビー玉から珍しい積み木まで、さまざまです。
汽車が走る線路は、カラフルなドミノ形のピースでできていて、それぞれに2つの数が書かれています。
汽車が動くためには、ドミノが数を合わせた完全な1本の鎖にならなければなりません。
今日は、珍しいおもちゃの緊急配送が止まったままです。
線路のピースが1組手渡され、点検することになりました。
途切れない鎖を作ることができれば、汽車は走り出し、おもちゃの国じゅうに笑顔を運びます。
できなければ、この1組は処分され、別の1組が試されます。
おもちゃたちが、このパズルを解くのを待っています。
ドミノは線路をつないで汽車を走らせることができるでしょうか。それとも、この1組は置き去りにされるのでしょうか。
説明
ドミノの連鎖を作りましょう。
与えられたドミノの石を、正しいドミノの連鎖になるように並べる順序を計算します。連鎖の中では、ある石の片側のドットが、隣り合う石の隣の側のドットと一致していなければなりません。さらに、隣り合う石がない側（最初と最後の石）のドット同士も一致していなければなりません。
たとえば、石[2|1]、[2|3]、[1|3]が与えられたときは、[1|2] [2|3] [3|1]や[3|2] [2|1] [1|3]、[1|3] [3|2] [2|1]などのように計算します。いずれも最初と最後の数値が同じです。
石[1|2]、[4|1]、[2|3]の場合、できあがる連鎖は有効ではありません。[4|1] [1|2] [2|3]の最初と最後の数値が同じではないからです。
4 != 3
テストケースによっては、連鎖の解答で同じ石を重複して使うことがあります。複数のドミノセットが使われていると考えてください。
実装
Goの関数を1つ定義します。名前はMakeChainとし、ドミノのスライスを受け取って、正しいドミノの連鎖を組み立てようとします。
MakeChainのシグネチャは次のとおりです。
type Domino [2]int
func MakeChain(input []Domino) (chain []Domino, ok bool)
okの真偽値の結果は、与えられた入力のドミノのリストを正しい連鎖に並べられるかどうかを示します。
空の入力リストは正しいものとみなされ、両側が同じ1つのドミノも正しいものとみなされます。
'chain'の結果は、0個以上のドミノを正しい連鎖になる順に並べたスライスです。
'input'のドミノは、それぞれの側が連鎖の中で隣り合うドミノと一致するように回転させる必要がある場合があります。これは許容されますし、想定もされています。
連鎖の先頭と末尾のドミノは、それぞれ外側の側どうしも一致していなければなりません。
与えられたドミノの入力スライスを正しい連鎖に並べられない場合、MakeChainはchainの結果としてnilを返してもかまいませんが、okの結果としてはfalseを返さなければなりません。
与えられた入力リストに対して正しい連鎖の並べ方が複数あり得るため、okがtrueのときは、テストプログラムは連鎖が正しいかどうかだけを確認します。
