Plan a commuter rail network that maximises the operator's balance

You are the network-planning engine for a startup rail operator dropped into a brand-new city. The city is a 50 x 50 grid of blocks. Thousands of residents each commute from a home block to a workplace block, and every commute you manage to serve pays a fare proportional to how far that person travels. You start with a fixed cash reserve and a fixed horizon of T = 800 planning steps. Each step you may lay one length of track, build one station, or wait and let the fares roll in — but you can never let the balance go negative. Your job is to decide what to build, where, and when so that the cash on hand at the end of the horizon is as large as possible.

The tension is pure capital budgeting under a network effect. A station costs a lot (5000) and reaches every commuter endpoint within a Manhattan radius of 2, so a single well-placed station can feed many commuters; track is cheap (100) but only chains two neighbours together. Fares only start flowing once a home and a workplace are both within reach of stations that sit in the same connected rail component, so early spend is an investment that pays back over the remaining turns. Spend too little and you leave fares on the table; spend too much too late and the horizon ends before the investment is recouped.

Hard Constraints

The city. An N x N grid, N = 50. Block (0,0) is the top-left; (i,j) is i blocks down and j blocks right. Every block is one of three states:

• Empty (the initial state of every block): connects to nothing.
• Rail: connects to at most two of its four orthogonal non-empty neighbours. There are six rail types, numbered by which two sides they join:

• Station: connects to all four orthogonal non-empty neighbours.

Two adjacent blocks are linked iff each one's piece "faces" the other: a station faces all four sides; a rail faces only the two sides of its type. Linked blocks form connected components.

Commuters. M residents live in the city (50 <= M <= 1600). Resident c has a home at (i_{c,s}, j_{c,s}) and a workplace at (i_{c,t}, j_{c,t}), with home-to-work Manhattan distance strictly greater than 4.

The game. You begin with K funds (11000 <= K <= 20000) and an all-empty grid, and play T = 800 turns. Each turn runs a build phase then a collect phase.

Build phase — choose exactly one action:

• Lay track: pick an empty block and set it to one of the six rail types. Costs 100.
• Build station: pick an empty or rail block and set it to a station (a station may upgrade an existing rail block). Costs 5000.
• Wait: do nothing. Costs 0.

An action is illegal — and makes the whole submission WA, forfeiting that case — if it would drop the balance below 0, lays track on a non-empty block, builds a station on a block that is already a station, or names an out-of-range block or rail type. The balance check happens before the collect phase.

Collect phase — every resident commutes simultaneously. Resident c pays a fare iff there exist two station blocks (i_p,j_p) and (i_q,j_q) such that:

• both blocks are stations, and they are in the same connected component (reachable through linked station/rail blocks),
• |i_{c,s} - i_p| + |j_{c,s} - j_p| <= 2 (a station within radius 2 of home),
• |i_{c,t} - i_q| + |j_{c,t} - j_q| <= 2 (a station within radius 2 of work).

When resident c pays, your balance increases by |i_{c,s} - i_{c,t}| + |j_{c,s} - j_{c,t}| (their home-to-work Manhattan distance). Fares are collected every turn for as long as the connection holds, so building earlier compounds.

Beyond the game rules:

• Submit an algorithm, not precomputed answers — the grader re-runs your code on instances you have never seen. Do not key on seeds or instance names.
• /app/methods/main/ is what gets graded. Keep the run.sh contract below.
• Each sealed case runs your run.sh under a wall-clock cap of 15 s. A crash, timeout, or a wrong number of action lines forfeits that case.
• There is no network at run time, on the workbench or in the grader. Python 3, g++ and a Rust toolchain are available in both; anything else you have to write yourself.

What You Have

• tools/in/ — 100 visible instances (seeds 0-99).
• tools/gen — the generator. Make more instances with ./tools/gen seeds.txt --dir=OUTDIR, one unsigned-64-bit seed per line. For local testing use seeds in 0..10000 only — the sealed grading seeds live far outside that range, so staying inside it keeps your practice set from colliding with the hidden set.
• tools/vis — the visualiser/judge, the same one the grader uses: ./tools/vis in.txt out.txt prints Score = <final balance> and writes a vis.html you can open.
• python3 selfcheck.py [N] — free and unlimited: runs your run.sh on the first N visible cases (default 100) and prints each case's raw score.
• methods/main/solution.py — a crude greedy starter, yours to rewrite or delete.

The instance arrives on stdin:

N M K T
i_{0,s} j_{0,s} i_{0,t} j_{0,t}
...
i_{M-1,s} j_{M-1,s} i_{M-1,t} j_{M-1,t}

N = 50, T = 800; the M lines give each resident's home then workplace.

What You Submit

Leave your best solver in methods/main/:

• run.sh (required): run once per test case as bash run.sh < instance.txt > out.txt. It must read one instance on stdin and write the T-line action list on stdout. Any language.
• build.sh (optional): if present, the grader runs it once before grading (e.g. to compile a C++ or Rust solver). Do your compilation here and have run.sh exec the built binary.

The action list on stdout is exactly T = 800 lines, one action per turn, in order:

• lay track: p i j (rail type 1..6 at block (i,j)),
• build station: 0 i j,
• wait: -1.

Outputting a number of actions other than T is WA. Lines beginning with # are treated as comments and ignored, so you may annotate freely.

There is no submit step and no per-attempt feedback. Work and self-check for as long as your run window allows, then leave your best run.sh in place.

How It Is Judged

The grader reruns your run.sh on 200 sealed instances you never see, drawn from the same generator, and scores each with the same visualiser. The absolute score of a case is your balance after turn T — higher is better; the visualiser reports Score = 0 for any invalid, incomplete, wrong-length or timed-out output. Scoring is per case and then aggregated, so a case you forfeit cannot be carried by a case you optimise.

How the raw balances map to the final reward is deliberately not disclosed — optimise the raw balance itself. The starter as shipped is the zero of that scale: submitted unchanged it scores 0.