计算Android屏幕解锁组合数

晚饭时和同事聊到安卓屏幕解锁时会有多少种解锁方案,觉得很有趣,吃完饭开始想办法解题,花了大概2个小时解决。思路如下:

  1. 使用索引值0-9表示从左到右、从上到下的9个点,行、列号很容易从索引值得到;
  2. 使用一个列表(routeList)来表示解锁路径,列表的元素为点的索引值;
  3. 从任意点N出发(将index(N)放入routeList),判断与哪些点(集合NextNodes)可以构成合法路径;然后用递归的方式从NextNodes中的点出发,寻找下一个可以构成合法路径的点;直到再也无法找到可用的点供路径使用

下一步,就是在Nexus 7上捣鼓,发现Android定义合法的解锁路径必须满足下列条件:

  • 构成路径的点不得少于4个
  • 路径中不能有重复的点
  • (这点有点绕口)构成边或对角线的两点(例如[0,2]构成边,[0,8]构成对角线),不能在路径中相邻,除非其中点已经在路径中出现

接下来就是写代码了,Let's talk with the code!

问题的解是:

 ###############################################################
####### AndrUlkComb.py #########
## Calculate the COMBination count for ANDroid UNLock screen ##
## By grepall@gmail.com ##
############################################################### ###############################################################
## The Android unlock screen looks like below
## -------------------------------
## o -> o -> o
##
## o o o
##
## o o o
## --------------------------------
##
## We'll use:
## 1. Index from 0-8 to represent all 9 nodes instead of
## using row:column format.
## 2. An array (routeList in the code) to record the path of the unlock combination.
## For example, for the unlock comb which is shown in
## in the figure. There will be 3 elements in the array:
## 0, 1, and 2. (Although it's NOT a valid path because of
## not long enough)
##
## Valid unlock path must holds true for 3 conditions:
## C1: It must pass 4 different nodes at least;
## C2: It cannot contains duplicate nodes;
## C3: This is a little tricky. Any node cannot direct link to another node, when
## any node will be past through if we connect those 2 nodes in the unlock panel. UNLESS
## the crossed node already EXISTs in the path.
## For example, path (0, 2, 5, 4) is not valid, because 0-->2 crosses node 1. But path
## (1, 0, 2, 5) is a vliad path.
## This rule holds for diagonal as well. #######################################################################
# M stands for the width of the unlock panel
# H stands for the height of the unlock panel
# CAUTION: Modify this value will NOT generate correct result!!! That's TO BE DONE
#
W = 3 #Width
H = 3 #Height # Unlock path
routeList = list() # Combination count, which is we want to know
routeCount = 0 def isValidRoute(p1, route):
# If the candidate node exists in the unlock path
if route.count(p1) != 0:
return False
return True; def isCrossPoint(p1, p2):
# Will the connection line (p1, p2) cross another node?
x1 = p1%W
y1 = p1/W
x2 = p2%W
y2 = p2/W
if x1 == x2 and abs(y1-y2) > 1:
return True # same column
if y1 == y2 and abs(x1-x2) > 1:
return True # same row
if abs(y1-y2) == abs(x1-x2) and abs(y1-y2)>1:
return True # diagonal
return False def tryPoint(lastPt, route):
# Try next valid node for the unlock path recursively
global routeCount
for pt in range(0, W*H):
if isValidRoute(pt, route): #C2
crossPt = (lastPt+pt)/2
if isCrossPoint(lastPt, pt) and route.count(crossPt) == 0: #C3
continue
route.append(pt)
if len(route) >3: #C1
routeCount += 1
tryPoint(pt, route)
route.pop() # Each node may be the start node for unlock
for i in range(0, W*H):
routeList = [i]
tryPoint(i, routeList)
print "Start from point %d, combination count is %d now..." % (i, routeCount)
print "Toatl combination counter for Android unlock screen: " + str(routeCount)
上一篇:j2ee的13个标准


下一篇:Tomcat设置开启时自动访问某个servlet类存在的问题