Detailed mathematical approach

Problem Summary

The mountain is described by the height function

$ h(x,y)=\Bigl(5000-0.005(x^2+y^2+xy)+12.5(x+y)\Bigr)e^{-\left|10^{-6}(x^2+y^2)-0.0015(x+y)+0.7\right|}. $

We must travel from

$ A=(200,200)\qquad\text{to}\qquad B=(1400,1400) $

while obeying the rule that the route may never rise above the smallest possible pass height. Among all such valid routes, we want the shortest one.

The implementation therefore solves two problems in sequence:

1. find the minimum feasible ceiling height,

2. under that ceiling, find the shortest route.

Mathematical Approach

1. The Minimax Pass Height

For any continuous path \(\gamma\) from \(A\) to \(B\), define its ceiling cost by

$ C(\gamma)=\max_{p\in\gamma} h(p). $

The smallest mountain pass height is then

$ f_*=\min_{\gamma:A\to B} C(\gamma). $

This is not yet a shortest-path problem in the Euclidean sense. It is a bottleneck problem: we minimize the highest altitude touched by the route.

Only after \(f_*\) is known does the actual geometric shortest-path problem begin.

2. Discrete Approximation on a Grid

The code samples the square

$ [0,1600]\times[0,1600] $

on a regular grid with spacing grid-step. With the default setting grid-step = 1.0, this gives

$ n=1601 $

grid points on each axis.

At each grid point \((i\Delta,j\Delta)\), the program stores the sampled height

$ h(i\Delta,j\Delta). $

This replaces the continuous terrain by a finite graph whose vertices are grid samples and whose edges connect the four axis-adjacent neighbors.

The four-neighbor choice matters because the code is using the grid only to estimate topological connectivity under a height ceiling; diagonal moves are not needed for the minimax search itself.

3. Why Dijkstra Still Works for a Bottleneck Objective

For a grid path

$ v_0,v_1,\dots,v_t, $

the discrete bottleneck cost is

$ \max\bigl(h(v_0),h(v_1),\dots,h(v_t)\bigr). $

If the current best ceiling at a vertex is \(c\), and we step to a neighbor \(u\), the new ceiling becomes

$ c'=\max(c,h(u)). $

This update is monotone: extending a path never lowers its ceiling. That is exactly the property Dijkstra needs. Once a vertex leaves the priority queue with the smallest currently known ceiling, no later path can improve it.

So the routine minimax_height is a correct Dijkstra-style solver for the minimax problem, with relaxation rule

$ \text{best}[u]\leftarrow \min\bigl(\text{best}[u], \max(\text{best}[v],h(u))\bigr). $

The returned value is a grid approximation of the true continuous pass height \(f_*\).

4. From Pass Height to a Forbidden Region

Once \(f_*\) is known, define the forbidden set

$ \Omega=\{(x,y): h(x,y)>f_*\}. $

The allowed set is its complement

$ F=\{(x,y): h(x,y)\le f_*\}. $

Any valid route must lie entirely in \(F\). Therefore the shortest valid route is simply the shortest Euclidean path from \(A\) to \(B\) in the plane with the obstacle region \(\Omega\) removed.

The critical boundary is the contour

$ \partial\Omega=\{(x,y): h(x,y)=f_*\}. $

The whole second phase of the algorithm is about approximating this contour and then solving a shortest-path problem around it.

5. Why the Final Route Reduces to “Segment + Arc + Segment”

For a fixed obstacle with smooth or polygonal boundary, a shortest path in the free plane has a standard structure:

1. whenever the path is strictly inside free space, it is a straight line segment,

2. if it cannot remain straight because the obstacle blocks it, it touches the obstacle boundary,

3. while constrained by the obstacle, it follows the boundary, then leaves it along another straight visible segment.

So once the relevant contour loop is known, the shortest valid route must be one of these forms:

1. the direct segment \(AB\), if it stays below \(f_*\),

2. \(A\to P_i\), then an arc of the contour, then \(P_j\to B\), where \(P_i\) and \(P_j\) are visible contour points.

This is the geometric reason the code only scans visible contour-point pairs instead of searching arbitrary curved paths in the plane.

6. Extracting the Level Set with Marching Squares

The grid already tells us which sampled vertices are above the ceiling and which are below it. The code marks a sample as inside the forbidden region when

$ h(i\Delta,j\Delta)>f_*. $

Each grid cell has four corners, so there are \(2^4=16\) possible above/below patterns. The arrays kCaseCount and kCaseEdges are the usual marching-squares lookup tables for those 16 cases.

If an edge crosses the contour \(h=f_*\), the crossing point is approximated by linear interpolation. If an edge endpoint heights are \(h_1\) and \(h_2\), then the crossing fraction is

$ t=\frac{f_*-h_1}{h_2-h_1}, $

and the point is

$ P(t)=P_1+t(P_2-P_1). $

Cells of ambiguous type produce two contour segments; ordinary crossing cells produce one. Running over all cells produces a polygonal approximation of the level set \(h=f_*\).

7. Quantization, Adjacency, and Closed Loops

The interpolated segment endpoints are floating-point numbers. Two segments that should meet can differ by tiny roundoff noise, so the code quantizes each point with scale

$ 10^6. $

That means nearly coincident points are snapped to the same integer key.

The program then builds an adjacency map from these quantized keys. In an ideal simple contour, every contour vertex has degree 2. The code checks exactly that.

Next it walks the adjacency graph to recover closed loops. If several loops appear, the implementation keeps the loop with largest perimeter.

This is an implementation-level robustness choice: numerically extracted contours can split into several pieces, but the outer main obstacle loop is the one relevant for the shortest route around the mountain.

8. Arc Lengths Along the Contour

Once a single contour loop

$ P_0,P_1,\dots,P_{m-1} $

has been recovered, the code computes prefix arc lengths

$ S_0=0,\qquad S_{i+1}=S_i+|P_iP_{i+1}|, $

with indices taken cyclically. The total contour perimeter is

$ L=S_m. $

For two contour vertices \(P_i\) and \(P_j\), one arc has length

$ s_{ij}=|S_j-S_i|, $

and the opposite arc has length

$ L-s_{ij}. $

The shorter one is the relevant boundary-travel cost for that pair.

9. Visibility Testing from \(A\) and \(B\)

A contour point \(P_i\) is usable from \(A\) only if the straight segment \(AP_i\) stays under the ceiling. Since the code does not solve the exact intersection analytically, it checks visibility by sampling points along the segment with step size vis-step.

If any sampled point satisfies

$ h(x,y)>f_*+10^{-10}, $

then the segment is rejected.

This produces two visible-index sets:

$ V_A=\{i: A\text{ can see }P_i\},\qquad V_B=\{j: B\text{ can see }P_j\}. $

Only pairs from \(V_A\times V_B\) need to be examined.

10. Final Candidate Formula

For each visible pair \((i,j)\), the candidate route length is

$ |AP_i|+\min\bigl(s_{ij},\,L-s_{ij}\bigr)+|P_jB|. $

The code also checks the direct segment \(AB\) first. If it is visible under \(f_*\), then no bent route can beat it, because a straight segment is the shortest Euclidean connection between two points.

Otherwise, the minimum over all visible contour pairs is the program's approximation to the true shortest valid route.

11. Implementation Sanity Checks

The program validates several necessary conditions:

1. \(f_*\) cannot be below the heights of \(A\) or \(B\),

2. the contour must not be empty,

3. every contour node must have degree 2,

4. the final route cannot be shorter than the direct distance \(|AB|\).

With the default parameters, the endpoint heights are approximately

$ h(A)\approx 7851.540,\qquad h(B)\approx 6964.696. $

The straight segment from \(A\) to \(B\) reaches heights above

$ 13275, $

so it is not feasible at the optimal ceiling.

When run with --verbose, the program reports

$ f_*\approx 10396.458664, $

and with default discretization it prints the route length

$ 2531.205. $

These are code-level numerical outputs, not symbolic closed forms.

How the Code Works

compute_heights samples the height field on the grid, optionally in parallel. minimax_height then runs the priority-queue minimax search and returns the discrete pass height.

After that, the code marks grid vertices with height above \(f_*\), extracts contour segments cell by cell with marching squares, quantizes segment endpoints, builds an adjacency graph, walks it into loops, chooses the largest loop, and computes prefix arc lengths around that loop.

Next, it evaluates which contour points are visible from \(A\) and \(B\), checks the direct segment \(AB\), and finally scans all visible pairs with the formula

$ |AP_i|+\min\bigl(s_{ij},L-s_{ij}\bigr)+|P_jB|. $

The minimum of those candidates is printed to three decimal places.

Complexity Analysis

If the grid has \(n\) points on each axis, then height sampling costs \(O(n^2)\), the minimax Dijkstra pass costs \(O(n^2\log n)\), contour extraction costs \(O(n^2)\), and visibility checks cost

$ O(|V_A|+|V_B|)\times\text{sampling work} $

plus the final pair scan

$ O(|V_A||V_B|). $

Memory usage is \(O(n^2)\) because the sampled height field dominates storage.

The important tradeoff is numerical: smaller grid-step and vis-step improve the approximation to the continuous problem, but they increase runtime and memory consumption.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=262
2. Bottleneck / widest path problems: Wikipedia - widest path problem
3. Marching squares: Wikipedia - marching squares
4. Dijkstra's algorithm: Wikipedia - Dijkstra's algorithm
5. Shortest path among obstacles / visibility ideas: Wikipedia - visibility graph