Passcode Derivation ¶

Gotta read the data first.

In [1]:

with open("txt/0079_keylog.txt") as f:
    keylog = {tuple(int(c) for c in line.strip()) for line in f}

If we assume that no characters are repeated in the passcode, then each entry in the keylog gives a partial ordering of the characters in the passcode. In math jargon, we are then looking for a linear extension of the partial ordering. This can be found with a topological sorting algorithm.

(If characters are repeated, we would instead have a preordering, and a topological sort wouldn't work. Fortunately for us, our assumption turns out to be correct.)

Conveniently, and somewhat interestingly, Python has graphlib in its standard library, which (as of the time of writing) only implements topological sorting - but that's all we need for this problem, so I guess don't look a gift horse in the mouth.

In [2]:

from graphlib import TopologicalSorter

ts = TopologicalSorter()
for attempt in keylog:
    for (idx, d) in enumerate(attempt):
        predecessors = attempt[:idx]
        ts.add(d, *predecessors)

tuple(ts.static_order())

Out[2]:

(7, 3, 1, 6, 2, 8, 9, 0)

Copyright (C) 2025 filifa¶

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.