Project Euler Problem 79 Solution: Passcode Derivation

Project Euler Problem 79 Statement

A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may ask for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.

The text file, keylog.txt, contains fifty successful login attempts.

Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.

Solution

HackerRank Project Euler Problem 79 overview:

This problem involves determining the shortest possible secret passcode based on multiple successful login attempts. Each attempt provides three distinct characters in the correct order as they appear in the passcode. All characters in the passcode are unique and have ASCII codes within a specified range. Your task is to analyze these ordered triplets to reconstruct the minimal passcode that satisfies all the given ordering constraints. If multiple valid passcodes exist, you should choose the lexicographically smallest one. If the constraints are inconsistent and no valid passcode can be formed, the output should be "SMTH WRONG".

Solution Summary

This solution uses topological sorting (Kahn's algorithm) to deduce the correct ordering of digits (or characters) in the passcode based on ordering constraints from multiple login attempts. The use of a min-heap ensures that when there are multiple valid candidates for the next digit, the lexicographically smallest one is chosen.

Solution Detail

1. Input Parsing

The code reads the number of login attempts and then each attempt. For example, if the input is:

5
SMH
TON
RNG
WRO
THG

then the list of attempts will be code>['SMH','TON','RNG','WRO','THG'].

2. Building the Graph

The goal is to build a directed graph where each directed edge represents the ordering constraint extracted from an attempt. For example, in the attempt "SMH":

$S \rightarrow M$: $S$ comes before $M$.
$M \rightarrow H$: $M$ comes before $H$.

The data structures used are:

An adjacency list (adj) to map each character to a set of characters that must follow it.
An in-degree dictionary (deg) where for every character $c$, deg[c] indicates how many characters must come before it.
A set (chars) of all unique characters from the login attempts.

3. Populating the Graph

For each login attempt, consecutive characters are paired using zip:

for attempt in attempts:
    for i, j in zip(attempt, attempt[1:]):
        if j not in adj[i]:
            adj[i].add(j)
            deg[j] += 1

This ensures that each unique ordering constraint is recorded once. For every new edge $i \rightarrow j$, $j$'s in-degree is incremented:

$$\text{deg}[j] \mathrel{+}= 1$$

4. Preparing the Topological Sort

A min-heap is used to obtain the digit with the smallest lexicographical order when there is a tie. First, all characters with zero in-degree (i.e., no prerequisites) are added to the heap:

heap = [c for c in chars if not deg[c]]
heapq.heapify(heap)
result = []

Here, only nodes where $\text{deg}[c] = 0$ are eligible to start the sorting.

5. Topological Sorting (Kahn's Algorithm)

The algorithm repeatedly removes a character from the heap, appends it to the result, and reduces the in-degree of its neighbors:

while heap:
    curr = heapq.heappop(heap)
    result.append(curr)
    for next_digit in adj[curr]:
        deg[next_digit] -= 1
        if not deg[next_digit]:
            heapq.heappush(heap, next_digit)

With each iteration, once a neighbor's in-degree becomes zero, it is added to the heap and processed next.

6. Generating the Final Output

After processing all nodes, the code checks if the result contains all the unique characters:

print("".join(result) if len(result) == len(chars) else "SMTH WRONG")

If the length of result equals the total number of characters, the passcode is valid. Otherwise, this indicates a potential cycle or inconsistency in the constraints, and an error message is printed.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 79

HackerRank Project Euler 79: Assume all characters in your password are different. You're given $T$ successful login attempts each containing 3 characters with ASCII codes from 33 to 126 both inclusive. You need to recover the shortest original password possible. If there are multiple choices, select the lexicographically smallest one.
If something went wrong and the original password cannot be recovered,output SMTH WRONG.

Python Source Code

from collections import defaultdict
import heapq

attempts = [input() for _ in range(int(input()))]
adj, deg = defaultdict(set), defaultdict(int)
chars = set().union(*attempts)

for attempt in attempts:
    for i, j in zip(attempt, attempt[1:]):
        if j not in adj[i]:
            adj[i].add(j)
            deg[j] += 1

heap = [c for c in chars if not deg[c]]
heapq.heapify(heap)
result = []

while heap:
    curr = heapq.heappop(heap)
    result.append(curr)
    for next_digit in adj[curr]:
        deg[next_digit] -= 1
        if not deg[next_digit]:
            heapq.heappush(heap, next_digit)

print("".join(result) if len(result) == len(chars) else "SMTH WRONG")