Problem 86 — Cuboid Route

Problem Analysis

At its heart this is a piece of geometry 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 unfold 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 Pythagorean theorem. A cuboid with dimensions a, b, c admits three unfoldings, but if I impose the canonical ordering a >= b >= c (so a is the largest dimension), the minimal one always lays the two smaller faces side by side, giving a path length of sqrt(a^2 + (b + c)^2). This ordering simultaneously discharges the "ignoring rotations" requirement, because each distinct cuboid maps to exactly one unordered triple.

The task then reduces to counting integer triples (a, b, c) with a >= b >= c >= 1 for which a^2 + (b + c)^2 is a perfect square. The key efficiency observation is that the formula depends on b and c only through their sum s = b + c. So rather than looping over both, I fix a, loop over s from 1 to 2a, test whether a^2 + s^2 is a perfect square once per value of s, and then count - in constant time - how many (b, c) pairs sum to s 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.

Solution Approach

Unfolding plus sum-substitution counting (Python and C)

Both files implement the identical algorithm; only the language idiom differs. The structure has three parts.

Outer loop with no fixed bound. I iterate a from 1 upward indefinitely - itertools.count(1) in Python, an open for (int a = 1; ; a++) in C. Since every new value of a 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 M.

Inner loop over the sum. For each a I loop b_plus_c (my name for s = b + c) from 1 to 2a. The lower bound is 1 because b and c are each at least 1; the upper bound is 2a because each is at most a. I test whether a^2 + s^2 is a perfect square. In Python I write math.sqrt(a**2 + b_plus_c**2).is_integer(); in C I compute the square root, round to the nearest integer with (long long)(sq + 0.5), and verify by squaring back with isq * isq == (long long)val.

Closed-form pair counting. When the square test passes, I count the pairs (b, c) with b >= c >= 1, b <= a, and b + c = s. The condition b >= c >= 1 lets c range from 1 to floor(s/2). The extra cap b <= a means s - c <= a, i.e. c >= s - a. This splits into two cases:

• If s <= a + 1, the constraint c >= s - a is no stronger than c >= 1, so the count is simply floor(s/2).
• If s > a + 1, the binding lower bound is c >= s - a, giving floor(s/2) - (s - a) + 1 = floor((2a - s + 2) / 2) pairs.

I add this count to a running accumulator and return a when the accumulator first meets or exceeds target_solutions. In code this is the b_plus_c <= a + 1 branch yielding b_plus_c / 2 versus the (2 * a - b_plus_c + 2) / 2 branch.

The only real difference between the two files is the perfect-square test: Python's is_integer() is the most readable form available, while C uses the classic round(sqrt(n))-then-square pattern. Both are safe because the largest value involved stays below roughly 6.6 million, far inside the exact-integer range of double-precision floating point.