AFTD Auto-Formalizing Theoretical Domains

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)
See it in the graphDiscuss this resultChallenge it