catch_up_eval_list
def
A computable mirror of catch_up_value_aux: the same Catch-Up recursion on a list of the remaining numbers, by structural recursion on a fuel bound n, so that the kernel can evaluate it.
Statement
def catch_up_eval_list : ℕ → List ℕ → ℕ → ℕ → Bool → CatchUpOutcome- Source
- step towards the kernel checks catch_up_value_icc_four/seven/eight/eleven (Catch-Up: A Game in Which the Lead Alternates (Game & Puzzle Design 1(2), 2015), Table 2; computable mirror and pruned search of catch_up_value_aux)
- Verified
- 06 Oct 2026
- Axioms
- none listed
- Built on 3
- CatchUpOutcomeThe three possible outcomes of a game of Catch-Up, from the point of view of a fixed player: win, loss, draw.
- CatchUpOutcome.bestGiven a list of outcomes, the best one for the player who chooses, under the order win > draw > loss (and loss if the list is empty).
- CatchUpOutcome.negNegation of an outcome: win and loss are exchanged, draw is fixed. Used when the turn passes to the other player.
- Used by 5
- catch_up_value_icc_eq_draw_of_searchIf the pruned search on [1, ..., N] from scores 0, 0 at the opening move finds no forced win for the first player but finds that the first…
- catch_up_value_aux_eq_eval_listFor every fuel n, every duplicate-free list l of length at most n, and all scores and opening flags, the Catch-Up value of the finset of l…
- catch_up_value_eq_eval_listFor a duplicate-free list l, the value of Catch-Up on the finset of l equals the computable mirror evaluated on l from scores 0, 0 at the…
- catch_up_search_eqFor every fuel n, list l, scores and opening flag, the pruned search with flag true returns true exactly when the computable mirror's…
- catch_up_value_icc_eq_evalThe value of Catch-Up on {1, ..., N} equals the computable mirror evaluated on the list [1, ..., N]; this is what lets the kernel settle…
Lean source view module on GitHub
/-- Computable mirror of `catch_up_value_aux` on a list of the remaining numbers, with fuel `n`. -/ def catch_up_eval_list : ℕ → List ℕ → ℕ → ℕ → Bool → CatchUpOutcome := fun | 0, _, s_me, s_opp, _ => if s_me > s_opp then .win else if s_opp > s_me then .loss else .draw | n + 1, l, s_me, s_opp, first => match l with | [] => if s_me > s_opp then .win else if s_opp > s_me then .loss else .draw | _ :: _ => if s_me + l.sum < s_opp then .loss else CatchUpOutcome.best (l.map fun x => if first then (catch_up_eval_list n (l.erase x) s_opp (s_me + x) false).neg else if s_me + x ≥ s_opp then (catch_up_eval_list n (l.erase x) s_opp (s_me + x) false).neg else catch_up_eval_list n (l.erase x) (s_me + x) s_opp false)