Project Euler

Marsh Crossing

Frodo and Sam need to travel exactly 100 leagues due East from point A to point B. On normal terrain they can cover 10 leagues per day. A marsh runs exactly South-West to North-East, 50 leagues wid...

Source sync Apr 19, 2026

Problem #0607

Level Level 11

Solved By 1,957

Languages C++, Python

Answer 13.1265108586

Length 436 words

geometryoptimizationbrute_force

Frodo and Sam need to travel 100 leagues due East from point A to point B. On normal terrain, they can cover 10 leagues per day, and so the journey would take 10 days. However, their path is crossed by a long marsh which runs exactly South-West to North-East, and walking through the marsh will slow them down. The marsh is 50 leagues wide at all points, and the mid-point of AB is located in the middle of the marsh. A map of the region is shown in the diagram below:

Problem illustration

The marsh consists of 5 distinct regions, each 10 leagues across, as shown by the shading in the map. The strip closest to point A is relatively light marsh, and can be crossed at a speed of 9 leagues per day. However, each strip becomes progressively harder to navigate, the speeds going down to 8, 7, 6 and finally 5 leagues per day for the final region of marsh, before it ends and the terrain becomes easier again, with the speed going back to 10 leagues per day.

If Frodo and Sam were to head directly East for point B, they would travel exactly 100 leagues, and the journey would take approximately 13.4738 days. However, this time can be shortened if they deviate from the direct path.

Find the shortest possible time required to travel from point A to B, and give your answer in days, rounded to 10 decimal places.

Problem 607: Marsh Crossing

Mathematical Foundation

Theorem 1 (Snell’s Law for Optimal Traversal). Consider a path through $k$ parallel regions with speeds $v_1, v_2, \ldots, v_k$ , where boundaries are parallel lines. The time-optimal path satisfies

\frac{\sin\theta_1}{v_1} = \frac{\sin\theta_2}{v_2} = \cdots = \frac{\sin\theta_k}{v_k}

where $\theta_i$ is the angle between the path in region $i$ and the normal to the boundaries.

Proof. This is Fermat’s principle of least time applied to layered media. Consider two adjacent regions with speeds $v_i$ and $v_{i+1}$ separated by a boundary. Let the crossing point on the boundary be parameterized by $y$ . The total time through both regions is

T(y) = \frac{\sqrt{d_i^2 + (y - y_{\text{prev}})^2}}{v_i} + \frac{\sqrt{d_{i+1}^2 + (y_{\text{next}} - y)^2}}{v_{i+1}}

where $d_i$ is the perpendicular width of region $i$ . Setting $\frac{dT}{dy} = 0$ :

\frac{y - y_{\text{prev}}}{v_i \sqrt{d_i^2 + (y - y_{\text{prev}})^2}} = \frac{y_{\text{next}} - y}{v_{i+1}\sqrt{d_{i+1}^2 + (y_{\text{next}} - y)^2}}

which is precisely $\frac{\sin\theta_i}{v_i} = \frac{\sin\theta_{i+1}}{v_{i+1}}$ . This extends by induction to all consecutive pairs, yielding the global Snell condition at optimality. $\square$

Lemma 1 (Coordinate Setup). Rotate the coordinate system by $45°$ so the marsh boundaries become vertical lines. In the rotated frame:

$A = (-50/\sqrt{2},\; -50/\sqrt{2})$ , $B = (50/\sqrt{2},\; 50/\sqrt{2})$
Marsh boundaries at $x$ -coordinates: $-25/\sqrt{2}, -15/\sqrt{2}, -5/\sqrt{2}, 5/\sqrt{2}, 15/\sqrt{2}, 25/\sqrt{2}$
Speeds in the 7 regions (left to right): $v = (10, 9, 8, 7, 6, 5, 10)$

Proof. The marsh is oriented at $45°$ to the East-West direction, so rotation by $45°$ aligns boundaries with the $y$ -axis. The width of each strip perpendicular to the boundary is $10/\sqrt{2}$ in the rotated frame (since a 10-league strip at $45°$ has perpendicular width $10\cos 45° = 10/\sqrt{2}$ ). The total perpendicular marsh width is $50/\sqrt{2}$ , centered at the midpoint. $\square$

Theorem 2 (Optimization Formulation). The minimum time is

T^* = \min_{y_1, \ldots, y_6} \sum_{i=0}^{6} \frac{\sqrt{(\Delta x_i)^2 + (y_{i+1} - y_i)^2}}{v_i}

where $\Delta x_i = x_{i+1} - x_i$ are the known widths of each region, $y_0 = -50/\sqrt{2}$ , $y_7 = 50/\sqrt{2}$ , and $v_0 = v_6 = 10$ , $v_1 = 9$ , $v_2 = 8$ , $v_3 = 7$ , $v_4 = 6$ , $v_5 = 5$ .

This is a convex optimization problem in 6 variables (each term in the sum is convex in $y_i$ ), so any local minimum is the global minimum.

Proof. The function $f(y_i, y_{i+1}) = \sqrt{c^2 + (y_{i+1} - y_i)^2}/v_i$ is convex in $(y_i, y_{i+1})$ since it is a positive scaling of a Euclidean norm (which is convex). The sum of convex functions is convex. $\square$

Editorial

Minimize travel time through 7 regions with different speeds. Uses Snell’s law analogy and scipy optimization. The marsh runs SW-NE at 45 degrees. We parameterize by the height (y-coordinate) where the path crosses each marsh boundary. We rotated coordinates. We then objective function. Finally, minimize using gradient-based method (e.g., L-BFGS).

Pseudocode

Rotated coordinates
Objective function
Minimize using gradient-based method (e.g., L-BFGS)

Complexity Analysis

Time: $O(I \cdot 6)$ where $I$ is the number of iterations of the optimizer (typically $I \leq 1000$ ). Each function/gradient evaluation is $O(1)$ (6 terms). Total: effectively $O(1)$ .
Space: $O(1)$ (6 optimization variables, 7 region parameters).

Answer

\boxed{13.1265108586}

C++ project_euler/problem_607/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 607: Marsh Crossing
 *
 * Minimize travel time across 7 regions with different speeds.
 * The marsh runs SW-NE (at 45 degrees) crossing the east-west path AB.
 *
 * Key insight: The path through each constant-speed region is a straight line.
 * We parameterize by the y-offset at each of the 6 boundary crossings.
 *
 * The geometry: A and B are 100 leagues apart, due east.
 * The marsh is 50 leagues wide perpendicular to its extent (SW-NE).
 * The midpoint of AB is at the center of the marsh.
 *
 * In the rotated frame (45 deg), the marsh boundaries are vertical.
 * The perpendicular width of each strip is 10 leagues, so in the
 * rotated frame each strip has x-width = 10/sqrt(2).
 *
 * But we can also work directly: The path from A to B can be parameterized
 * by the perpendicular offsets at each marsh boundary.
 */

const double S2 = sqrt(2.0);
const double INF_VAL = 1e18;

// The marsh is perpendicular to its SW-NE direction.
// Width of each strip measured perpendicular to the marsh direction = 10 leagues
// In the east direction, the strip boundaries are at specific positions.
//
// Let's set up coordinates with A at origin, B at (100, 0).
// The marsh runs SW to NE. Its center passes through (50, 0).
// The marsh direction is at 45 degrees (NE direction): unit vector (1/sqrt2, 1/sqrt2)
// The perpendicular to the marsh: (1/sqrt2, -1/sqrt2)
//
// The marsh boundaries (perpendicular distance from center):
// -25, -15, -5, 5, 15, 25 leagues from center
// The center of the marsh is at point (50, 0).
//
// A point (x, y) has perpendicular distance to center:
// d = ((x-50)/sqrt2 - y/sqrt2) ... actually let's think more carefully.
//
// The marsh runs along direction (1,1)/sqrt2. Its perpendicular is (1,-1)/sqrt2.
// The signed perpendicular distance from (50,0) of point (x,y) is:
// d = ((x-50) - y) / sqrt(2)   [using normal (1,-1)/sqrt2]
//
// Wait, the perpendicular to (1,1) is (1,-1). So the signed distance is:
// d = ((x-50)*1 + (y-0)*(-1)) / sqrt(2) = (x - 50 - y) / sqrt(2)
//
// The marsh extends from d = -25 to d = 25.
// Strip boundaries at d = -25, -15, -5, 5, 15, 25.
//
// For the path, we parameterize by the position along the marsh direction
// at each boundary. Let t_i be the component along the marsh direction
// (1,1)/sqrt(2) at boundary i.
//
// At boundary i with perpendicular distance d_i from center:
//   x - 50 - y = d_i * sqrt(2)
//   x + y = t_i * sqrt(2)   (position along marsh)
// So x = 50 + (d_i + t_i)/sqrt(2) * sqrt(2)/2 ... let me just parameterize differently.
//
// Actually let's use the approach: parameterize by the y-coordinate where
// the path crosses each marsh boundary.
//
// Boundary i is the locus of points where (x - 50 - y)/sqrt(2) = d_i
// i.e., x = 50 + y + d_i * sqrt(2)
//
// For a crossing at height y, the x-coordinate is:
//   x = 50 + y + d_i * sqrt(2)

double d_boundaries[6] = {-25, -15, -5, 5, 15, 25};
double speeds[7] = {10, 9, 8, 7, 6, 5, 10};

// Point A = (0, 0), point B = (100, 0)
// Crossing boundary i at height h_i means point (50 + h_i + d_i*sqrt(2), h_i)
// But A is at perpendicular distance (0 - 50 - 0)/sqrt(2) = -50/sqrt(2) ≈ -35.36
// which is < -25, so A is before the marsh. Good.
// B is at perpendicular distance (100 - 50 - 0)/sqrt(2) = 50/sqrt(2) ≈ 35.36
// which is > 25, so B is after the marsh. Good.

double compute_time(double h[6]) {
    // Compute points: A, boundary crossings, B
    // A = (0, 0)
    // Boundary i crossing at height h[i]: position = (50 + h[i] + d_boundaries[i]*S2, h[i])
    // B = (100, 0)

    double px[8], py[8];
    px[0] = 0; py[0] = 0;  // A
    for (int i = 0; i < 6; i++) {
        px[i+1] = 50.0 + h[i] + d_boundaries[i] * S2;
        py[i+1] = h[i];
    }
    px[7] = 100.0; py[7] = 0;  // B

    double total = 0;
    for (int i = 0; i < 7; i++) {
        double dx = px[i+1] - px[i];
        double dy = py[i+1] - py[i];
        double dist = sqrt(dx*dx + dy*dy);
        total += dist / speeds[i];
    }
    return total;
}

int main() {
    // Optimize using gradient descent with adaptive step size
    double h[6];
    // Initialize to 0 (straight path)
    for (int i = 0; i < 6; i++) h[i] = 0;

    double lr = 0.1;
    double best_time = compute_time(h);

    for (int outer = 0; outer < 100; outer++) {
        for (int iter = 0; iter < 100000; iter++) {
            double grad[6];
            double eps = 1e-10;
            for (int i = 0; i < 6; i++) {
                h[i] += eps;
                double tp = compute_time(h);
                h[i] -= 2*eps;
                double tm = compute_time(h);
                h[i] += eps;
                grad[i] = (tp - tm) / (2*eps);
            }

            double h_new[6];
            for (int i = 0; i < 6; i++) {
                h_new[i] = h[i] - lr * grad[i];
            }
            double t_new = compute_time(h_new);

            if (t_new < best_time) {
                for (int i = 0; i < 6; i++) h[i] = h_new[i];
                best_time = t_new;
            } else {
                lr *= 0.5;
                if (lr < 1e-18) break;
            }
        }
        if (lr < 1e-18) break;
    }

    printf("%.10f\n", best_time);
    return 0;
}

Python project_euler/problem_607/solution.py

"""
Project Euler Problem 607: Marsh Crossing

Minimize travel time through 7 regions with different speeds.
Uses Snell's law analogy and scipy optimization.

The marsh runs SW-NE at 45 degrees. We parameterize by the
height (y-coordinate) where the path crosses each marsh boundary.
"""

import numpy as np
from scipy.optimize import minimize

S2 = np.sqrt(2.0)

# Perpendicular distances of boundaries from marsh center
d_boundaries = np.array([-25.0, -15.0, -5.0, 5.0, 15.0, 25.0])
speeds = np.array([10.0, 9.0, 8.0, 7.0, 6.0, 5.0, 10.0])

# A = (0, 0), B = (100, 0)
# Marsh center at (50, 0)
# Perpendicular distance of point (x,y) from center = (x - 50 - y) / sqrt(2)
# Boundary i: x - 50 - y = d_i * sqrt(2), so x = 50 + y + d_i * sqrt(2)

def total_time(h):
    """Compute total travel time given y-coordinates at 6 boundaries."""
    px = np.zeros(8)
    py = np.zeros(8)
    px[0], py[0] = 0.0, 0.0   # A
    px[7], py[7] = 100.0, 0.0  # B
    for i in range(6):
        px[i+1] = 50.0 + h[i] + d_boundaries[i] * S2
        py[i+1] = h[i]

    total = 0.0
    for i in range(7):
        dx = px[i+1] - px[i]
        dy = py[i+1] - py[i]
        dist = np.sqrt(dx**2 + dy**2)
        total += dist / speeds[i]
    return total

# Initial guess: straight path (all h = 0)
h_init = np.zeros(6)

# Use multiple optimizers for precision
result = minimize(total_time, h_init, method='Nelder-Mead',
                  options={'xatol': 1e-15, 'fatol': 1e-15, 'maxiter': 10000000, 'adaptive': True})

result = minimize(total_time, result.x, method='Powell',
                  options={'xtol': 1e-15, 'ftol': 1e-15, 'maxiter': 10000000})

result = minimize(total_time, result.x, method='Nelder-Mead',
                  options={'xatol': 1e-15, 'fatol': 1e-15, 'maxiter': 10000000, 'adaptive': True})

print(f"{result.fun:.10f}")