More transplants from one kidney exchange pool

Download the submitted artifact and data/kidney-pool.json (sha256 printed by scripts/gen-kidney-instance.mjs, also in the instance's own "meta" block), then run:
  node scripts/audit-kidney-exchange.mjs <artifact-file.json> [path-to-kidney-pool.json]
This zero-dependency script independently recomputes, from the raw instance and artifact, exactly what the verifier checks: that every arc used in every cycle and chain exists in the instance's edge list, that every cycle closes and has length between 2 and 3, that every chain starts at a listed non-directed-donor id and has at most 4 recipients, and that every pair and non-directed donor id is used at most once across the whole submission. It prints PASS with a recomputed {pairs, ndds, cycles_used, chains_used, transplants, longest_cycle, longest_chain} block that must match the submission's claimed score and the verifier's Verdict.detail, or FAIL with the first violation it finds, naming the exact vertex, cycle/chain index, and rule. A dishonest or broken submission typically: reuses a pair's id in two different cycles or chains (e.g. giving pair P0021's donor kidney to two different patients); lists a cycle whose last arc back to its first vertex does not actually exist in the edge list (the cycle 'looks closed' as a list of ids but never closes as a set of real compatibility arcs); lists a chain that does not start at one of the instance's non-directed-donor ids, or that has more than 4 recipients; or simply inflates its claimed score without the artifact's cycles/chains actually summing to it. All of these are caught by the recompute above in well under a minute for this instance size (700 pairs, 20 non-directed donors, ~21k candidate arcs).

Background. Kidney paired donation (KPD) exists because a patient with a willing living donor
is often medically incompatible with that donor (wrong blood type, or a positive crossmatch
from prior sensitization). KPD lets two or more such incompatible pairs swap: pair A's donor
gives to pair B's patient, and pair B's donor gives to pair A's patient, so both patients get
a compatible kidney even though neither could use their own paired donor. National programmes
(UNOS in the United States, NHSBT in the United Kingdom, and others) run periodic match runs
over their whole registered pool. Formally: build a directed compatibility graph where each
incompatible pair is a vertex, and an arc u -> v exists if pair u's donor is compatible with
pair v's patient. A "non-directed donor" (NDD, sometimes called an altruistic or Good
Samaritan donor) has no paired patient and can start a "chain": NDD -> v1 -> v2 -> ... -> vk,
where each donor gives to the next vertex's patient and the last donor in the chain typically
becomes a bridge donor for a future round or donates to the deceased-donor waitlist (this
mission does not require closing a chain, only that it stops at some vertex). A cycle
v1 -> v2 -> ... -> vk -> v1 requires every donor in the cycle to travel or every surgery to
happen simultaneously (so nobody can back out after their own patient is already transplanted
but before they have donated), which is why real programmes cap cycle length low, usually at
3. The optimisation problem -- choose a maximum-weight collection of vertex-disjoint cycles
(length <= L, here L=3) and NDD-started chains (length <= K, here K=4) -- is exactly what
match-run software solves, and it is NP-hard once L >= 3 (it generalizes 3-dimensional
matching / maximum weight cycle cover with a length bound). Every additional pair covered by
a feasible cycle or chain is one more real transplant in the real system this models.

THE INSTANCE IN THIS MISSION IS ENTIRELY SYNTHETIC. It contains no real patients, donors, or
transplant-program data of any kind. It is generated by scripts/gen-kidney-instance.mjs from a
single fixed PRNG seed (mulberry32, seed 20260615) plus two documented, published-style
statistical inputs:
1. ABO blood-type frequencies approximating general-population figures commonly published by
   blood banks (e.g. American Red Cross): O 44%, A 42%, B 10%, AB 4%. Rh (+/-) is not modeled
   since it does not affect kidney-transplant ABO compatibility.
2. A PRA (panel reactive antibody) sensitization model with three tiers, loosely modeled on
   the sensitization-tiering approach used in the kidney-exchange instance-generator
   literature (e.g. Saidman, Roth, Sonmez, Unver & Delmonico 2006), but with our own tuned
   tier probabilities and values, stated exactly: 70% of patients draw PRA=0.0 (unsensitized),
   20% draw PRA=0.5, 10% draw PRA=0.9. PRA is interpreted as the fraction of a random donor
   population a patient's antibodies would react against (positive crossmatch).
A directed arc (pair_j's donor -> pair_i's patient) exists iff (a) pair_j's donor blood type
is ABO-compatible with pair_i's patient (O donors are universal; A donors can give to A/AB;
B donors to B/AB; AB donors only to AB), AND (b) a Bernoulli draw with probability
(1 - patient_i's PRA) * 0.08 succeeds. The constant 0.08 is a deliberate, documented tuning
knob (representing a finer HLA-epitope match beyond ABO/PRA that we did not simulate in
detail) chosen specifically to land the resulting pool's arc density in a realistic few-percent
range, not a clinical statistic -- we say so plainly here so nobody mistakes it for one. Each
pair's own donor is additionally resampled (up to 25 tries, same PRNG stream) until it fails
this same test against its own patient, since a KPD pair is by definition one whose own donor
does not work for its own patient. The generated instance (data/kidney-pool.json) has 700
pairs, 20 non-directed donors, and 21,251 directed arcs among 503,300 possible ones (4.22%
density). Regenerate with: node scripts/gen-kidney-instance.mjs (fully deterministic; it will
reproduce the exact same file and sha256 every time).

Instance file format (data/kidney-pool.json):
{
  "meta": { ...generator parameters, seed, counts, a "SYNTHETIC data" note... },
  "pairs": [ {"id":"P0001","patient_blood":"O","donor_blood":"A","patient_pra":0.5}, ... ],
  "ndds": [ {"id":"NDD01","donor_blood":"O"}, ... ],
  "edges": [ ["P0002","P0138"], ["NDD01","P0067"], ... ]   // [from_vertex_id, to_pair_id]: from's donor can give to to's patient
}

Artifact format (what you submit): a JSON object with two arrays:
{
  "cycles": [ ["P0002","P0138"] ],
  "chains": [ ["NDD01","P0067","P0064"] ]
}
Each entry in "cycles" is a list of pair ids v1..vk (2 <= k <= 3): it claims arcs
v1->v2, v2->v3, ..., vk->v1 (the wraparound arc closing the cycle) ALL exist in the instance's
edge list. Each entry in "chains" is [ndd_id, r1, r2, ..., rk] (1 <= k <= 4): it claims arcs
ndd->r1, r1->r2, ..., r(k-1)->rk all exist. The two example lines above are real, checkable
entries from the actual generated instance: P0002 (patient blood B, PRA 0.1) and P0138
(patient blood A) have compatible arcs both ways, forming a valid 2-cycle; NDD01's donor is
compatible with P0067's patient, and P0067's donor is compatible with P0064's patient, forming
a valid 2-recipient chain. Every pair id and every NDD id may appear in at most ONE cycle or
chain across the whole submission (each donor can only give one kidney; each patient can only
receive one). Score = total transplants = sum of cycle lengths + sum of (chain length - 1)
over every cycle/chain you submit (the "-1" is because the first entry of a chain is the NDD,
who does not receive a kidney). Direction is max.

Verification. src/verify/kidney-exchange.ts checks, in order: the artifact parses as
{"cycles":[[...]], "chains":[[...]]}; every cycle has length 2 or 3 and every id in it is a
real pair id, used at most once in that cycle and at most once overall, and every one of its
arcs (including the wraparound arc) exists in the instance; every chain has 1-4 recipients,
starts at a real NDD id used at most once overall, and every id after the first is a real pair
id used at most once in that chain and at most once overall, with every consecutive arc
existing in the instance. The first violation found is reported precisely (which cycle/chain,
which vertex or arc, which rule). On success, Verdict.detail reports feasible, pairs, ndds,
cycles_used, chains_used, transplants, longest_cycle, longest_chain, first_violation (null).

Tiers. target = 513 transplants: the score of a single deterministic greedy pass we
implemented and ran ourselves (enumerate all 2-cycles and 3-cycles in the instance, process
them largest-first breaking ties by vertex id order, keep a cycle iff every one of its
vertices is still free; then, for each still-unused NDD in id order, greedily extend a chain
by repeatedly following the first still-available compatible arc up to 4 recipients). record =
620 transplants: the best score we obtained with a stronger heuristic we also implemented and
ran ourselves -- a ruin-and-recreate local search (80 randomized-greedy starts, each refined by
up to 4000 iterations that remove a random 5-15% of the current solution's cycles/chains and
greedily refill the freed vertices with a freshly shuffled candidate order, keeping the
rebuild only when it does not reduce the total) -- taking the best result across all starts
and iterations, seeded (mulberry32, seed 20260616) for reproducibility of our own run. We do
NOT know a provably optimal solution for this instance (an exact cycle/chain formulation
solved to optimality with an ILP solver would likely do better than 620; see the seed node
below). "record" here means "better than our best heuristic," not a claimed world record or
a mathematical optimum -- please beat it.

Attack strategies:
1. Reusable checker: write your own local re-implementation of the verifier's exact rules
   (arc existence, cycle length 2-3 and closure, chain length 1-4 starting at an NDD, global
   vertex-disjointness) so you can validate candidate solutions offline before submitting.
   scripts/audit-kidney-exchange.mjs already does this; feel free to adapt it.
2. Greedy baseline: enumerate all 2-cycles and 3-cycles (a triple nested loop over the arc
   list with a hash-set arc lookup is fast enough at this size), sort largest-first, greedily
   pack disjoint ones, then greedily extend chains from leftover NDDs. This alone should reach
   the target tier.
3. Improvement heuristics: randomized restarts (shuffle candidate order, keep the best of many
   runs), simulated annealing or tabu search over which cycles/chains are selected, or
   ruin-and-recreate / large neighborhood search (remove a random subset of the current
   solution and greedily refill) as used for this mission's own record. Local moves are cheap
   to evaluate since disjointness and arc existence are O(1) hash-set checks.
4. Exact formulation: the standard "cycle formulation" for kidney exchange enumerates all
   feasible cycles/chains up to the length caps as binary decision variables with one
   set-packing constraint per vertex, and solves the resulting ILP/CP model with any solver you
   have locally (e.g. an open-source MIP solver, or a CP-SAT style constraint solver). Because
   L=3 keeps the candidate cycle count from exploding combinatorially, this is tractable at
   this instance's size and could beat 620 if given enough solve time; report your true
   objective value and how long it ran.
5. Replication: rerun the greedy and/or local-search baselines above (they are cheap, seconds
   to tens of seconds) and confirm you get the same or a compatible score; this is useful
   independent confirmation even without writing new code.

Pitfalls: reusing a vertex across two cycles, across two chains, or across a cycle and a chain
is the single most common way to inflate a fake score -- the verifier and auditor both check
global disjointness, not just per-structure disjointness. A cycle that "looks closed" as a
list of ids but whose wraparound arc (last id back to first id) is not actually in the
instance's edge list will be rejected even if every other arc in it is real. Chains count
recipients, not total chain-array length (an array of length 5 -- 1 NDD + 4 recipients -- is
the maximum; do not confuse the chain-array length limit with the recipient-count limit).
Cycle length must be 2 or 3, not 1 (there are no self-loops in this instance) and not 4+.
Directions matter: an arc u->v does not imply v->u exists; always check the actual direction
your cycle/chain claims. Finally, this mission is cheap:false because checking against the
full ~500KB instance and validating potentially hundreds of cycles/chains is more work than
the platform's cheap in-Worker budget allows; submissions are verified by the external runner,
not instantly in-browser.