This is only a partial answer. The only relevant starting dots are 1, 2, and 5. For dots 1 and 2, you can generate a pattern equivalent to starting at any of the other dots (other than 5) with a simple rotation transformation. This means if you can enumerate all the patterns starting at 1 and 2 you can count all the patterns starting at any number other than 5 by multiplying by 4.
The paths starting at 5 are a different case. You can count all of them by counting all the paths that start with 5->1 and 5->2 and multiplying by 4 since you again can generate all the other possible paths with a simple rotation transformation.
So, a way to enumerate the paths would be...
(All paths starting at 1 + all paths starting at 2 + all paths starting with 5->1 + all paths starting with 5->2) * 4
Again, the numbering system, for easy reference:
1 2 3
4 5 6
7 8 9
For this first move:
From 1 -> 2, 4, 5, 6 and 8 are accessible.
From 2 -> 1, 3, 4, 5, 6, 7, and 9 are accessible (basically just not 8 or itself).
From 5 -> 1, 2, 3, 4, 6, 7, 8, and 9 are accessible.
For moves after that it gets really interesting.
For example, 1537 is a valid password. 1539 is not.
Here succinctly, are the rules:
No dot may be part of the path twice. If a dot is not part of the path and it is exactly crossed over by a transition, it becomes part of the path between the source dot and destination dot.
Here are some sample paths:
- 2->3->1->8 is allowed.
- 1->3->2->5 is not allowed because 2 is not part of the path when 1->3 goes exactly over 2, so the path becomes 1->2->3->5 whether you want it to or not.
- 1->2->3->7 is not allowed because 3->7 crosses over 5 and 5 is not already part of the path.
- 1->5->3->7 is allowed. 5 is ignored in 3->7 because it is already part of the path.
This program:
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)
Generates an answer of 389112.
It also validates my previous intuitions:
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