如何仅用Python标准库推导Project Euler #79的最短密码顺序？

在线银行常用的一种安全验证方式是要求用户输入密码中的三个随机字符。例如，若密码为531278，可能要求输入第2、3、5位字符，预期回复为317。
文本文件keylog.txt包含50次成功登录尝试记录。已知每次要求的三个字符均按密码中的顺序给出，需分析该文件以确定最短的可能密码。

目前已确定密码由8个不同数字组成（集合为{'3', '7', '2', '6', '1', '0', '9', '8'}），但无法确定数字的顺序。尝试编写is_before(x)、is_after(x)等函数来推导数字相对位置，但逻辑复杂且无法得到正确结果，现需定义函数完成密码数字的排序。

现有代码如下：

# 读取文件并通过集合去重，转成列表
with open('D:\\Development\\keylog.txt', 'r') as file:
    logins = list(set(file.read().split()))

# 创建三个分别对应登录记录中三个位置数字的集合
first_digits = set()
second_digits = set()
third_digits = set()

for login in logins:
    first_digits.add(login[0])
    second_digits.add(login[1])
    third_digits.add(login[2])

newSet = (first_digits | second_digits | third_digits)

# 三个集合合并后得到8个数字的集合
# 由此可推断最短密码由这8个不同数字组成
# 集合内容为：{'3', '7', '2', '6', '1', '0', '9', '8'}

# 待定义：推导密码数字顺序的函数

这个问题本质是拓扑排序问题：每个登录记录abc都隐含了a必须在b之前、b必须在c之前的约束关系，我们可以把这些约束转换成有向无环图（DAG），再通过拓扑排序得到满足所有约束的最短序列。

具体步骤：

• 构建约束关系：遍历去重后的登录记录，为每个abc添加a→b、b→c的有向边，同时记录每个节点的入度（即有多少数字必须在它之前）。
• 拓扑排序：
  1. 初始化队列，把所有入度为0的节点（即没有任何数字必须在它前面的数字）加入队列。
  2. 每次从队列取出一个节点，加入结果序列，然后遍历它的所有邻接节点，将邻接节点的入度减1；如果邻接节点入度变为0，就加入队列。
  3. 重复直到队列为空，得到的序列就是满足所有约束的最短密码。

实现代码：

from collections import deque

with open('D:\\Development\\keylog.txt', 'r') as file:
    logins = list(set(file.read().split()))

# 初始化图和入度字典
graph = {digit: set() for digit in {'3', '7', '2', '6', '1', '0', '9', '8'}}
in_degree = {digit: 0 for digit in {'3', '7', '2', '6', '1', '0', '9', '8'}}

# 构建约束关系
for seq in logins:
    # 添加 a -> b 的约束
    if seq[1] not in graph[seq[0]]:
        graph[seq[0]].add(seq[1])
        in_degree[seq[1]] += 1
    # 添加 b -> c 的约束
    if seq[2] not in graph[seq[1]]:
        graph[seq[1]].add(seq[2])
        in_degree[seq[2]] += 1

# 拓扑排序
queue = deque([digit for digit in in_degree if in_degree[digit] == 0])
passcode = []

while queue:
    current = queue.popleft()
    passcode.append(current)
    for neighbor in graph[current]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0:
            queue.append(neighbor)

# 输出结果
print("最短可能密码:", ''.join(passcode))

代码说明 #

• graph字典存储每个数字的后续必须出现的数字集合，in_degree存储每个数字需要前置的数字数量。
• 拓扑排序过程确保每次选择没有前置约束的数字，逐步构建符合所有登录记录顺序的密码。
• 因为所有约束都能构成无环图（题目保证存在有效密码），最终得到的序列就是最短的8位密码。

内容的提问来源于stack exchange，提问作者Sigmatest