Вступ
У Тойленді потяги завжди зайняті: вони розвозять скарби по всьому місту, від блискучих кульок до рідкісних будівельних кубиків.
Колії, якими вони їздять, зроблені з різнобарвних деталей у формі доміно, і на кожній позначено два числа.
Щоб потяги рухалися, доміно мають утворити бездоганний ланцюжок, у якому числа збігаються.
Сьогодні термінова доставка рідкісних іграшок призупинена.
Нам передали набір деталей колії для огляду.
Якщо з них удасться скласти безперервний ланцюжок, потяг вирушить у дорогу й подарує усмішки всьому Тойленду.
Якщо ж ні, набір відкладуть, а натомість спробують інший.
Іграшки сподіваються, що саме ми розгадаємо цю головоломку.
Чи зʼєднають доміно колії й змусять потяг рушити, чи цей набір залишиться позаду?
Вказівки
Складіть ланцюг із доміно.
Обчисліть спосіб упорядкувати заданий набір кісточок доміно так, щоб вони утворили правильний ланцюг доміно.
У ланцюгу крапки на одній половині кісточки мають збігатися з крапками на сусідній половині суміжної кісточки.
Крім того, крапки на половинах кісточок без сусідів (першої та останньої кісточки) мають збігатися між собою.
Наприклад, для кісточок [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 під назвою MakeChain, яка приймає зріз доміно та намагається побудувати допустимий ланцюжок доміно.
Функція MakeChain повинна мати таку сигнатуру:
type Domino [2]int
func MakeChain(input []Domino) (chain []Domino, ok bool)
Результат ok типу bool показує, чи можна наданий вхідний список доміно впорядкувати в допустимий ланцюжок.
Порожній вхідний список вважається допустимим, і одне доміно, сторони якого однакові, також вважається допустимим.
Результат «chain» - це зріз, що містить нуль або більше доміно, упорядкованих у послідовність, яка показує допустимий ланцюжок.
Прийнятно (і очікувано), що доміно в «input» можуть потребувати обертання, щоб кожна сторона збігалася із сусіднім доміно в ланцюжку.
Доміно на початку й у кінці ланцюжка також мають збігатися зовнішніми сторонами.
Якщо наданий вхідний зріз доміно не можна впорядкувати в допустимий ланцюжок, MakeChain може повернути nil для результату «chain», але має повернути false для результату «ok».
Оскільки для наданого вхідного списку може існувати більше одного допустимого варіанта ланцюжка, коли ok дорівнює true, тестова програма перевірятиме ланцюжок лише на коректність.
