Solution

Answer: 73162890

The key observation is that each successful login attempt gives a partial ordering constraint on the digits of the secret passcode.

If a login attempt is 319, then:

3 appears before 1
1 appears before 9
therefore 3 also appears before 9

So the entire problem becomes:

Find the shortest sequence of digits satisfying all precedence constraints.

This is exactly a topological ordering problem on a directed graph.

Step 1 — Understand the constraints

The file keylog.txt contains these 50 login attempts:

Each 3-digit entry says:

If the attempt is abc, then

$$a < b < c$$

in the ordering of the passcode digits.

For example:

319 gives edges:
$3 \to 1$
$1 \to 9$
680 gives:
$6 \to 8$
$8 \to 0$

We combine all such constraints.

Step 2 — Build the directed graph

Collect all precedence relations.

From all entries, we obtain constraints such as:

$7 \to 3$
$7 \to 1$
$3 \to 1$
$1 \to 9$
$6 \to 8$
$8 \to 0$
etc.

The digits involved are:

$${0,1,2,3,6,7,8,9}$$

Notice digit 4 and 5 never appear, so they cannot belong to the shortest valid passcode.

Step 3 — Topological ordering

We now repeatedly choose a digit with no unmet predecessors.

The ordering emerges uniquely:

7 must come first.
Then 3.
Then 1.
Then 6.
Then 2.
Then 8.
Then 9.
Finally 0.

Thus the shortest passcode is:

$$73162890$$

Python implementation

from collections import defaultdict, deque

# Login attempts from the problem file
attempts = [
    "319","680","180","690","129","620","762","689","762","318",
    "368","710","720","710","629","168","160","689","716","731",
    "736","729","316","729","729","710","769","290","719","680",
    "318","389","162","289","162","718","729","319","790","680",
    "890","362","319","760","316","729","380","319","728","716"
]

# Directed graph
graph = defaultdict(set)

# In-degree count for topological sort
indegree = defaultdict(int)

# All digits appearing in the file
digits = set()

# Build precedence graph
for attempt in attempts:
    a, b, c = attempt
    digits.update([a, b, c])

    # Add edge a -> b
    if b not in graph[a]:
        graph[a].add(b)
        indegree[b] += 1

    # Add edge b -> c
    if c not in graph[b]:
        graph[b].add(c)
        indegree[c] += 1

# Ensure every digit exists in indegree dictionary
for d in digits:
    indegree[d] += 0

# Queue all nodes with indegree 0
queue = deque(sorted([d for d in digits if indegree[d] == 0]))

# Topological ordering
result = []

while queue:
    node = queue.popleft()
    result.append(node)

    for nxt in sorted(graph[node]):
        indegree[nxt] -= 1
        if indegree[nxt] == 0:
            queue.append(nxt)

# Construct passcode
passcode = "".join(result)

print(passcode)

Code walkthrough

Build the graph

graph = defaultdict(set)
indegree = defaultdict(int)

graph[a] stores all digits that must come after a.
indegree[x] counts how many prerequisites digit x has.

a, b, c = attempt

For a string like "319":

a = '3'
b = '1'
c = '9'

We add edges:

a -> b
b -> c

This encodes the required ordering.

Topological sort

Digits with indegree = 0 have no remaining prerequisites.

queue = deque(sorted([...]))

We repeatedly:

remove a valid digit,
append it to the answer,
decrease indegrees of dependent digits.

This constructs a valid shortest ordering satisfying all constraints.

Small example verification

Suppose attempts were only:

319
318

Constraints:

$3 < 1 < 9$
$3 < 1 < 8$

A valid shortest passcode would be:

The algorithm correctly produces such an ordering.

Final verification

The computed passcode:

$$73162890$$

contains exactly the digits that appear in the log,
satisfies every ordering constraint,
is minimal because topological ordering uses each necessary digit once.

Checking a few examples:

319 appears in order inside 73162890
680 appears in order
729 appears in order
890 appears in order

All constraints are satisfied.

Answer: 73162890

Project Euler Problem 79