Detailed mathematical approach

Problem Summary

The ant starts at \(A(0,1)\) and must reach \(B(d,1)\), where \(d\in 2\mathbb{Z}_{>0}\). Every move is a straight segment between lattice points, always going forward in \(x\). If a segment starts at height \(y_0\) and ends at height \(y_1\), then its speed is

$v=\begin{cases} y_0, & y_0=y_1,\\ \dfrac{y_1-y_0}{\ln y_1-\ln y_0}, & y_0\ne y_1. \end{cases}$

The objective is to minimize the total travel time; that minimum is denoted by \(F(d)\). The published checkpoints are \(F(4)=2.960516287\), \(F(10)=4.668187834\), and \(F(100)=9.217221972\). The real target is \(F(10000)\), so a brute-force search over all lattice paths is far too large.

Mathematical Approach

The implementations solve the problem on the left half of the picture first and then mirror that half-path. Write

$w=\frac d2.$

The task is therefore to understand good paths from \((0,1)\) to the vertical line \(x=w\), and then double the best half-cost.

Step 1: Rewrite Every Segment Cost

For one segment from \((x_0,y_0)\) to \((x_1,y_1)\), let

$\Delta x=x_1-x_0,\qquad \Delta y=y_1-y_0,\qquad L=\sqrt{(\Delta x)^2+(\Delta y)^2}.$

The travel time is \(L/v\). It is convenient to write it with a reciprocal-speed factor

$\psi(y_0,y_1)=\begin{cases} \dfrac1{y_0}, & y_0=y_1,\\[4pt] \dfrac{\ln y_1-\ln y_0}{y_1-y_0}, & y_0\ne y_1. \end{cases}$

Then every segment contributes

$\tau\bigl((x_0,y_0)\to(x_1,y_1)\bigr)=L\,\psi(y_0,y_1).$

When \(y_1\to y_0\), the second branch tends to \(1/y_0\), so the horizontal and non-horizontal cases fit together continuously. For \(y_0\ne y_1\), the speed is the logarithmic mean of \(y_0\) and \(y_1\), and \(\psi\) is its reciprocal.

Step 2: Use Symmetry and Work on a Half-Path

The endpoints \(A(0,1)\) and \(B(d,1)\) are symmetric with respect to the line \(x=w\). Reflecting a path in that line preserves Euclidean lengths and also preserves the pair of endpoint heights of every reflected segment, so it preserves travel time as well.

The C++, Python, and Java implementations therefore search for a left half-path from \((0,1)\) to some midpoint \((w,Y)\), then reflect it to obtain a full path from \(A\) to \(B\). Under that model,

$F(d)=2\min_{1\le Y\le w} D(w,Y),$

where \(D(x,y)\) denotes the minimum time to reach \((x,y)\) on the left half. The searched half-path is restricted to nondecreasing heights, so the reflected second half automatically supplies the matching descent back to \(y=1\).

Step 3: Dynamic Programming Recurrence

Set the base state

$D(0,1)=0.$

For every lattice point \((x,y)\) with \(0\le x\le w\) and \(1\le y\le w\), the half-path cost is obtained from an earlier point \((x_0,y_0)\) with \(x_0\le x\) and \(y_0\le y\):

$D(x,y)=\min_{\substack{0\le x_0\le x\\1\le y_0\le y}}\left(D(x_0,y_0)+\sqrt{(x-x_0)^2+(y-y_0)^2}\,\psi(y_0,y)\right).$

This is a shortest-path computation on an acyclic state graph: \(x\) never decreases, and on the searched half-path the height never decreases either. Any state on the boundary \(x=w\) is already a complete half-solution and yields the full candidate time \(2D(w,y)\).

Step 4: Worked Example for \(d=4\)

For \(d=4\), we have \(w=2\). A natural half-path is

$ (0,1)\to(1,2)\to(2,2). $

The first segment has length \(\sqrt2\) and reciprocal speed

$\psi(1,2)=\frac{\ln 2-\ln 1}{2-1}=\ln 2.$

So its time is \(\sqrt2\ln 2\). The second segment is horizontal at height \(2\), length \(1\), hence time \(1/2\). The half-cost is therefore

$D(2,2)=\sqrt2\ln 2+\frac12.$

Reflecting this half-path gives the full path

$ (0,1)\to(1,2)\to(2,2)\to(3,2)\to(4,1), $

and thus

$F(4)=2\left(\sqrt2\ln 2+\frac12\right)=2.9605162869\ldots,$

which matches the stated checkpoint \(2.960516287\). This is a useful small-scale example of the general recurrence.

Step 5: Why the Full DP Is Still Too Large

If we allowed every state \((x,y)\) to examine every predecessor \((x_0,y_0)\), then there would be \(O(w^2)\) states and up to \(O(w^2)\) predecessors per state. For \(d=10000\), we have \(w=5000\), so a literal implementation of the full recurrence would be far too slow.

The implementations therefore keep the same segment-cost formula and the same half-path DP idea, but prune the search to a narrow region where near-optimal states are expected to lie.

Step 6: Restrict the Search to a Reference Arc

The reference curve used by the implementations is the quarter-circle

$x_{\mathrm{arc}}(y)=w-\sqrt{w^2-y^2},\qquad 1\le y\le w,$

which is the left branch of the circle centered at \((w,0)\) with radius \(w\).

Only source states near that circle are expanded, namely those satisfying

$\left|\sqrt{(w-x_0)^2+y_0^2}-w\right|\le \varepsilon.$

For each target height \(y\), destination \(x\)-coordinates are restricted to a narrow horizontal band:

$\max\bigl(x_0,\ x_{\mathrm{arc}}(y)-W\bigr)\le x\le \min\bigl(w,\ x_{\mathrm{arc}}(y)+1\bigr).$

In the released implementations, the default values are \(W=30\) and \(\varepsilon=0.5\). This is not the unrestricted theoretical DP; it is a numerically guided pruning strategy. However, it reproduces all published checkpoints and is exactly the algorithm used by the C++, Python, and Java implementations.

How the Code Works

The C++, Python, and Java implementations allocate a table of best half-path times for all lattice states with \(0\le x\le w\) and \(1\le y\le w\). Every entry starts at infinity except the initial state \((0,1)\), whose cost is \(0\).

They then precompute two geometric ingredients: \(\ln y\) for each height \(y\), and the reference-arc position \(x_{\mathrm{arc}}(y)\). Precomputing logarithms is important because the reciprocal-speed factor is evaluated repeatedly for many pairs of heights.

Next, for each horizontal position \(x_0\), the implementation precomputes the heights \(y_0\) that lie inside the thin annulus around the reference circle. Those lattice points are treated as the expandable source states.

When one source state is expanded, the implementation sweeps through all target heights \(y\ge y_0\). For each such \(y\), it evaluates the reciprocal-speed factor once, computes the admissible horizontal band around the reference arc, and relaxes all destinations \((x,y)\) inside that band.

Whenever a relaxation reaches the boundary \(x=w\), the best half-answer seen so far is updated. After all source states have been processed, the final result returned is exactly twice that best half-cost, formatted to nine decimal places.

Complexity Analysis

Let \(w=d/2\), and let \(W\) be the horizontal band width. The unpruned monotone DP has \(O(w^2)\) states and \(O(w^2)\) predecessor checks per state, so its naive time complexity is \(O(w^4)\), with \(O(w^2)\) memory.

In the implemented version, the annulus around the reference circle has constant thickness, so it contains only \(O(w)\) relevant source states. Each expanded source considers \(O(wW)\) destination cells, because it scans all target heights and only a band of width \(O(W)\) in the horizontal direction. That gives a practical running cost of roughly \(O(w^2W)\), while memory remains \(O(w^2)\).

For the actual target \(d=10000\), we have \(w=5000\) and the default \(W=30\), which is why the pruned method is feasible whereas the unrestricted DP is not.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=460
2. Logarithmic mean: Wikipedia — Logarithmic mean
3. Dynamic programming: Wikipedia — Dynamic programming
4. Shortest path problem: Wikipedia — Shortest path problem
5. Circle: Wikipedia — Circle