Detailed mathematical approach

Problem Summary

We study equilateral pentagons with side length \(1\) that must move through a right-angled corridor of width \(W\). For such a pentagon let \(A\) be its area, and let \(W\) be the smallest corridor width that still allows a continuous motion from one straight branch of the corridor to the other.

The objective is to maximize

$\frac{A}{W^2}.$

This ratio is scale invariant: scaling the pentagon by a factor \(\lambda\) multiplies the area by \(\lambda^2\) and the required corridor width by \(\lambda\). So it is enough to work with unit-edge pentagons and optimize a normalized shape parameter.

Mathematical Approach

The implementation solves the problem numerically but the geometry is highly structured. First it restricts to a symmetric one-parameter family of equilateral pentagons, then it computes the minimal corridor width for each candidate by sampling all orientations and testing whether those orientations form a continuous feasible passage around the corner.

Step 1: Reduce the pentagon to one angle

Symmetry about the perpendicular bisector of the first edge lets us place the first four visible vertices as

$v_0=(0,0),\qquad v_1=(1,0),\qquad v_2=(1+\cos a,\sin a),\qquad v_4=(-\cos a,\sin a).$

This already guarantees

$|v_1-v_0|=|v_2-v_1|=|v_0-v_4|=1.$

The only missing point is \(v_3\), which must satisfy

$|v_3-v_2|=|v_3-v_4|=1.$

So the entire symmetric equilateral pentagon is controlled by the single angle parameter \(a\).

Step 2: Recover the fifth vertex from two unit circles

The distance between the two circle centers is

$d=|v_2-v_4|=1+2\cos a.$

For the two unit circles to intersect we need \(d\le 2\), hence this construction requires

$a\ge \frac{\pi}{3}.$

The midpoint of \(v_2v_4\) is \(\left(\frac12,\sin a\right)\), so the two possible intersection points are

$v_3=\left(\frac12,\sin a \pm \sqrt{1-\frac{d^2}{4}}\right).$

These are the two mirror candidates examined by the implementation. For each candidate, the area is computed with the shoelace formula

$A=\frac12\left|\sum_{i=0}^{4}\left(x_i y_{i+1}-x_{i+1} y_i\right)\right|,$

with indices taken cyclically.

Step 3: Translate the corridor constraints into width profiles

Fix an orientation angle \(\theta\), rotate the pentagon by \(\theta\), and then translate the rotated coordinates so that the minimum \(x\)-coordinate and minimum \(y\)-coordinate are both \(0\). For the translated polygon \(P_\theta\), define

$w_x(\theta)=x_{\max}-x_{\min},\qquad w_y(\theta)=y_{\max}-y_{\min}.$

These are the widths needed for the pentagon to fit inside a straight vertical corridor and a straight horizontal corridor of width \(W\), respectively.

The corner constraint is different. In the translated picture, a right-angled corridor of width \(W\) occupies the union of the strips \(x\le W\) and \(y\le W\), so the forbidden region is the upper-right square where both coordinates exceed \(W\). Therefore the pentagon fits at the corner exactly when

$\max_{p\in P_\theta}\min(p_x,p_y)\le W.$

This motivates the corner-width functional

$w(\theta)=\max_{p\in P_\theta}\min(p_x,p_y).$

Step 4: Why only vertices and diagonal crossings matter

Along any edge segment of the polygon, the function \(\min(x,y)\) is piecewise linear. Away from the diagonal \(x=y\), it is simply one coordinate or the other. The only place where the active branch can switch is where the edge crosses the diagonal.

So the maximum value of \(\min(x,y)\) on the polygon boundary is attained either at a vertex or at a point where an edge meets the diagonal \(x=y\).

The implementation uses exactly that fact: for every sampled orientation it checks all shifted vertices and all edge-diagonal intersections, and the largest such value becomes \(w(\theta)\).

Step 5: Turn continuous motion into connectivity on the angle circle

For a fixed corridor width \(W\), let

$S_W=\{\theta\in[0,2\pi): w(\theta)\le W\}.$

These are the orientations that can be placed at the corner. A continuous passage around the bend requires more than isolated feasible orientations. We need one connected arc of \(S_W\) that contains

an orientation with \(w_y(\theta)\le W\), so the pentagon can lie inside a straight horizontal branch, and

an orientation with \(w_x(\theta)\le W\), so it can lie inside a straight vertical branch.

Because orientation is periodic, the angle domain is a circle. The implementation samples that circle densely, sorts the samples by increasing \(w(\theta)\), activates them in threshold order, and merges neighboring active samples. Each connected component stores the smallest observed \(w_x\) and \(w_y\). The first threshold whose component satisfies both minima is the required motion width for that pentagon.

Worked Example: A concrete symmetric pentagon at \(a=\frac{\pi}{2}\)

Take

$a=\frac{\pi}{2}.$

Then

$v_0=(0,0),\qquad v_1=(1,0),\qquad v_2=(1,1),\qquad v_4=(0,1),$

and the two circle intersections are

$v_3=\left(\frac12,1\pm\frac{\sqrt3}{2}\right).$

Using the upper intersection gives a simple pentagon with area

$A=1+\frac{\sqrt3}{4}\approx 1.4330127.$

At orientation \(\theta=0\), the polygon is already translated with \(x_{\min}=y_{\min}=0\), so

$w_x(0)=1,\qquad w_y(0)=1+\frac{\sqrt3}{2},\qquad w(0)=1.$

This means the pentagon can sit at the corner of a width-\(1\) corridor, because no point has both coordinates larger than \(1\). But it does not fit completely inside a straight horizontal branch of width \(1\), since its vertical span exceeds \(1\). This is exactly why the algorithm tracks all three profiles \(w\), \(w_x\), and \(w_y\).

Step 6: Optimize the normalized objective

For each admissible \(a\), the implementation evaluates both mirror candidates, computes the corresponding minimal corridor width \(W(a)\), and keeps the larger value of

$F(a)=\frac{A(a)}{W(a)^2}.$

The search is one-dimensional, and within the narrow region containing the best symmetric pentagon the numerical profile is handled efficiently by a golden-section search.

How the Code Works

The C++ implementation precomputes a dense table of trigonometric values for equally spaced orientations around the full circle. For each candidate pentagon it rotates the five vertices at every sampled angle, shifts the pose so the lower-left touching position is normalized, and records the three geometric profiles \(w\), \(w_x\), and \(w_y\).

It then sorts the sampled orientations by the corner-width profile \(w\). As the threshold rises, neighboring active samples on the cyclic angle grid are merged with a disjoint-set structure. Each connected component remembers the smallest straight-corridor widths seen so far, so the first component with both \(w_x\le W\) and \(w_y\le W\) determines the motion width.

At the outer level, the implementation performs a golden-section search over the single angle parameter and evaluates both circle-intersection branches at each step. The final candidate is checked numerically to confirm that all five edges still have unit length and that the pentagon is simple. The Python and Java implementations delegate to the same compiled numerical core and return the parsed numeric result.

Complexity Analysis

Let \(N_\theta\) be the number of sampled orientations. For one pentagon, computing all rotated poses and the three width profiles costs \(O(N_\theta)\) geometric work because the polygon has only five vertices and five edges. Sorting the orientations by \(w\) costs

$O(N_\theta\log N_\theta),$

and the connectivity sweep with a disjoint-set structure is effectively linear, \(O(N_\theta \alpha(N_\theta))\).

So one motion-width evaluation is dominated by \(O(N_\theta\log N_\theta)\) time and \(O(N_\theta)\) memory. If the outer search uses \(T\) objective evaluations, the total cost is

$O(T\,N_\theta\log N_\theta).$

The C++ version parallelizes the per-angle geometry across hardware threads, which improves wall-clock time but does not change the asymptotic bound.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=667
2. Shoelace formula: Wikipedia - Shoelace formula
3. Moving sofa problem: Wikipedia - Moving sofa problem
4. Golden-section search: Wikipedia - Golden-section search
5. Disjoint-set data structure: Wikipedia - Disjoint-set data structure