StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>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.</p> <p>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.</p> <p>So, a way to enumerate the paths would be...</p> <p>(All paths starting at 1 + all paths starting at 2 + all paths starting with 5->1 + all paths starting with 5->2) * 4</p> <p>Again, the numbering system, for easy reference:</p> <pre><code>1 2 3 4 5 6 7 8 9 </code></pre> <p>For this first move:</p> <p>From 1 -> 2, 4, 5, 6 and 8 are accessible.</p> <p>From 2 -> 1, 3, 4, 5, 6, 7, and 9 are accessible (basically just not 8 or itself).</p> <p>From 5 -> 1, 2, 3, 4, 6, 7, 8, and 9 are accessible.</p> <p>For moves after that it gets really interesting.</p> <p>For example, 1537 is a valid password. 1539 is not.</p> <p>Here succinctly, are the rules:</p> <p>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.</p> <p>Here are some sample paths:</p> <ul> <li>2->3->1->8 is allowed.</li> <li>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.</li> <li>1->2->3->7 is not allowed because 3->7 crosses over 5 and 5 is not already part of the path.</li> <li>1->5->3->7 is allowed. 5 is ignored in 3->7 because it is already part of the path.</li> </ul> <p>This program:</p> <pre><code>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) </code></pre> <p>Generates an answer of 389112.</p> <p>It also validates my previous intuitions:</p> <pre><code>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 </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload