Nehmen wir an, Sie haben gesehen, wie Ihr Freund sein Passwort in sein Android-Handy eingegeben hat. Sie erinnern sich nicht, wie sie das Muster erstellt haben, aber Sie erinnern sich, wie das Muster aussieht. Als betroffener Freund möchten Sie wissen, wie sicher sein Passwort ist. Ihre Aufgabe ist es, alle Möglichkeiten zu berechnen, mit denen ein bestimmtes Muster erstellt werden kann.

Wie Android-Muster funktionieren

Muster werden in einem 3x3-Raster von Knoten gezeichnet. In einem Muster besucht man eine Reihe von Knoten, ohne jemals den Finger vom Bildschirm zu heben. Jeder Knoten, den sie besuchen, ist durch eine Kante mit dem vorherigen Knoten verbunden. Es sind zwei Regeln zu beachten.

• Sie dürfen einen Knoten nur einmal besuchen

• Eine Kante darf einen nicht besuchten Knoten nicht passieren

Beachten Sie, dass es möglich ist, sich wie ein Ritter zu bewegen, obwohl dies in der Regel sehr schwierig und daher in realen Android-Lock-Kombinationen nicht sehr häufig ist . Das heißt, es ist möglich, sich von einer Seite zu einer nicht angrenzenden Ecke oder umgekehrt zu bewegen. Hier sind zwei Beispiele für Muster, die eine solche Bewegung anwenden:

Hier ist ein animiertes Gif davon, wie es aufgeführt wird.

Ein Muster lösen

Ein typisches Muster könnte ungefähr so ​​aussehen:

Bei einem einfachen Muster wie diesem gibt es zwei Möglichkeiten, das Muster zu zeichnen. Sie können an einem der beiden losen Enden beginnen und durch die hervorgehobenen Knoten zum anderen gehen. Während dies für viele Muster gilt, insbesondere für solche, die Menschen normalerweise anwenden, gilt dies nicht für alle Muster.

Betrachten Sie das folgende Muster:

Es gibt zwei sofort erkennbare Lösungen. Einer beginnt oben links:

Und eine, die unten in der Mitte beginnt:

Da eine Linie jedoch einen Punkt passieren darf, nachdem sie bereits ausgewählt wurde, beginnt in der oberen Mitte ein zusätzliches Muster:

Dieses spezielle Muster hat 3 Lösungen, aber Muster können irgendwo zwischen 1 und 4 Lösungen haben ^{[Zitieren benötigt]} .

Hier einige Beispiele:

1.

2.

3.

4.

I / O

Ein Knoten kann als Ganzzahl von null bis einschließlich neun, als Zeichenfolgenäquivalent oder als Zeichen von a bis i (oder A bis I) dargestellt werden. Jeder Knoten muss eine eindeutige Darstellung aus einer dieser Mengen haben.

Eine Lösung wird durch einen geordneten Container dargestellt, der Knotendarstellungen enthält. Knoten müssen in der Reihenfolge bestellt werden, in der sie durchlaufen werden.

Ein Muster wird durch einen ungeordneten Container mit Knotenpaaren dargestellt. Jedes Paar stellt eine Kante dar, die die beiden Punkte des Paares verbindet. Musterdarstellungen sind nicht eindeutig.

Sie nehmen eine Musterdarstellung als Eingabe über Standardeingabemethoden und geben alle möglichen Lösungen aus, die das gleiche Muster über Standardausgabemethoden erstellen.

Sie können davon ausgehen, dass jeder Eingang mindestens eine Lösung hat und mindestens 4 Knoten miteinander verbindet.

Sie können einen bestellten Container anstelle eines ungeordneten Containers verwenden, wenn Sie dies wünschen oder aufgrund der Sprachauswahl dazu gezwungen sind.

Testfälle

Mit den Knoten in folgendem Muster angeordnet:

0 1 2
3 4 5
6 7 8

Sei {...}ein ungeordneter Behälter,[...] sei ein geordneter Container und (...)sei ein Paar.

Die folgenden Ein- und Ausgänge sollten übereinstimmen

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

Ein imgur Album aller Testfälle als Bilder kann gefunden werden hier . Muster sind in blauen Lösungen in rot.

Wertung

Das ist Code Golf. Wenigste Bytes gewinnt.

Python 2.7, 493 430 Bytes

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

Die einzeilige Version umschließt das Programm, exec("...".replace('I',' for i in '))sodass alle for-Schleifen und Generatoren mit einer einzigen kurzgeschlossen werden können, Iund spart 15 Byte gegenüber dieser besser lesbaren Version:

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

Das Programm nimmt die Eingabe in der gezeigten Weise (z. B. {(1,4),(3,4),(5,4),(8,5)}) oder als Liste von Zeichenfolgen (z. B. ['14','34','54','85']) (oder in anderen pythonfreundlichen Formaten) und gibt die Ausgabe als Liste von Zeichenfolgen zurück.Wir haben also technisch einen bestellten Container mit bestellten Containern.

Die Funktion Nnormalisiert ein Muster, so dass zwei Muster leicht verglichen werden können. Bei der Normalisierung werden die Paare sortiert, die Kanten kennzeichnen ( '02'statt '20'). Verwenden Sie die Zeichenfolgenersetzung, um doppelte Kanten zu erweitern (z. B. '02'wird'01 12' ), teilen Sie die Kanten in eine Gruppe, um doppelte Kanten zu entfernen, und sortieren Sie das Ergebnis.

Die Funktion F Tupel von Ints / Strings zu Strings geglättet, sodass wir Pfade normalisieren können, die auf unterschiedliche Weise erstellt wurden.

Die Liste L enthält alle Zeilen auf dem Bildschirm.

Wir nehmen dann jede Permutation aller Ziffern im normalisierten Muster und berechnen einen gültigen Pfad oder L ungültigen (der sich niemals zu einer Liste von Paaren normalisiert, wie dies bei realen Pfaden der Fall wäre) oder eine Liste von Paaren, die angibt, dass die Auftragsknoten besucht werden, wenn sie gültig sind. Wenn sich dies auf dasselbe Muster normalisiert, haben wir eine gültige Lösung und nehmen sie in die endgültige Liste auf.

Die Hauptprüfung, die zum Überprüfen einer Permutation als Zeichenfolge erforderlich sist -1<s.find(i[::2])<s.find(i[1]), besteht darin , dass ein Fehler in einer Zeile erkannt wird i. Beispielsweise '210'erkennt der Code bei der Zeile einen Fehler, wenn ein Fehler '20'auftritt (dh der Index ist größer als -1), und '1'tritt danach auf. Wir müssen uns keine Sorgen machen, dass 1 nicht auftritt, da die 1 im normalisierten Muster angezeigt wird, wenn sie nicht in der Eingabe enthalten ist.

ANMERKUNG: Ich weiß, dass das Ersetzen str(i)for i in t mit map(str,t) und {i for i in`x`if i.isdigit()} mit set('012345678')&set(`x`) den ursprünglichen Code kürzer machen würde, aber dies wäre immer noch etwas länger als das Ersetzen I .