notes.html

problem 68 · 27 lines

<article>
<h3>Problem Analysis</h3>
<p>
A "magic" n-gon ring is a small <a class="reference-source" href="https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)" rel="noopener noreferrer" target="_blank">graph</a> built from two layers of nodes. The inner layer is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Cycle_(graph_theory)" rel="noopener noreferrer" target="_blank">cycle</a> of n nodes, each connected to its two neighbours; the outer layer attaches one external node to each inner node. A "line" of the ring is a triple - an outer node, the inner node it hangs off, and the next inner node clockwise. I fill the 2n positions with the integers 1 to 2n and require that all n lines share a common sum S, the magic total. For n = 5 the goal is the lexicographically largest 16-digit string formed by concatenating the lines, starting from the line whose outer node is smallest (a canonical start that removes rotational ambiguity).
</p>
<p>
The first key observation is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Counting" rel="noopener noreferrer" target="_blank">counting</a> identity. Each outer node belongs to exactly one line, while each inner node is shared between two lines (it is the second node of one line and the first node of the next). Summing all n lines gives n*S = (sum of outer nodes) + 2*(sum of inner nodes). Since 1 + 2 + ... + 2n is fixed, choosing which n numbers form the inner ring already fixes S. The second observation is more powerful still: once the inner ring <a class="reference-source" href="https://en.wikipedia.org/wiki/Permutation" rel="noopener noreferrer" target="_blank">permutation</a> is fixed and I pin the smallest outer node at the first position, every other outer value is forced by outer[i] = S - inner[i] - inner[i+1]. I never search the outer positions at all - I compute them. This collapses an exponential search over all 2n positions into a permutation enumeration over only the n inner positions, with a cheap O(n) check per candidate. A final structural insight specific to the 16-digit requirement: 10 is the only two-digit value in 1..10, and an inner node contributes to two lines (so a 10 inside would add two digits twice), whereas an outer node contributes once. To get exactly 16 digits rather than 17, 10 must sit on an outer node, so the inner ring is drawn only from {1, ..., 9}. The resulting complexity is O(P(min(9, 2n), n) * n), which for n = 5 is at most P(9, 5) = 15120 candidates - trivially fast.
</p>
<h3>Solution Approach</h3>
<h4>Inner-ring Enumeration with Forced Outer Values</h4>
<p>
Both files implement the same algorithm. The Python version is iterative, driven by <a class="reference-source" href="https://docs.python.org/3/library/itertools.html#itertools.permutations" rel="noopener noreferrer" target="_blank">itertools.permutations</a>; the C version is a recursive <a class="reference-source" href="https://en.wikipedia.org/wiki/Backtracking" rel="noopener noreferrer" target="_blank">backtracking</a> search. The four logical steps are identical.
</p>
<p>
<strong>Step 1 - Enumerate inner ring permutations.</strong> I generate all ordered arrangements of n values chosen from {1, ..., min(9, 2n)}. The cap of 9 encodes the "10 belongs on the outside" constraint that yields a 16-digit result for n = 5; using <code>min(9, 2n)</code> keeps the code correct for the smaller dev cases (n = 3, 4), where the cap is irrelevant, and for the larger extra cases. In C, <code>solve_recursive</code> fills <code>inner_choice[depth]</code> with each unused value, marks it in the <code>used</code> direct-address array, recurses, and unmarks on the way back out.
</p>
<p>
<strong>Step 2 - Compute and validate adjacent inner sums.</strong> For a candidate inner ring I compute the n sums s[k] = inner[k] + inner[(k+1) mod n]. These are the inner contribution of each line. If any two sums coincide, the corresponding outer values would collide - two lines would demand the same outer node - so I reject the candidate immediately. Python uses <code>len(set(inner_sums)) != n</code>; C uses a nested loop comparison. Rejecting early here keeps the inner loop tight.
</p>
<p>
<strong>Step 3 - Force the outer values.</strong> I place the smallest still-available number at outer position 0, canonicalising the clockwise start exactly as the problem requires. The magic total becomes S = outer[0] + s[0]. Every remaining outer value is then forced: outer[i] = S - s[i]. I check each forced value is in range and still available; the first failure aborts the candidate. This is the heart of the algorithm - the outer ring is computed, never searched.
</p>
<p>
<strong>Step 4 - Build and compare the string.</strong> A valid arrangement is concatenated line by line into a digit string and compared with the running best. Python converts the string to an arbitrary-precision <a class="reference-source" href="https://docs.python.org/3/library/functions.html#int" rel="noopener noreferrer" target="_blank">int</a> and compares numerically. C compares with a custom <code>cmp_magic</code> that ranks by length first, then lexicographically - equivalent to numeric comparison for equal-length non-negative integers, and free of overflow concerns.
</p>
</article>