notes.html

problem 61 · 33 lines

<article>
<h3>Problem Analysis</h3>
<p>
    The surface of this problem is number theory: <a class="reference-source" href="https://en.wikipedia.org/wiki/Polygonal_number" rel="noopener noreferrer" target="_blank">figurate (polygonal) numbers</a> generated by simple closed-form formulas such as the triangle numbers <code>n(n+1)/2</code> and the octagonal numbers <code>n(3n-2)</code>. But the real structure is combinatorial. I need an ordered set of six 4-digit numbers, one drawn from each of six polygon families, in which the last two digits of each number equal the first two digits of the next, and the chain closes back on itself. The phrase "last two digits link to the first two digits" is the decisive clue: this is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Graph_theory" rel="noopener noreferrer" target="_blank">graph</a> problem in disguise. If I treat each 4-digit figurate number as a node and draw a directed edge from A to B whenever <code>A mod 100 == B div 100</code>, then a valid answer is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Cycle_(graph_theory)" rel="noopener noreferrer" target="_blank">cycle</a> of length six in this graph whose members collectively cover all six polygon types.
  </p>
<p>
    Two observations make the problem tractable. First, the candidate set is tiny: each family contributes only a few dozen values between 1000 and 9999, so the whole graph has fewer than 200 nodes and the average out-degree (the number of successors per node) is small. Second, because each node carries one or more polygon-type labels and I want exactly one node per type, the search is naturally bounded to paths of length six. A <a class="reference-source" href="https://en.wikipedia.org/wiki/Depth-first_search" rel="noopener noreferrer" target="_blank">depth-first search</a> (DFS) that extends paths node by node, pruning when it would revisit a node, suffices. The worst-case bound is O(V<sup>L</sup>) for paths of length L in a graph of V nodes, but the short successor lists collapse this to a near-instant search in practice - the recorded times are 0.0009 s in C and 0.0233 s in Python on the full six-family case. The one subtlety that demands care is that some numbers belong to more than one polygon family (every <a class="reference-source" href="https://en.wikipedia.org/wiki/Hexagonal_number" rel="noopener noreferrer" target="_blank">hexagonal number</a> is also triangular, for instance), so the type-coverage check is not simply "six distinct types appear."
  </p>
<h3>Solution Approach</h3>
<h4>Graph-Based DFS with Polygon-Type Verification (C and Python)</h4>
<p>
    Both files implement the same algorithm. I describe it once and note the language-specific differences afterwards.
  </p>
<p>
<strong>Step 1 - generate figurate numbers.</strong> For each active polygon type I enumerate every 4-digit value its formula produces. In C I iterate <code>n</code> from 1, skip forward until the value reaches 1000, then collect values until they exceed 9999. In Python I do the same but seed the loop at the right index by inverting the formula: for triangle numbers, <code>P(n) = n(n+1)/2</code> inverts to <code>n = (-1 + sqrt(1+8P))/2</code>, so I begin the generator at the <a class="reference-source" href="https://en.wikipedia.org/wiki/Floor_and_ceiling_functions" rel="noopener noreferrer" target="_blank">floor</a> of that value rather than from 1. The ranges are so small that the inverse is a refinement of style rather than a necessity, but it is the principled way to start a <a class="reference-source" href="https://en.wikipedia.org/wiki/Monotonic_function" rel="noopener noreferrer" target="_blank">monotone</a> sequence at a threshold.
  </p>
<p>
<strong>Step 2 - build the successor graph.</strong> I collect all distinct 4-digit figurate values into a node list, then add a directed edge from node A to node B whenever <code>A % 100 == B / 100</code>. I additionally require the shared prefix to be at least 10: a two-digit prefix below 10 (like 05) cannot be the first two digits of a genuine 4-digit number, so those links would be spurious. C stores the graph as a fixed-size 2D array <code>successors[i][]</code> with a parallel <code>succ_counts[]</code> array; Python uses a <a class="reference-source" href="https://docs.python.org/3/library/stdtypes.html#dict" rel="noopener noreferrer" target="_blank">dict</a> mapping each number to a list of successors.
  </p>
<p>
<strong>Step 3 - DFS for closed cycles.</strong> Starting from every node in turn, I walk the graph <a class="reference-source" href="https://en.wikipedia.org/wiki/Depth-first_search" rel="noopener noreferrer" target="_blank">depth-first</a>, maintaining the current path and a visited marker. When the path reaches the target length I check whether the final node links back to the start (<code>cur % 100 == start / 100</code>); if so I have a closed <a class="reference-source" href="https://en.wikipedia.org/wiki/Cycle_(graph_theory)" rel="noopener noreferrer" target="_blank">cycle</a>. The visited marker guarantees all members of the path are distinct, which the problem requires. The marker is set on entry and cleared on exit - the standard <a class="reference-source" href="https://en.wikipedia.org/wiki/Backtracking" rel="noopener noreferrer" target="_blank">backtracking</a> discipline.
  </p>
<p>
<strong>Step 4 - verify type coverage.</strong> A candidate cycle is valid only if each polygon type is represented by exactly one member, accounting for numbers that belong to several families. My check first counts, for each type, how many cycle members belong to it, and rejects the cycle if any type has zero members. Then it builds the reverse map - for each cycle member, which types it belongs to - and flags a conflict if any multi-type number is the sole representative of every one of its types simultaneously (which would mean those types cannot all be filled). The C version expresses this with small explicit loops; the Python version builds two dictionaries (type-to-members and member-to-types) and applies the same test.
  </p>
<p>
<strong>Step 5 - deduplicate and report.</strong> Because the DFS starts from every node, the same unordered set is discovered once per starting point. I canonicalise each cycle by sorting its members, then store only unique sorted sets - Python uses a <a class="reference-source" href="https://docs.python.org/3/library/stdtypes.html#set" rel="noopener noreferrer" target="_blank">set</a> of sorted tuples for O(1) deduplication, while C sorts each candidate with an <a class="reference-source" href="https://en.wikipedia.org/wiki/Insertion_sort" rel="noopener noreferrer" target="_blank">insertion sort</a> and linearly scans previously stored results. The final output reports how many valid sets were found and their sums.
  </p>
<p>
<strong>Language differences.</strong> Python leans on <a class="reference-source" href="https://docs.python.org/3/glossary.html#term-generator" rel="noopener noreferrer" target="_blank">generators</a>, an <a class="reference-source" href="https://docs.python.org/3/library/enum.html" rel="noopener noreferrer" target="_blank">enum</a> for the polygon types, a <a class="reference-source" href="https://docs.python.org/3/glossary.html#term-decorator" rel="noopener noreferrer" target="_blank">decorator</a> for input validation, and dict/set comprehensions, all of which make the code expressive and self-documenting. C uses static arrays sized by <code>#define</code> constants and an array of <a class="reference-source" href="https://en.wikipedia.org/wiki/Function_pointer" rel="noopener noreferrer" target="_blank">function pointers</a> to drive a single generation loop over all six formulas. The algorithms are identical, so the roughly 25x speed gap (0.0009 s versus 0.0233 s on the main case) is pure interpreter overhead.
  </p>
</article>