0079 破译密码
* * * *
拉格朗日计划
* * * *
破译密码

一种常用的密保手段是向用户询问密码中的三个随机位置处的字符。例如,若密码是531278,则询问第2、3、5位时用户应回答317。

在文件keylog.txt中包含对某个未知数字密码的50次的正确回答。

假设所询问的三个位置总是按升序排列,求能与该文件的数据记录一致的最短密码。

本题难度:



解答

对0-9的每个数字i,统计文件中出现在i之前的数字和出现在i之后的数字,分别用pre[i]和post[i]表示,结果如下: $$ \begin{matrix} digit & pre & post \\ 0 & [1, 2, 3, 6, 7, 8, 9] & [] \\ 1 & [3, 7] & [0, 2, 6, 8, 9] \\ 2 & [1, 3, 6, 7] & [0, 8, 9] \\ 3 & [7] & [0, 1, 2, 6, 8, 9] \\ 4 & [] & [] \\ 5 & [] & [] \\ 6 & [1, 3, 7] & [0, 2, 8, 9] \\ 7 & [] & [0, 1, 2, 3, 6, 8, 9] \\ 8 & [1, 2, 3, 6, 7] & [0, 9] \\ 9 & [1, 2, 3, 6, 7, 8] & [0] \\ \end{matrix} $$ 对表中数据拓扑排序后不难看出结果是$73162890$。

s=[]
with open("079_keylog.txt") as f:
    for line in f:
        s.append(line.strip())

t=sorted(list(set(s)))
d=[[[],[]] for i in range(10)]

for x in t:
    a,b,c=map(int,x)
    d[a][1].append(b)
    d[a][1].append(c)
    d[b][1].append(c)
    d[b][0].append(a)
    d[c][0].append(a)
    d[c][0].append(b)

for i in range(10):
    print i," pre:",sorted(list(set(d[i][0])))," post", sorted(list(set(d[i][1])))