The Endless Expanse

This is an experimental problem. You are expected to explore various aspects of the resources you are given before submitting a solution.

The Void is a Cartesian plane. Ships arrive one at a time, each with an origin and a destination. You place gates to reduce how far they travel.

A ship flies in straight lines at a cost equal to Euclidean distance.

A gate is an unordered pair of points ${a, b}$. A ship at either endpoint crosses instantly to the other at zero cost. Gates are bidirectional and shared: once placed, every later ship may use it, any number of times, in either direction.

Each ship takes the cheapest route from its origin to its destination given the gates standing when it departs. Flying straight is always available, so a ship never pays more than $|o - d|$.

Placing gate ${a, b}$ costs

$10 \cdot |a - b|$

charged immediately and permanently. Gates cannot be removed.

Total cost is

$\text{cost} = \sum_{\text{placed}} 10|a - b| ;+; \sum_{t} \text{travel}(n_t, W_t)$

where $W_t$ is the set of gates standing when ship $n_t$ departs. A ship that departed before you placed a gate does not benefit from it.

Ships $n_1, \ldots, n_T$ arrive in order:

At step $t$ you can see $n_t$ and $n_1 \ldots n_{t-1}$. You cannot see what comes next, and you are not told $T$. Attempting to reach unarrived ships raises LookaheadError.

This is what makes the problem hard. With the whole list visible up front it would be a static network design problem. Online, you must decide whether the traffic you have seen is a real pattern worth paying for, or noise. Place too early and you buy infrastructure for a pattern that is not there; place too late and the traffic that justified it has already paid full price.

$W = \emptyset$ is always legal and costs $\sum_t |o_t - d_t|$. Your score is percent saved against that baseline. Never do worse than it.

Some datasets contain no exploitable structure. On those the correct answer is to place nothing and save 0%. A strategy that finds patterns in noise loses money.

You do not need to detect this explicitly. A gate pays for itself only if the travel it saves across the ships still to come exceeds 10 × length. On structured traffic a real route clears that bar; on unstructured traffic no route ever does, because random endpoints generate no repeat demand. Enforce the payoff condition honestly and the right behavior follows on its own.

Ships are CSV: origin_x,origin_y,dest_x,dest_y, one row per ship, in arrival order. data/<name>/train_NN.csv is yours to study. data/<name>/test_NN.csv is what you are graded on.

There are four datasets. single has one heavy route between two clusters; crossing has several routes that cross; star routes everything through one hub; noise has no structure at all.

Regenerate with python main.py --write-data.

Put a Strategy subclass named MyStrategy, taking no constructor arguments, in submission.py, then click execute or submit. It prints SCORE <mean percent saved> and PASS if you pass.

• geometry.py — Point, Ship, Void, Strategy. The API.
• shortest_path.py — routing engine. You do not need to read it.
• main.py — data generation and grading.
• submission.py — your solution.
• starter.ipynb — scratch space.