notes.html
problem 86 · 26 lines
<article>
<h3>Problem Analysis</h3>
<p>
At its heart this is a piece of <a class="reference-source" href="https://en.wikipedia.org/wiki/Geometry" rel="noopener noreferrer" target="_blank">geometry</a> wrapped around a counting problem. A spider walking across the faces of a cuboid cannot travel through the interior, so the "straight line" distance is the shortest path constrained to the surface. The standard trick is to <a class="reference-source" href="https://en.wikipedia.org/wiki/Net_(polyhedron)" rel="noopener noreferrer" target="_blank">unfold</a> the cuboid: cut along an edge and rotate the two adjacent faces the path crosses until they lie flat in a single plane. Once flattened, the shortest surface path becomes an ordinary straight line, and its length follows directly from the <a class="reference-source" href="https://en.wikipedia.org/wiki/Pythagorean_theorem" rel="noopener noreferrer" target="_blank">Pythagorean theorem</a>. A cuboid with dimensions <code>a</code>, <code>b</code>, <code>c</code> admits three unfoldings, but if I impose the canonical ordering <code>a >= b >= c</code> (so <code>a</code> is the largest dimension), the minimal one always lays the two smaller faces side by side, giving a path length of <code>sqrt(a^2 + (b + c)^2)</code>. This ordering simultaneously discharges the "ignoring rotations" requirement, because each distinct cuboid maps to exactly one unordered triple.</p>
<p>
The task then reduces to counting integer triples <code>(a, b, c)</code> with <code>a >= b >= c >= 1</code> for which <code>a^2 + (b + c)^2</code> is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Square_number" rel="noopener noreferrer" target="_blank">perfect square</a>. The key efficiency observation is that the formula depends on <code>b</code> and <code>c</code> only through their sum <code>s = b + c</code>. So rather than looping over both, I fix <code>a</code>, loop over <code>s</code> from <code>1</code> to <code>2a</code>, test whether <code>a^2 + s^2</code> is a perfect square once per value of <code>s</code>, and then count - in constant time - how many <code>(b, c)</code> pairs sum to <code>s</code> under the constraints. This collapses what would be a three-nested-loop search into an O(M^2) scan in the answer M, with an early exit the instant the running count crosses the target.</p>
<h3>Solution Approach</h3>
<h4>Unfolding plus sum-substitution counting (Python and C)</h4>
<p>
Both files implement the identical algorithm; only the language idiom differs. The structure has three parts.</p>
<p>
<strong>Outer loop with no fixed bound.</strong> I iterate <code>a</code> from <code>1</code> upward indefinitely - <code>itertools.count(1)</code> in Python, an open <code>for (int a = 1; ; a++)</code> in C. Since every new value of <code>a</code> can only add to the running total, iterating in increasing order lets me return the answer the moment the threshold is reached, without ever needing to guess an upper bound for <code>M</code>.</p>
<p>
<strong>Inner loop over the sum.</strong> For each <code>a</code> I loop <code>b_plus_c</code> (my name for <code>s = b + c</code>) from <code>1</code> to <code>2a</code>. The lower bound is <code>1</code> because <code>b</code> and <code>c</code> are each at least <code>1</code>; the upper bound is <code>2a</code> because each is at most <code>a</code>. I test whether <code>a^2 + s^2</code> is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Square_number" rel="noopener noreferrer" target="_blank">perfect square</a>. In Python I write <code>math.sqrt(a**2 + b_plus_c**2).is_integer()</code>; in C I compute the square root, round to the nearest integer with <code>(long long)(sq + 0.5)</code>, and verify by squaring back with <code>isq * isq == (long long)val</code>.</p>
<p>
<strong>Closed-form pair counting.</strong> When the square test passes, I count the pairs <code>(b, c)</code> with <code>b >= c >= 1</code>, <code>b <= a</code>, and <code>b + c = s</code>. The condition <code>b >= c >= 1</code> lets <code>c</code> range from <code>1</code> to <code>floor(s/2)</code>. The extra cap <code>b <= a</code> means <code>s - c <= a</code>, i.e. <code>c >= s - a</code>. This splits into two cases:</p>
<ul>
<li>If <code>s <= a + 1</code>, the constraint <code>c >= s - a</code> is no stronger than <code>c >= 1</code>, so the count is simply <code>floor(s/2)</code>.</li>
<li>If <code>s > a + 1</code>, the binding lower bound is <code>c >= s - a</code>, giving <code>floor(s/2) - (s - a) + 1 = floor((2a - s + 2) / 2)</code> pairs.</li>
</ul>
<p>
I add this count to a running accumulator and return <code>a</code> when the accumulator first meets or exceeds <code>target_solutions</code>. In code this is the <code>b_plus_c <= a + 1</code> branch yielding <code>b_plus_c / 2</code> versus the <code>(2 * a - b_plus_c + 2) / 2</code> branch.</p>
<p>
The only real difference between the two files is the perfect-square test: Python's <code>is_integer()</code> is the most readable form available, while C uses the classic <code>round(sqrt(n))</code>-then-square pattern. Both are safe because the largest value involved stays below roughly <code>6.6</code> million, far inside the exact-integer range of <a class="reference-source" href="https://en.wikipedia.org/wiki/Double-precision_floating-point_format" rel="noopener noreferrer" target="_blank">double-precision floating point</a>.</p>
</article>