079. 密码推断(Passcode derivation)

网上银行经常使用的一种安全措施是向用户询问其密码中的三个随机字符。例如,如果密码是531278,银行可能会问用户密码中的第二个、第三个和第五个字符是多少,正确的回复应该是317。文本文件 keylog.txt包含了五十个成功的登录尝试,假设其中的三个字符总是按顺序出现的,通过分析这个文件推断出未知长度的最短的可能密码。

分析:这道题可以使用图论中的拓扑排序算法较为容易的解决。所谓拓扑排序(Topological Sorting)是指一个有向无环图(DAG, Directed Acyclic Graph)中的所有顶点的线性序列。且该序列必须满足下面两个条件:(1)每个顶点出现且只出现一次;(2)若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。显然,只有有向无环图才有拓扑排序,非有向无环图不存在拓扑排序。通过分析题意,题目要求最短的可能密码,因此这个密码中必然不能出现重复的数字,否则就不可能是最短的,这满足拓扑排序的第一个条件。此外,文本文件中给出的五十个三位数都是按照同样的从前到后的顺序从密码中取出来的,因此也满足拓扑排序的第二个条件。因此,题目要求的长度最短的可能密码实际上就是求这个图的拓扑排序。

经过分析,我们发现这五十个数字中只有三十三个是不重复的,因此我们可以用集合来存储这些数字避免重复。对于其中的任意一个数字,实际上可以构成有向图的两条边,比如319就表明存在\(3\rightarrow9\)以及\(1\rightarrow9\)这两条边。我们使用networkx库将这些边的数据导入到图中,遍历所有三十三个数字,最终形成的图如下:

img

从以上图中我们就可以明显看出,因为7这个数字不存在指向它的边,因此必然是密码中的第一个数字;此外,没有从0这个数字出发指向其它数字的边,所以0必然是密码中最后一个数字。在有了以上图模型后,我们可以使用卡恩算法或者深度优先搜索求出这个图的拓扑排序。在这里我们就不重复造轮子了,直接使用networkx库中已有的算法。经过尝试,这个图只存在一个拓扑排序,将它拼接成一个数字,即为题目所求。

# time cost = 367 µs ± 2.94 µs

import networkx as nx

def get_data_from_file(file_name="data/ep79.txt"):
    data = set()
    with open(file_name) as f:
        for line in f.readlines():
            data.add(line)
    return data

def main():
    data = get_data_from_file()
    G = nx.DiGraph()
    for i in data:
        G.add_edges_from([(i[0],i[1]),(i[1],i[2])])
    ans = list(nx.all_topological_sorts(G))[0]
    return int(''.join(ans))