Допустим, вы видели, как ваш друг вводил свой пароль в свой телефон Android. Вы не помните, как они создали шаблон, но вы помните, как выглядит шаблон. Будучи заинтересованным другом, которым вы являетесь, вы хотите знать, насколько безопасен их пароль. Ваша задача состоит в том, чтобы рассчитать все способы, которыми можно создать конкретный шаблон.

Как работают шаблоны Android

Шаблоны нарисованы на сетке 3х3 узлов. В схеме каждый посещает ряд узлов, даже не отрывая палец от экрана. Каждый узел, который они посещают, связан с предыдущим узлом ребром. Есть два правила, которые нужно иметь в виду.

• Вы не можете посещать какой-либо один узел более одного раза

• Ребро не может пройти через не посещенный узел

Обратите внимание, что, хотя обычно это очень трудно выполнить и, следовательно, не очень часто встречается в реальных комбинациях блокировки андроида, можно двигаться как рыцарь . То есть можно перемещаться с одной стороны в несмежный угол или наоборот. Вот два примера шаблонов, использующих такой шаг:

Вот анимированный GIF этого исполняемого.

Решение шаблона

Типичный шаблон может выглядеть примерно так:

С помощью простого шаблона, подобного этому, есть два способа нарисовать шаблон двумя способами. Вы можете начать с любого из двух свободных концов и проходить через выделенные узлы к другому. Хотя это верно для многих моделей, особенно тех, которые обычно используют люди, это не так для всех моделей.

Рассмотрим следующую схему:

Есть два сразу узнаваемых решения. Один начинается в верхнем левом углу:

И один начинается в нижнем центре:

Однако, поскольку линии разрешено проходить через точку после того, как она уже выбрана, в верхней средней части начинается дополнительный шаблон:

Этот конкретный шаблон имеет 3 решения , но образцы могут иметь где - нибудь между 1 и 4 решения ^{[править]} .

Вот несколько примеров каждого:

1.

2.

3.

4.

I / O

Узел может быть представлен как целые числа от нуля до девяти включительно, их строковые эквиваленты или символы от a до i (или от A до I). Каждый узел должен иметь уникальное представление из одного из этих наборов.

Решение будет представлено упорядоченным контейнером, содержащим представления узлов. Узлы должны быть упорядочены в том же порядке, в котором они пропущены.

Шаблон будет представлен неупорядоченным контейнером пар узлов. Каждая пара представляет ребро, начинающее соединять две точки в паре. Образцы представлений не являются уникальными.

Вы будете использовать представление шаблона в качестве входных данных с помощью стандартных методов ввода и выводить все возможные решения, которые создают один и тот же шаблон, с помощью стандартных методов вывода.

Можно предположить, что каждый вход будет иметь хотя бы одно решение и будет соединять как минимум 4 узла.

Вы можете использовать заказанный контейнер вместо неупорядоченного, если вы того пожелаете или вынуждены выбирать язык.

Тестовые случаи

С узлами, расположенными по следующей схеме:

0 1 2
3 4 5
6 7 8

Позвольте {...}быть неупорядоченным контейнером, [...]быть заказанным контейнером и (...)быть парой.

Следующие входы и выходы должны совпадать

{(1,4),(3,5),(5,8)} -> {[1,4,3,5,8]}
{(1,4),(3,4),(5,4),(8,5)} -> {[1,4,3,5,8]}
{(0,4),(4,5),(5,8),(7,8)} -> {[0,4,5,8,7],[7,8,5,4,0]}
{(0,2),(2,4),(4,7)} -> {[0,1,2,4,7],[1,0,2,4,7],[7,4,2,1,0]}
{(0,2),(2,6),(6,8)} -> {[0,1,2,4,6,7,8],[1,0,2,4,6,7,8],[8,7,6,4,2,1,0],[7,8,6,4,2,1,0]}
{(2,3),(3,7),(7,8)} -> {[2,3,7,8],[8,7,3,2]}
{(0,7),(1,2),(1,4),(2,7)} -> {[0,7,2,1,4],[4,1,2,7,0]}
{(0,4),(0,7),(1,3),(2,6),(2,8),(3,4),(5,7)} -> {[1,3,4,0,7,5,8,2,6]}
{(1,3),(5,8)} -> {}

Imgur альбом всех тестовых случаев в виде картинок можно найти здесь . Узоры в синих решениях в красном.

счет

Это код гольф. Побеждает несколько байтов.

Python 2,7, 493 430 байт

exec("L=['012','345','678','036','147','258','048','246'];L+=[i[::-1]IL];S=sorted;F=lambda t:''.join(str(i)It)\ndef N(x):\n s=' '.join(F(S(i))Ix)\nIL:s=s.replace(i[::2],i[:2]+' '+i[1:])\n return S(set(s.split()))\ndef P(s):\n e=0\nIL:e|=-1<s.find(i[::2])<s.find(i[1])\n return[zip(s[:-1],s[1:]),L][e]\nx=N(input());print[F(i)I__import__('itertools').permutations({iI`x`if i.isdigit()})if x==N(P(F(i)))]".replace('I',' for i in '))

Однострочная версия оборачивает программу exec("...".replace('I',' for i in '))так, что все циклы for и генераторы могут быть закорочены одним Iи экономит 15 байтов по сравнению с этой более читаемой версией:

L=['012','345','678','036','147','258','048','246'];L+=[i[::-1]for i in L]
S=sorted;F=lambda t:''.join(str(i)for i in t)
def N(x):
 s=' '.join(F(S(i))for i in x)
 for i in L:s=s.replace(i[::2],i[:2]+' '+i[1:])
 return S(set(s.split()))
def P(s):
 e=0
 for i in L:e|=-1<s.find(i[::2])<s.find(i[1])
 return[zip(s[:-1],s[1:]),L][e]
x=N(input())
print[F(i)for i in __import__('itertools').permutations({i for i in`x`if i.isdigit()})if x==N(P(F(i)))]

Программа принимает входные данные указанным способом (например {(1,4),(3,4),(5,4),(8,5)}) или в виде списка строк (например ['14','34','54','85']) (или в других дружественных для Python форматах) и возвращает выходные данные в виде списка строк. Таким образом, у нас технически есть заказанный контейнер заказанных контейнеров.

Функция Nнормализует шаблон, так что два шаблона можно легко сравнить. Нормализация сортирует пары, обозначающие ребра (поэтому '02'вместо '20'), использует замену строки для расширения двойных ребер (например, '02'становится '01 12'), разбивает ребра в набор для удаления дубликатов и сортирует результат.

Функция Fсглаживает кортежи из строк / строк в строки, поэтому мы можем нормализовать пути, созданные разными способами.

Список Lсодержит все строки на экране.

Затем мы берем каждую перестановку всех цифр в нормализованном шаблоне и вычисляем действительный путь или, Lесли он неверен (который никогда не нормализуется к списку пар, как это делают реальные пути), или список пар, указывающих, что узлы заказа посещены, если они действительны. Если это нормализуется к тому же шаблону, то мы имеем правильное решение и включаем его в окончательный список.

Основной проверкой, необходимой для проверки перестановки в виде строки, sявляется -1<s.find(i[::2])<s.find(i[1])обнаружение ошибки со строкой i. Например, со строкой '210'код обнаруживает ошибку, если '20'происходит (т. Е. Ее индекс больше -1), и '1'возникает после нее. Нам не нужно беспокоиться о том, что 1 не встречается, потому что 1 будет отображаться в нормализованном шаблоне, когда его нет на входе.

ПРИМЕЧАНИЕ: я знаю, что замена str(i)for i in t на map(str,t) и {i for i in`x`if i.isdigit()} с set('012345678')&set(`x`) сделает исходный код короче, но это все равно будет немного дольше, чем замена I .