Detailed mathematical approach

Problem Summary

The pipe has radius \(R=50\), and we must place one sphere of each integer radius \(30,31,\dots,50\) inside it. If the minimum possible pipe length is \(L\), the required output is \(\operatorname{round}(1000L)\).

There are \(21\) spheres, so a direct search over all \(21!\) orders is hopeless. The implementations therefore split the task into two parts: geometry, which gives the exact cost of putting two radii next to each other, and combinatorics, which chooses the best overall order.

Mathematical Approach

Once an order of radii is fixed, the best placement of the sphere centers is forced by the cylinder geometry. That turns the packing problem into a shortest-path problem on the set of radii.

Geometry of Two Consecutive Spheres

Take two consecutive spheres with radii \(a\) and \(b\) inside a pipe of radius \(R\). In a shortest arrangement each sphere is pushed against the wall, because moving a center farther from the axis can only increase the transverse separation and therefore reduce the required axial gap.

If the two centers sit on opposite sides of the pipe, their transverse separation is

$d_\perp=(R-a)+(R-b)=2R-a-b.$

The spheres are tangent, so the distance between their centers is \(a+b\). By the Pythagorean theorem, the needed separation along the pipe axis is

$d(a,b)=\sqrt{(a+b)^2-(2R-a-b)^2}=2\sqrt{R(a+b-R)}.$

This is exactly the quantity evaluated by the C++, Python, and Java implementations. For Problem 222, \(R=50\), so the formula becomes

$d(a,b)=10\sqrt{2(a+b-50)}.$

The important structural fact is that the pair cost depends only on the sum \(a+b\), and it is symmetric, increasing, and concave as that sum grows.

From an Ordering to the Total Pipe Length

Suppose the radii are arranged in the axial order

$r_1,r_2,\dots,r_n.$

If consecutive spheres alternate from one side of the pipe to the other, then the left end of the pipe is \(r_1\) units before the first center, the right end is \(r_n\) units after the last center, and each adjacent pair contributes one gap \(d(r_i,r_{i+1})\). Therefore

$L(r_1,\dots,r_n)=r_1+\sum_{i=1}^{n-1} d(r_i,r_{i+1})+r_n.$

Reversing the order leaves this expression unchanged, because the endpoint term becomes \(r_n+r_1\) and the same pair distances appear in the opposite direction.

Why the Two Largest Radii Are Treated as Endpoints

The pair cost \(d(a,b)\) is an increasing concave function of \(a+b\). That favors mixing large and small radii rather than paying two large adjacency costs next to the same interior sphere. Exchange arguments for concave pair costs push the larger radii outward, producing a pendulum-like optimal order whose two ends are the two largest radii.

This is the structural reduction used by the implementations: one optimal arrangement has \(49\) at one end and \(50\) at the other. Because reversing the entire order gives the same total length, it is enough to fix \(49\) as the first sphere and \(50\) as the final sphere, and optimize only the \(19\) radii \(30,31,\dots,48\) in between.

Exact Subset Recurrence

Let \(S\subseteq\{30,31,\dots,48\}\) be the set of interior radii that have not yet been placed, and let \(x\) be the radius of the current last sphere in the partially built chain. Define \(F(S,x)\) to be the minimum additional length needed to finish the arrangement and then append the final radius \(50\).

The terminal case is immediate:

$F(\varnothing,x)=d(x,50)+50.$

If \(S\neq\varnothing\), the next sphere can be any \(r\in S\), so

$F(S,x)=\min_{r\in S}\bigl(d(x,r)+F(S\setminus\{r\},r)\bigr).$

The full answer before the final multiplication by \(1000\) is therefore

$L_{\min}=49+F(\{30,31,\dots,48\},49).$

The recurrence is exact because the future depends only on two facts: which radii remain unused, and the radius currently sitting at the open end of the chain.

Worked Example: The Small Checkpoint Instance

The C++ implementation contains a tiny exhaustive check with pipe radius \(R=8\) and sphere radii \(5,6,7,8\). For that instance, the best order is

$7,5,6,8$

or its reversal \(8,6,5,7\). The three pair distances are

$d(7,5)=\sqrt{12^2-4^2}=8\sqrt{2},\qquad d(5,6)=\sqrt{11^2-5^2}=4\sqrt{6},\qquad d(6,8)=\sqrt{14^2-2^2}=8\sqrt{3}.$

Hence the total length is

$L=7+8+8\sqrt{2}+4\sqrt{6}+8\sqrt{3}\approx 49.9680739307.$

This small case already shows the same pattern as the full problem: the largest two radii sit at the ends, and the interior order alternates large and small values to keep the pair sums under control.

How the Code Works

The C++, Python, and Java implementations all evaluate the same recurrence. A state is encoded by a bitmask for the unused interior radii and by the radius currently sitting at the open end of the partial arrangement. From that state, the implementation tries every remaining radius, adds the geometric gap \(d(x,r)\), and memoizes the best continuation.

The search starts with \(49\) already fixed on the left, while \(50\) is reserved as the forced final sphere. When the mask becomes empty, the implementation closes the chain by adding the last gap to \(50\) and then the terminal contribution \(50\) itself. After the optimal real-valued length is found, each program returns \(\operatorname{round}(1000L)\).

The storage strategy differs slightly by language. The C++ and Java implementations use dense floating-point tables indexed by \((\text{mask},\text{last})\), which is efficient because removing \(49\) and \(50\) leaves a contiguous mask range of size \(2^{19}\). The Python implementation uses a dictionary keyed by the same logical state. The C++ version also compares the optimized solver against brute force on the four-sphere checkpoint instance described above.

Complexity Analysis

Let \(n=21\). Fixing the two endpoint spheres leaves \(n-2=19\) radii inside the subset mask. The number of memoized states is \(O(n2^{n-2})\), and each state examines up to \(O(n)\) next choices, so the running time is

$O(n^2 2^{n-2}).$

For Problem 222 this is easily manageable, whereas brute force would require evaluating \(21!\) different orders. The memory usage is

$O(n2^{n-2}),$

which in the array-based versions corresponds to about \(21\cdot 2^{19}\) floating-point entries plus small auxiliary overhead.

Footnotes and References

1. Problem page: Project Euler 222
2. Sphere packing: Wikipedia - Sphere packing
3. Pythagorean theorem: Wikipedia - Pythagorean theorem
4. Held-Karp style subset dynamic programming: Wikipedia - Held-Karp algorithm