Android On an Android smartphone, there are some interesting and different ways
ID: 3120888 • Letter: A
Question
Android On an Android smartphone, there are some interesting and different ways of entering a passcode. The swipe lock is a graph with 9 vertices and we want to create a directed path on the graph. (Remember that a path is a walk in which you never revisit a vertex. Saying that the path is directed means that you have a starting and ending place as indicated by the arrows in the picture.) How many swipe passwords (directed paths) are possible on a grid of 9 dots of length 4 if we add the restriction that (1) there are no loops and (2) it never revisits a vertex. What if we extend it to passwords of length 5? What if we extend it to passwords of length 6? How many passwords are there of length at least 4 at most 6? The next vertex in a path doesn't have to be a neighboring vertex. You can go from corner to corner in one step if you like.Explanation / Answer
Solution:
If the nodes are labeled as
1 2 3
then (1 2 3), (2 1 3), (2 3 1), (3 2 1) could all be valid. (Note that these are all too short, since the minimum length is 4 points.)
The output of the code below is:
Sequences by length: [0, 0, 0, 0, 1624, 7152, 26016, 72912, 140704, 140704]
total number of sequences : 389112
min_seq_length = 4
def Middle(a, b):
"""Return the node between a and b if there is one, or None."""
if (a+b)%2 != 0:
return None
mid = (a+b)/2
if mid == 5:
return mid
if a%3 == b%3:
return mid
if (a-1)/3 == (b-1)/3:
return mid
return None
def NextValid(base):
"""Generate valid moves j+1 given a sequence of moves 1..j."""
if len(base) >= 9:
return
if len(base) == 0:
for i in xrange(1,10):
yield i
return
for i in xrange(1,10):
if not i in base:
mid = Middle(i, base[-1])
if mid is None or mid in base:
yield i
def Sequences(base):
"""Generator for valid sequences of moves."""
if len(base) >= min_seq_length:
yield list(base)
for n in NextValid(base):
for s in Sequences(base + [n]):
yield s
seqs_of_length = [0]*10
for seq in Sequences([]):
seqs_of_length[len(seq)] += 1
print 'Sequences by length:', seqs_of_length
print 'Total number of sequences:', sum(seqs_of_length).