Powiedzmy, że widziałeś, jak znajomy wprowadza swoje hasło do swojego telefonu z Androidem. Nie pamiętasz, jak zrobili wzór, ale pamiętasz, jak wygląda wzór. Będąc zaniepokojonym przyjacielem, którym jesteś, chcesz wiedzieć, jak bezpieczne jest jego hasło. Twoim zadaniem jest obliczyć wszystkie sposoby wykonania określonego wzoru.

Jak działają wzorce Androida

Wzory są rysowane na siatce 3 x 3 węzłów. We wzorze odwiedza się szereg węzłów, nie podnosząc nigdy palca z ekranu. Każdy odwiedzany węzeł jest połączony krawędzią z poprzednim węzłem. Należy pamiętać o dwóch zasadach.

• Nie możesz odwiedzić żadnego węzła więcej niż raz

• Krawędź nie może przechodzić przez nieodwiedzony węzeł

Pamiętaj, że chociaż zazwyczaj bardzo trudny do wykonania, a zatem niezbyt powszechny w prawdziwych kombinacjach blokad Androida, można poruszać się jak rycerz . Oznacza to, że możliwe jest przejście z jednej strony do niesąsiadującego rogu lub na drugą stronę. Oto dwa przykłady wzorców wykorzystujących taki ruch:

Oto animowany gif, który jest wykonywany.

Rozwiązywanie wzoru

Typowy wzór może wyglądać mniej więcej tak:

Z prostym wzorem takim jak ten istnieją dwa sposoby narysowania wzoru. Możesz zacząć od jednego z dwóch luźnych końców i podróżować przez podświetlone węzły do ​​drugiego. Chociaż jest to prawdą w przypadku wielu wzorców, szczególnie tych, które zwykle stosują ludzie, nie dotyczy to wszystkich wzorców.

Rozważ następujący wzór:

Istnieją dwa natychmiast rozpoznawalne rozwiązania. Jeden zaczyna się w lewym górnym rogu:

I jeden zaczynający się w dolnej środkowej części:

Ponieważ jednak linia może przechodzić przez punkt, który już został wybrany, w górnym środkowym środku pojawia się dodatkowy wzór:

Ten konkretny wzór ma 3 rozwiązania, ale wzory mogą mieć od 1 do 4 rozwiązań ^{[potrzebne źródło]} .

Oto kilka przykładów:

1.

2)

3)

4

I / O

Węzeł może być reprezentowany jako liczby całkowite od zera do dziewięciu włącznie, ich ciągi znaków lub znaki od a do i (lub od A do I). Każdy węzeł musi mieć unikalną reprezentację z jednego z tych zestawów.

Rozwiązanie będzie reprezentowane przez uporządkowany kontener zawierający reprezentacje węzłów. Węzły muszą być zamawiane w tej samej kolejności, w jakiej są przekazywane.

Wzór będzie reprezentowany przez nieuporządkowany kontener par węzłów. Każda para reprezentuje krawędź rozpoczynającą się od połączenia dwóch punktów w parze. Reprezentacje wzorów nie są unikalne.

Przyjmiesz reprezentację wzorca jako dane wejściowe za pomocą standardowych metod wprowadzania i wyświetlisz wszystkie możliwe rozwiązania, które tworzą ten sam wzór za pomocą standardowych metod wyjścia.

Możesz założyć, że każde wejście będzie miało co najmniej jedno rozwiązanie i połączy co najmniej 4 węzły.

Możesz zdecydować się na użycie zamówionego kontenera zamiast nieuporządkowanego, jeśli chcesz lub jesteś zmuszony przez wybór języka.

Przypadki testowe

Z węzłami ułożonymi w następujący wzór:

0 1 2
3 4 5
6 7 8

Niech {...}stanie się nieuporządkowanym pojemnikiem, [...]będzie zamówionym pojemnikiem i (...)będzie parą.

Następujące wejścia i wyjścia powinny się zgadzać

{(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)} -> {}

Album imgur wszystkich przypadków testowych, jak zdjęcia można znaleźć tutaj . Wzory są w kolorze niebieskim rozwiązania w kolorze czerwonym.

Punktacja

To jest kod golfowy. Wygrywa najmniej bajtów.

Python 2.7, 493 430 bajtów

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 '))

Wersja jednowierszowa otacza program, exec("...".replace('I',' for i in '))dzięki czemu wszystkie pętle for i generatory mogą być zwierane jednym Ii oszczędza 15 bajtów w stosunku do tej bardziej czytelnej wersji:

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)))]

Program pobiera dane wejściowe w sposób pokazany (np. {(1,4),(3,4),(5,4),(8,5)}) Lub jako listę ciągów (np. ['14','34','54','85']) (Lub w innych formatach przyjaznych dla Pythona) i zwraca dane wyjściowe jako listę ciągów. Więc technicznie mamy zamówiony pojemnik z zamówionymi pojemnikami.

Funkcja Nnormalizuje wzorzec, dzięki czemu można łatwo porównać dwa wzorce. Normalizacja sortuje pary oznaczające krawędzie (więc '02'zamiast '20'), użyj zamiany łańcucha, aby rozwinąć podwójne krawędzie (np. '02'Staje się '01 12'), dzieli krawędzie na zestaw, aby usunąć duplikaty, i sortuje wynik.

Funkcja Fspłaszcza krotki liczb całkowitych / ciągów do ciągów, dzięki czemu możemy normalizować ścieżki wytworzone na różne sposoby.

Lista Lzawiera wszystkie linie na ekranie.

Następnie bierzemy każdą permutację wszystkich cyfr w znormalizowanym wzorze i obliczamy prawidłową ścieżkę lub Ljeśli jest niepoprawna (która nigdy nie normalizuje się do listy par, tak jak w przypadku prawdziwych ścieżek), lub listę par wskazującą, że węzły porządku są odwiedzane, jeśli są poprawne. Jeśli normalizuje się ten sam wzorzec, mamy prawidłowe rozwiązanie i umieszczamy je na końcowej liście.

Głównym sprawdzianem potrzebnym do zweryfikowania permutacji jako łańcucha sjest -1<s.find(i[::2])<s.find(i[1])wykrycie błędu z linią i. Na przykład w wierszu '210'kod wykrywa błąd, jeśli '20'wystąpi (tzn. Jego indeks jest większy niż -1) i '1'występuje po nim. Nie musimy się martwić, że 1 nie wystąpi, ponieważ 1 pojawi się w znormalizowanym wzorze, gdy nie był wprowadzony.

UWAGA: Wiem, zastępując str(i)for i in t z map(str,t) i {i for i in`x`if i.isdigit()} z set('012345678')&set(`x`) uczyniłoby oryginalny kod krótszy, ale to nadal będzie nieco dłuższy, że podstawiając I .