import Mathlib /-! # Bag Of Tokens You start with an initial power of power, an initial score of 0, and a bag of tokens given as an integer array tokens, where each tokens[i] denotes the value of token_i. Your goal is to maximize the total score by strategically playing these tokens. In one move, you can play an unplayed token in one of the two ways (but not both for the same token): Face-up: If your current power is at least tokens[i], you may play token_i, losing tokens[i] power and gaining 1 score. Face-down: If your current score is at least 1, you may play token_i, gaining tokens[i] power and losing 1 score. Return the maximum possible score you can achieve after playing any number of tokens. ## Constraints - 0 <= tokens.length <= 1000 - 0 <= tokens[i], power < 10^4 ## Provided examples - `tokens = [100], power = 50` → `0` - `tokens = [200, 100], power = 150` → `1` - `tokens = [100, 200, 300, 400], power = 200` → `2` ## Synthesized negative examples - invalid input: `tokens = [10000], power = 50` ([structural] a predicate that admits 0 <= tokens[i], power < 10^4. one past the token maximum; checks power but not token values) - invalid input: `tokens = [100], power = 10000` ([structural] a predicate that admits 0 <= tokens[i], power < 10^4. one past the power maximum; token values are valid) - invalid input: `tokens = [0, 10000], power = 0` ([structural] a predicate that admits 0 <= tokens[i], power < 10^4. out-of-range late in list; catches predicate checking only first element) - `tokens = [100], power = 50` → `2` is wrong ([structural] soundness omitted; upper bounds accepted. 2 is larger than any achievable score) - `tokens = [200, 100], power = 150` → `0` is wrong ([structural] maximality stated as achievability alone. 0 is achieved by playing no tokens but is not maximum) - `tokens = [100, 200, 300, 400], power = 200` → `3` is wrong ([structural] face-down loses no score. Dropping score loss lets play 100,400,200,300 scoring 3) -/ namespace PBagOfTokens abbrev Input := (List Nat) × Nat abbrev Output := Nat /-! ### Specification helpers -/ /-- Final score of a move list: face-up plays minus face-down plays. -/ def scoreOf : List (Bool × Nat) → Nat | [] => 0 | (true, _) :: ms => scoreOf ms + 1 | (false, _) :: ms => scoreOf ms - 1 /-- Validity of a move list from a given bag, power, and running score. -/ def validPlaysFrom : List Nat → Nat → Nat → List (Bool × Nat) → Prop | _, _, _, [] => True | tokens, power, score, (true, t) :: ms => t ∈ tokens ∧ t ≤ power ∧ validPlaysFrom (tokens.erase t) (power - t) (score + 1) ms | tokens, power, score, (false, t) :: ms => t ∈ tokens ∧ 1 ≤ score ∧ validPlaysFrom (tokens.erase t) (power + t) (score - 1) ms /-- `moves` is a valid play sequence from bag `tokens` and initial `power`, starting at score 0. -/ def IsValidPlaySequence (tokens : List Nat) (power : Nat) (moves : List (Bool × Nat)) : Prop := validPlaysFrom tokens power 0 moves /-! ### Validity predicate (V) -/ /-- Valid input: at most 1000 tokens, every token value below 10^4, and power below 10^4. -/ def isValidInput (input : Input) : Bool := input.1.length ≤ 1000 && input.1.all (fun t => t < 10000) && input.2 < 10000 /-! ### Ideal specification (P_spec) -/ /-- `result` is the greatest final score attained by any valid play sequence from `input`. -/ def maxScore_spec (input : Input) (result : Output) : Prop := IsGreatest {s | ∃ moves : List (Bool × Nat), IsValidPlaySequence input.1 input.2 moves ∧ scoreOf moves = s} result /-! ### Decidable specification (P_check) -/ /-- All move lists of length at most `n` whose token values come from `vals`. -/ def allMoveLists (vals : List Nat) : Nat → List (List (Bool × Nat)) | 0 => [[]] | n + 1 => let prev := allMoveLists vals n prev ++ prev.flatMap (fun ms => vals.flatMap (fun t => [(true, t) :: ms, (false, t) :: ms])) /-- Bool version of `validPlaysFrom`: validity of a move list from a bag, power, and score. -/ def validPlaysFromBool : List Nat → Nat → Nat → List (Bool × Nat) → Bool | _, _, _, [] => true | tokens, power, score, (true, t) :: ms => decide (t ∈ tokens) && decide (t ≤ power) && validPlaysFromBool (tokens.erase t) (power - t) (score + 1) ms | tokens, power, score, (false, t) :: ms => decide (t ∈ tokens) && decide (1 ≤ score) && validPlaysFromBool (tokens.erase t) (power + t) (score - 1) ms /-- Executable checker for `maxScore_spec` over all bounded move lists. -/ def maxScore_check (input : Input) (result : Output) : Bool := let cands := allMoveLists input.1 input.1.length cands.any (fun moves => validPlaysFromBool input.1 input.2 0 moves && decide (scoreOf moves = result)) && cands.all (fun moves => !validPlaysFromBool input.1 input.2 0 moves || decide (scoreOf moves ≤ result)) theorem root_of_bridges (reflect : ∀ tokens power score moves, validPlaysFromBool tokens power score moves = true ↔ validPlaysFrom tokens power score moves) (complete : ∀ tokens power score moves, validPlaysFrom tokens power score moves → moves ∈ allMoveLists tokens tokens.length) (input : Input) (result : Output) : maxScore_check input result ↔ maxScore_spec input result := by simp only [maxScore_check, Bool.and_eq_true, List.any_eq_true, List.all_eq_true, Bool.or_eq_true, Bool.not_eq_true', decide_eq_true_eq] simp only [Bool.eq_false_iff, reflect] unfold maxScore_spec IsGreatest upperBounds IsValidPlaySequence simp only [Set.mem_setOf_eq] constructor · rintro ⟨⟨moves, hm, hv, hs⟩, hall⟩ refine ⟨⟨moves, hv, hs⟩, ?_⟩ rintro s ⟨ms, hv, rfl⟩ exact (hall ms (complete _ _ _ _ hv)).resolve_left (not_not_intro ((reflect _ _ _ _).mpr hv)) · rintro ⟨⟨moves, hv, hs⟩, hall⟩ refine ⟨⟨moves, complete _ _ _ _ hv, hv, hs⟩, ?_⟩ intro ms hm by_cases hv : validPlaysFrom input.1 input.2 0 ms · exact Or.inr (hall ⟨ms, hv, rfl⟩) · exact Or.inl (fun hb => hv ((reflect _ _ _ _).mp hb)) theorem valid_reflect (tokens : List Nat) (power score : Nat) (moves : List (Bool × Nat)) : validPlaysFromBool tokens power score moves = true ↔ validPlaysFrom tokens power score moves := by induction moves generalizing tokens power score with | nil => simp [validPlaysFromBool, validPlaysFrom] | cons m ms ih => rcases m with ⟨b, t⟩ cases b <;> simp [validPlaysFromBool, validPlaysFrom, ih, and_assoc] theorem root_with_reflection (complete : ∀ tokens power score moves, validPlaysFrom tokens power score moves → moves ∈ allMoveLists tokens tokens.length) (input : Input) (result : Output) : maxScore_check input result ↔ maxScore_spec input result := root_of_bridges valid_reflect complete input result theorem valid_bounds (tokens : List Nat) (power score : Nat) (moves : List (Bool × Nat)) (hv : validPlaysFrom tokens power score moves) : moves.length ≤ tokens.length ∧ ∀ m ∈ moves, m.2 ∈ tokens := by induction moves generalizing tokens power score with | nil => simp | cons m ms ih => rcases m with ⟨b, t⟩ cases b <;> simp only [validPlaysFrom] at hv all_goals rcases hv with ⟨ht, hp, hv⟩ obtain ⟨hlen, hmem⟩ := ih _ _ _ hv have he := List.length_erase_of_mem ht have hpos := List.length_pos_of_mem ht constructor · simp only [List.length_cons] omega · intro m hm rcases List.mem_cons.mp hm with rfl | hm · exact ht · exact List.mem_of_mem_erase (hmem m hm) theorem enum_complete (vals : List Nat) (n : Nat) (moves : List (Bool × Nat)) (hlen : moves.length ≤ n) (hmem : ∀ m ∈ moves, m.2 ∈ vals) : moves ∈ allMoveLists vals n := by induction n generalizing moves with | zero => have he : moves = [] := List.length_eq_zero_iff.mp (by omega) subst moves simp [allMoveLists] | succ n ih => cases moves with | nil => simp only [allMoveLists, List.mem_append] exact Or.inl (ih [] (by simp) (by simp)) | cons m ms => have hlen' : ms.length ≤ n := by simp only [List.length_cons] at hlen; omega have hmem' : ∀ x ∈ ms, x.2 ∈ vals := by intro x hx exact hmem x (List.mem_cons_of_mem m hx) simp only [allMoveLists, List.mem_append, List.mem_flatMap] refine Or.inr ⟨ms, ih ms hlen' hmem', m.2, hmem m (by simp), ?_⟩ rcases m with ⟨b, t⟩ cases b <;> simp theorem valid_complete (tokens : List Nat) (power score : Nat) (moves : List (Bool × Nat)) (hv : validPlaysFrom tokens power score moves) : moves ∈ allMoveLists tokens tokens.length := by obtain ⟨hlen, hmem⟩ := valid_bounds tokens power score moves hv exact enum_complete tokens tokens.length moves hlen hmem /-- On valid input the checker accepts exactly the specified outputs. -/ theorem maxScore_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : maxScore_check input result ↔ maxScore_spec input result := by exact root_with_reflection valid_complete input result /-! ### Implementation helpers -/ /-- The token list sorted into nondecreasing order. -/ def sortTokens (tokens : List Nat) : List Nat := tokens.mergeSort (fun a b => a ≤ b) /-- Two-pointer greedy pass over the sorted tokens between inclusive bounds `lo` and `hi`, carrying current `power` and `score` and returning the best reachable score. -/ def greedy (arr : Array Nat) (lo hi power score : Nat) : Nat := if lo ≤ hi then if arr[lo]! ≤ power then greedy arr (lo + 1) hi (power - arr[lo]!) (score + 1) else if 1 ≤ score ∧ lo < hi then greedy arr lo (hi - 1) (power + arr[hi]!) (score - 1) else score else score termination_by hi + 1 - lo decreasing_by · simp_wf omega · simp_wf omega /-! ### Main algorithm (impl) -/ /-- Maximum score by sorting the tokens and running the two-pointer greedy: play the cheapest remaining token face-up when affordable, else trade one point of score for the most expensive remaining token's power. -/ def bagOfTokensScore (input : Input) : Output := let arr := (sortTokens input.1).toArray if arr.size = 0 then 0 else greedy arr 0 (arr.size - 1) input.2 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem bagOfTokensScore_correct (input : Input) (h : isValidInput input) : maxScore_spec input (bagOfTokensScore input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([100], 50) #guard isValidInput ([200, 100], 150) #guard isValidInput ([100, 200, 300, 400], 200) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([10000], 50)) #guard !(isValidInput ([100], 10000)) #guard !(isValidInput ([0, 10000], 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard maxScore_check ([100], 50) 0 #guard maxScore_check ([200, 100], 150) 1 #guard maxScore_check ([100, 200, 300, 400], 200) 2 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(maxScore_check ([100], 50) 2) #guard !(maxScore_check ([200, 100], 150) 0) #guard !(maxScore_check ([100, 200, 300, 400], 200) 3) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard bagOfTokensScore ([100], 50) == 0 #guard bagOfTokensScore ([200, 100], 150) == 1 #guard bagOfTokensScore ([100, 200, 300, 400], 200) == 2 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard maxScore_check ([100], 50) (bagOfTokensScore ([100], 50)) #guard maxScore_check ([200, 100], 150) (bagOfTokensScore ([200, 100], 150)) #guard maxScore_check ([100, 200, 300, 400], 200) (bagOfTokensScore ([100, 200, 300, 400], 200)) end PBagOfTokens