Магическая пирамида
Существует множество вариаций знаменитой головоломки Кубик Рубика. Одна из них, называемая Магическая Пирамида, основана на тетраэдре вместо куба. Грани тетраэдра обозначены латинскими буквами X, U, V и W. Каждая грань разделена на 9 равносторонних треугольников, пронумерованных от 1 до 36, как показано на Рисунке 1. Чтобы собрать тетраэдр, необходимо сложить большой треугольник вниз вдоль внутренних толстых линий и склеить совпадающие половины внешних толстых линий.
Каждый из маленьких треугольников окрашен в один из четырех различных цветов, которые обозначены латинскими буквами a, b, c и d. Точно 9 треугольников каждого из четырех цветов.
Мы можем трансформировать тетраэдр, используя операцию «поворот грани». Для этого выбираем грань пирамиды и ориентируем пирамиду так, чтобы выбранная грань была обращена к нам. Затем определяем направление вращения (по часовой стрелке или против часовой стрелки). Наконец, поворачиваем часть тетраэдра, ближайшую к выбранной грани и имеющую толщину 1/3 высоты тетраэдра, на 120 градусов в выбранном направлении, оставляя остальную часть тетраэдра неподвижной. Рисунок 2 иллюстрирует эффект вращения грани U по часовой стрелке.
Кроме вращения граней, мы также можем применить операцию «магическая перекраска». Эта операция определяется перестановкой (p_1, …, p_36) целых чисел от 1 до 36. Эффект операции заключается в том, что треугольник, находящийся в позиции i (согласно нумерации, данной на Рисунке 1), перекрашивается в цвет треугольника, находящегося в позиции p_{i} (согласно той же нумерации). Все 36 треугольников перекрашиваются одновременно.
Головоломка решена, если после применения ряда операций «поворот грани» и/или «магическая перекраска» все треугольники на каждой грани тетраэдра имеют один и тот же цвет.
Напишите программу для решения головоломки Магическая Пирамида, используя минимально возможное количество ходов. Вы можете предположить, что все тестовые случаи решаемы за 9 или менее ходов.
Входные данные
Первая строка файла содержит 36 букв 'a'…'d'. Буква на позиции i обозначает начальный цвет треугольника номер i. Известно, что каждая из четырех букв встречается ровно 9 раз в первой строке файла.
Вторая строка файла содержит 36 различных целых чисел от 1…36, которые описывают операцию "магическая перекраска". i-е целое число в этой строке является элементом p_i перестановки, определяющей операцию.
Выходные данные
Первая и единственная строка файла должна содержать строку символов 'X', 'U', 'V', 'W', 'x', 'u', 'v', 'w' и '*'. i-й символ должен описывать i-й ход в решении головоломки. Каждая операция "поворот грани" обозначается меткой соответствующей грани, при этом строчная буква обозначает поворот по часовой стрелке, а заглавная буква — против часовой стрелки. Операция "магическая перекраска" обозначается символом '*'.
Если существует несколько решений с минимальным количеством ходов, выведите любое из них. Если головоломка может быть решена без ходов, выведите пустую строку в файл.