notes.html

problem 79 · 27 lines

<article>
<h3>Problem Analysis</h3>
<p>
Each successful login reveals three characters from the passcode in the exact order they occur. A login like "abc" therefore encodes two ordering facts: <em>a</em> appears before <em>b</em>, and <em>b</em> appears before <em>c</em>. Gathering every such "X before Y" fact across all fifty logins yields a <a class="reference-source" href="https://en.wikipedia.org/wiki/Partially_ordered_set" rel="noopener noreferrer" target="_blank">partial order</a> over the distinct observed digits. The shortest passcode consistent with every observation is one that lists each observed digit exactly once, arranged so that no ordering fact is violated. (I assume each digit occurs only once in the passcode; if any digit repeated, the constraints could force a longer answer, but this keylog is consistent with a single occurrence of each digit.)
</p>
<p>
This is the canonical setting for <a class="reference-source" href="https://en.wikipedia.org/wiki/Topological_sorting" rel="noopener noreferrer" target="_blank">topological sorting</a>. I model the constraints as a <a class="reference-source" href="https://en.wikipedia.org/wiki/Directed_acyclic_graph" rel="noopener noreferrer" target="_blank">directed acyclic graph</a> (DAG): each distinct digit becomes a node, and an edge from X to Y means "X must precede Y". A <a class="reference-source" href="https://en.wikipedia.org/wiki/Topological_sorting" rel="noopener noreferrer" target="_blank">topological sort</a> linearises the nodes so that every edge points forward, which is exactly the passcode I want. Because every login succeeded, the facts cannot contradict each other - the graph has no cycles - so a valid ordering is guaranteed to exist. With at most ten distinct decimal digits and fifty logins of length three, the <a class="reference-source" href="https://en.wikipedia.org/wiki/Directed_acyclic_graph" rel="noopener noreferrer" target="_blank">DAG</a> has at most ten nodes and a handful of distinct edges. The work is <a class="reference-source" href="https://en.wikipedia.org/wiki/Time_complexity" rel="noopener noreferrer" target="_blank">O(D^2)</a> in the number of distinct digits D, which is effectively constant here.
</p>
<h3>Solution Approach</h3>
<h4>Reverse Topological Sort by Repeated Sink Removal</h4>
<p>
Both the Python and C solutions implement the same algorithm. I chose repeated sink removal because it maps cleanly onto the constraint structure and is straightforward to reason about and verify.
</p>
<p>
<strong>Step 1 - Parse and deduplicate.</strong> I read the keylog, split it into lines, and discard duplicates. Seeing the same login twice contributes no new ordering information, so removing duplicates early keeps the inner loops lean. Python uses a <code>set</code> of strings, which deduplicates for free. The C version scans the lines already seen with <code>strcmp</code> - linear, but acceptable because the line count is bounded by a small constant (<code>MAX_LINES = 200</code>).
</p>
<p>
<strong>Step 2 - Build the successor graph.</strong> For each login and each consecutive pair at positions <code>(i, i+1)</code>, I record that the character at <code>i</code> must precede the character at <code>i+1</code>. I store this as a <em>successor set</em>: for each digit, the set of digits that must follow it. Python uses a <code>dict</code> mapping each character to a <code>set</code> of successors. C uses a <a class="reference-source" href="https://en.wikipedia.org/wiki/Bit_array" rel="noopener noreferrer" target="_blank">bitmask</a> array: <code>successor[i]</code> is an unsigned integer whose bit <em>j</em> is set when digit <em>j</em> must follow digit <em>i</em>. Both versions derive the number of consecutive pairs from <code>asked_characters - 1</code>, so the same code generalises beyond exactly three characters per login.
</p>
<p>
<strong>Step 3 - Repeatedly remove a sink.</strong> A <em>sink</em> is a node with no remaining successors among the digits not yet placed. Such a node can safely sit furthest to the right of whatever ordering I build, because nothing still active must come after it. I find a sink, prepend it to the result string, then deactivate it and strip it from every other node's successor set. This is <a class="reference-source" href="https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm" rel="noopener noreferrer" target="_blank">Kahn's algorithm</a> run sink-first rather than source-first; prepending each removed sink naturally yields the passcode in left-to-right order. In Python, the loop scans the dictionary for a key whose successor set is empty and uses a <a class="reference-source" href="https://docs.python.org/3/tutorial/controlflow.html#break-and-continue-statements-and-else-clauses-on-loops" rel="noopener noreferrer" target="_blank">for/else</a> to detect the impossible cycle case. In C, I build an <code>active_mask</code> of all still-active nodes and look for an <code>i</code> where <code>successor[i] &amp; active_mask</code> is zero - a single <a class="reference-source" href="https://en.wikipedia.org/wiki/Bitwise_operation" rel="noopener noreferrer" target="_blank">bitwise AND</a> tells me whether any active successor remains.
</p>
<p>
<strong>Language differences.</strong> The Python solution is concise and reads almost like the algorithm description, thanks to <code>dict</code> and <code>set</code>. The C solution is more verbose but turns the "any active successor?" test into one <a class="reference-source" href="https://en.wikipedia.org/wiki/Bitwise_operation" rel="noopener noreferrer" target="_blank">bitwise</a> operation and avoids dynamic allocation entirely. Both finish in negligible time and return the same answer, <code>73162890</code>.
</p>
</article>