Google


Tuesday, January 11, 2011

Android lock

I have tried to determine the number of possible combinations on a 3x3 Android pattern lock. I come up with 10,305 combinations which is slightly more than the 10,000 combinations you would get with a 4 number lock. Let me know if you find any errors.

#count how many patterns there are on 3x3 lock
#every point visited once
#can move straight and diagonal
#path length 1 to 9

#length 1 is trivial: 9 possibilities

done=dict()
for c in range(1,4):
    for r in range(1,4):
        poss=len(done)
        done[poss]=[[c,r]]

poss=len(done)
print poss

def posspath(curpath): #returns all possible paths from a curpath
    outpath=[]
    #can go 8 different ways
    for add in ([0,1],[1,0],[1,1],[0,-1],[-1,0],[1,-1],[-1,1],[-1,-1]):
        c=curpath[-1][0]
        r=curpath[-1][1]
        #if within bounds and not visited
        if 1<=c+add[0]<=3 and 1<=r+add[1]<=3 and [c+add[0],r+add[1]] not in curpath:
            outpath+=[curpath+[[c+add[0],r+add[1]]]]
    return outpath
   
for path in range(2,10):
    for c in range(1,4):
        for r in range(1,4):
            curpath=[[c,r]]
            nextpath=posspath(curpath)
            i=0
            while i
                if len(nextpath[i])==path:
                    if nextpath[i] not in done.keys():
                        poss=len(done)
                        done[poss]=nextpath[i]
                else:
                    #explore possible and remove original
                    nextpath2=posspath(nextpath[i])
                    nextpath.remove(nextpath[i])
                    nextpath+=nextpath2
                    i-=1
                i+=1
           
poss=len(done)
print poss

               
        
                       

2 comments:

anders-kaseorg said...

Your answer isn’t right because the Android allows some patterns that you didn’t account for. The actual number is 389112.

yurx said...

Moves = 4, combinations = 1624
Moves = 5, combinations = 7152
Moves = 6, combinations = 26016
Moves = 7, combinations = 72912
Moves = 8, combinations = 140704
Moves = 9, combinations = 140704
Total combinations (using 4-9 dots) = 389112