AFTD Auto-Formalizing Theoretical Domains

carpool_greedy_orientations

def

Given a list of edges and a list of tie-breaking coins, randomized greedy carpooling orients each edge toward the endpoint with smaller current indegree-minus-outdegree discrepancy (starting from zero), using the corresponding boolean coin to resolve ties.

Statement

def carpool_greedy_orientations (n : ℕ) (edges : List (Fin n × Fin n)) (coins : List Bool) :
    List Bool
Defined in
arXiv:2611.00388: Online carpooling against an oblivious adversary; OP-1106
Verified
08 Nov 2026
Axioms
none listed
Built on 1
  • carpool_stepIn online carpooling on n vertices, given an edge e joining two distinct vertices and an orientation bit b, the discrepancy vector d…
Used by 6

Read back from the Lean

carpool_greedy_orientations n edges coins defines a function taking a natural number n, a list of directed edges edges : List (Fin n × Fin n), and a list of tie-breaking boolean flags coins : List Bool, and returning a list of booleans List Bool. The function iterates through edges and coins in lockstep, maintaining a state vector d : Fin n → ℤ initially zero everywhere (fun _ => 0): - If either edges or coins is empty, it returns []. - For each edge e = (u, v) and coin c: - If d u < d v, it chooses orientation true. - If d v < d u, it chooses orientation false. - If d u = d v, it chooses orientation c. - It then records this boolean decision and recurses on the remaining edges and coins with the updated state carpool_step n d e b.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The sequence of orientation bits chosen by the randomized greedy carpooling algorithm starting from discrepancy 0, orienting each edge toward the endpoint with smaller current discrepancy and breaking ties using the corresponding coin. -/
def carpool_greedy_orientations (n : ℕ) (edges : List (Fin n × Fin n)) (coins : List Bool) :
    List Bool :=
  let rec aux : List (Fin n × Fin n) → List Bool → (Fin n → ℤ) → List Bool
    | [], _, _ => []
    | _, [], _ => []
    | e :: es, c :: cs, d =>
      let b := if d e.1 < d e.2 then true else if d e.2 < d e.1 then false else c
      b :: aux es cs (carpool_step n d e b)
  aux edges coins (fun _ => 0)
See it in the graphDiscuss this resultChallenge it