Dies ist nur eine Teilantwort. Die einzigen relevanten Ausgangspunkte sind 1, 2 und 5. Für die Punkte 1 und 2 kann man mit einer einfachen Rotationstransformation ein Muster erzeugen, das einem Muster entspricht, das bei einem beliebigen anderen Punkt (außer 5) beginnt. Das heißt, wenn man alle Muster, die bei 1 und 2 beginnen, aufzählen kann, kann man auch alle Muster zählen, die bei einer anderen Zahl als 5 beginnen, indem man mit 4 multipliziert.
Die Pfade, die bei 5 beginnen, sind ein anderer Fall. Man kann sie alle zählen, indem man alle Pfade zählt, die mit 5->1 und 5->2 beginnen und mit 4 multipliziert, da man wiederum alle anderen möglichen Pfade mit einer einfachen Rotationstransformation erzeugen kann.
Eine Möglichkeit, die Pfade aufzuzählen, wäre also...
(Alle Wege, die mit 1 beginnen + alle Wege, die mit 2 beginnen + alle Wege, die mit 5->1 beginnen + alle Wege, die mit 5->2 beginnen) * 4
Auch hier wieder das Nummerierungssystem, um den Überblick zu behalten:
1 2 3
4 5 6
7 8 9
Für diesen ersten Schritt:
Von 1 -> 2, 4, 5, 6 und 8 sind zugänglich.
Von 2 -> 1, 3, 4, 5, 6, 7 und 9 sind zugänglich (grundsätzlich nur nicht 8 oder sich selbst).
Von 5 -> 1, 2, 3, 4, 6, 7, 8, und 9 sind zugänglich.
Bei den Zügen danach wird es dann richtig interessant.
Zum Beispiel ist 1537 ein gültiges Passwort. 1539 ist es nicht.
Hier sind die Regeln kurz und bündig:
Kein Punkt darf zweimal Teil des Pfades sein. Ist ein Punkt nicht Teil des Pfades und wird er von einem Übergang genau überquert, wird er Teil des Pfades zwischen Quell- und Zielpunkt.
Hier sind einige Beispielpfade:
- 2->3->1->8 ist erlaubt.
- 1->3->2->5 ist nicht erlaubt, weil 2 nicht Teil des Pfades ist, wenn 1->3 genau über 2 geht, also wird der Pfad zu 1->2->3->5, ob du es willst oder nicht.
- 1->2->3->7 ist nicht zulässig, weil 3->7 die 5 überquert und die 5 nicht bereits Teil des Pfades ist.
- 1->5->3->7 ist erlaubt. Die 5 wird bei 3->7 ignoriert, da sie bereits Teil des Pfades ist.
Dieses Programm:
class LockPattern(object):
def __init__(self, *args):
if (len(args) == 1) and hasattr(args[0], '__iter__'):
args = tuple(args[0])
if len(args) > 9:
raise TypeError("A LockPattern may have at most 9 elements.")
self._pattern = ()
for move in args:
if not self.isValidNextStep(move):
raise TypeError("%r is not a valid lock sequence." % (args,))
else:
self._pattern = self._pattern + (move,)
def __len__(self):
return len(self._pattern)
def __iter__(self):
return iter(self._pattern)
def isValidNextStep(self, nextdot):
nextdot = int(nextdot)
if (nextdot < 1) or (nextdot > 9):
raise ValueError("A lock sequence may only contain values from 1 "
"to 9 and %d isn't." % (nextdot,))
if len(self._pattern) <= 0:
return True # Any dot is valid for the first dot
if len(self._pattern) >= 9:
return False
if nextdot in self._pattern:
return False # No dot may be visited twice
prevdot = self._pattern[-1]
dotpair = tuple(sorted((prevdot, nextdot)))
if dotpair == (1,3):
return 2 in self._pattern
if dotpair == (1,7):
return 4 in self._pattern
if dotpair in ((1,9),(2,8),(3,7),(4,6)):
return 5 in self._pattern
if dotpair == (3,9):
return 6 in self._pattern
if dotpair == (7,9):
return 8 in self._pattern
return True
def isValidLockSequence(self):
return 4 <= len(self)
def newSequenceAddDot(self, nextdot):
if not self.isValidNextStep(nextdot):
raise ValueError("%d is not a valid next dot for the sequence." % (nextdot,))
newseq = LockPattern()
newseq._pattern = self._pattern + (nextdot,)
return newseq
def genAllPatterns(starting = LockPattern()):
if starting.isValidLockSequence():
yield starting
for dot in xrange(1,10):
if starting.isValidNextStep(dot):
for result in genAllPatterns(starting.newSequenceAddDot(dot)):
yield result
print reduce(lambda x, p: x+1, genAllPatterns(), 0)
Erzeugt eine Antwort von 389112.
Es bestätigt auch meine früheren Intuitionen:
lsts = tuple(((p, list(genAllPatterns(LockPattern(p)))) for p in ((1,), (2,), (5,1), (5,2))))
[(x[0], len(x[1])) for x in lsts]
-> [((1,), 38042), ((2,), 43176), ((5, 1), 7352), ((5, 2), 8708)]
sum((len(x[1]) for x in lsts)
-> 97278
97278 * 4
-> 389112
