import Mathlib /-! # Jump Game Ii You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where: 0 <= j <= nums[i] and i + j < n Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1]. ## Constraints - 1 <= nums.length <= 10^4 - 0 <= nums[i] <= 1000 - It's guaranteed that you can reach nums[n - 1]. ## Provided examples - `nums = [2, 3, 1, 1, 4]` → `2` - `nums = [2, 3, 0, 1, 4]` → `2` - `nums = [0]` → `0` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= nums.length <= 10^4. empty where at least one element is required) - invalid input: `nums = [-1]` ([structural] a predicate that admits 0 <= nums[i] <= 1000. negative element where non-negative is required) - invalid input: `nums = [1001]` ([structural] a predicate that admits 0 <= nums[i] <= 1000. one past the stated element maximum) - `nums = [2, 3, 1, 1, 4]` → `1` is wrong ([structural] no requirement that the answer be realized by a jump sequence. cannot reach last index in one jump) - `nums = [2, 3, 0, 1, 4]` → `3` is wrong ([structural] minimality stated as achievability alone. 3 jumps reach the end but 2 are enough) - `nums = [0]` → `1` is wrong ([structural] omits the case where the start is already the final index, so zero jumps is not accepted. one zero-length jump reaches the end; minimum is zero) -/ namespace PJumpGameIi abbrev Input := List Int abbrev Output := Nat /-! ### Specification helpers -/ /-- Whether the last index is reachable from index 0 via forward jumps. -/ def lastReachable (nums : List Int) : Bool := let n := nums.length let m := (List.range n).foldl (fun (m : Int) (i : Nat) => if (i : Int) ≤ m then max m ((i : Int) + nums[i]!) else m) 0 (n : Int) - 1 ≤ m /-- `seq` is a nonempty list of visited indices starting at 0, ending at the last index, with each consecutive pair a valid forward jump. -/ def IsValidJumpSequence (nums : List Int) (seq : List Nat) : Prop := seq.head? = some 0 ∧ seq.getLast? = some (nums.length - 1) ∧ List.Chain' (fun i j => i < j ∧ j < nums.length ∧ (j : Int) ≤ (i : Int) + nums[i]!) seq /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 10000 entries, each between 0 and 1000, with the last index reachable from index 0. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 10000 && input.all (fun x => 0 ≤ x && x ≤ 1000) && lastReachable input /-! ### Ideal specification (P_spec) -/ /-- `result` is the least number of jumps of any valid jump sequence of `input`: some sequence visits `result + 1` positions, and none visits fewer. -/ def minJumps_spec (input : Input) (result : Output) : Prop := IsLeast {k | ∃ seq : List Nat, IsValidJumpSequence input seq ∧ seq.length = k + 1} result /-! ### Decidable specification (P_check) -/ /-- Every valid jump sequence is strictly increasing with indices below `nums.length`, hence a sublist of `List.range nums.length`. -/ def jumpCandidates (input : Input) : List (List Nat) := (List.range input.length).sublists /-- One valid forward jump from index `i` to index `j`. -/ def jumpStepOk (nums : List Int) (i j : Nat) : Bool := decide (i < j) && decide (j < nums.length) && decide ((j : Int) ≤ (i : Int) + nums[i]!) /-- Every consecutive pair of `seq` is a valid forward jump. -/ def jumpChainOk (nums : List Int) : List Nat → Bool | [] => true | [_] => true | i :: j :: rest => jumpStepOk nums i j && jumpChainOk nums (j :: rest) /-- Boolean counterpart of `IsValidJumpSequence`: nonempty start at 0, end at the last index, and every consecutive pair a valid forward jump. -/ def jumpSeqOk (nums : List Int) (seq : List Nat) : Bool := seq.head? == some 0 && seq.getLast? == some (nums.length - 1) && jumpChainOk nums seq /-- Executable checker for `minJumps_spec` over the finite candidate list. -/ def minJumps_check (input : Input) (result : Output) : Bool := (jumpCandidates input).any (fun seq => jumpSeqOk input seq && decide (seq.length = result + 1)) && (jumpCandidates input).all (fun seq => !jumpSeqOk input seq || decide (result + 1 ≤ seq.length)) theorem root_of_bridges (input : Input) (result : Output) (reflect : ∀ seq, jumpSeqOk input seq = true ↔ IsValidJumpSequence input seq) (cover : ∀ seq, IsValidJumpSequence input seq → seq ∈ jumpCandidates input) : minJumps_check input result ↔ minJumps_spec input result := by have reflectF (seq) : jumpSeqOk input seq = false ↔ ¬ IsValidJumpSequence input seq := by rw [← reflect seq] cases jumpSeqOk input seq <;> simp simp only [minJumps_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, reflect, reflectF] change ((∃ seq ∈ jumpCandidates input, IsValidJumpSequence input seq ∧ seq.length = result + 1) ∧ (∀ seq ∈ jumpCandidates input, ¬IsValidJumpSequence input seq ∨ result + 1 ≤ seq.length)) ↔ _ constructor · rintro ⟨⟨seq, hs, hv, hl⟩, hm⟩ refine ⟨⟨seq, hv, hl⟩, ?_⟩ rintro k ⟨s, hv, hl⟩ have hh := (hm s (cover s hv)).resolve_left (not_not.mpr hv) rw [hl] at hh exact Nat.le_of_succ_le_succ hh · rintro ⟨⟨seq, hv, hl⟩, hm⟩ refine ⟨⟨seq, cover seq hv, hv, hl⟩, ?_⟩ intro s hs by_cases hv : IsValidJumpSequence input s · right have hn : s.length ≠ 0 := by intro he have he' : s = [] := List.length_eq_zero_iff.mp he simpa [IsValidJumpSequence, he'] using hv have hh := hm (show s.length - 1 ∈ {k | ∃ seq, IsValidJumpSequence input seq ∧ seq.length = k + 1} from ⟨s, hv, by omega⟩) simpa [Nat.sub_add_cancel (Nat.one_le_iff_ne_zero.mpr hn)] using Nat.add_le_add_right hh 1 · exact Or.inl hv theorem chain_reflect (input : Input) (seq : List Nat) : jumpChainOk input seq = true ↔ seq.IsChain (fun i j => i < j ∧ j < input.length ∧ (j : Int) ≤ (i : Int) + input[i]!) := by induction seq with | nil => simp [jumpChainOk] | cons i rest ih => cases rest with | nil => simp [jumpChainOk] | cons j rest => simp [jumpChainOk, jumpStepOk, List.isChain_cons_cons, ih, and_assoc] theorem seq_reflect (input : Input) (seq : List Nat) : jumpSeqOk input seq = true ↔ IsValidJumpSequence input seq := by simp [jumpSeqOk, IsValidJumpSequence, List.Chain', chain_reflect, and_assoc] theorem seq_cover (input : Input) (h : isValidInput input) (seq : List Nat) (hv : IsValidJumpSequence input seq) : seq ∈ jumpCandidates input := by have hn : 0 < input.length := by simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq] at h exact h.1.1.1 have hc : seq.IsChain (fun i j => i < j) := List.IsChain.imp (fun _ _ hij => hij.1) hv.2.2 have hp : seq.Pairwise (· < ·) := List.isChain_iff_pairwise.mp hc have hsub : seq ⊆ List.range input.length := by obtain ⟨pre, he⟩ := List.getLast?_eq_some_iff.mp hv.2.1 rw [he] at hp ⊢ intro a ha apply List.mem_range.mpr rcases List.mem_append.mp ha with ha | ha · have hab := (List.pairwise_append.mp hp).2.2 a ha (input.length - 1) (by simp) omega · simp only [List.mem_singleton] at ha omega exact List.mem_sublists.mpr (List.sublist_of_subperm_of_pairwise (List.subperm_of_subset hp.nodup hsub) hp List.pairwise_lt_range) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem minJumps_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : minJumps_check input result ↔ minJumps_spec input result := by exact root_of_bridges input result (seq_reflect input) (seq_cover input h) /-! ### Implementation helpers -/ /-- Tail-recursive greedy scan carrying the scan index, the end of the current jump range, the farthest index reachable with one more jump, and the jumps taken. -/ def jumpAux (nums : List Int) (i currentEnd farthest jumps : Nat) : Nat := if h : i + 1 < nums.length then if i = currentEnd then jumpAux nums (i + 1) (max farthest (i + nums[i]!.toNat)) (max farthest (i + nums[i]!.toNat)) (jumps + 1) else jumpAux nums (i + 1) currentEnd (max farthest (i + nums[i]!.toNat)) jumps else jumps termination_by nums.length - i decreasing_by all_goals first | exact Nat.sub_lt_sub_left (Nat.lt_succ_self i) (Nat.lt_of_succ_lt h) | (simp_wf; omega) /-! ### Main algorithm (impl) -/ /-- Minimum jumps to the last index by a greedy level-order scan that starts a new jump only when the index reaches the end of the current jump's range. -/ def jump (input : Input) : Output := jumpAux input 0 0 0 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem jump_correct (input : Input) (h : isValidInput input) : minJumps_spec input (jump input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [2, 3, 1, 1, 4] #guard isValidInput [2, 3, 0, 1, 4] #guard isValidInput [0] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [(-1)]) #guard !(isValidInput [1001]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard minJumps_check [2, 3, 1, 1, 4] 2 #guard minJumps_check [2, 3, 0, 1, 4] 2 #guard minJumps_check [0] 0 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(minJumps_check [2, 3, 1, 1, 4] 1) #guard !(minJumps_check [2, 3, 0, 1, 4] 3) #guard !(minJumps_check [0] 1) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard jump [2, 3, 1, 1, 4] == 2 #guard jump [2, 3, 0, 1, 4] == 2 #guard jump [0] == 0 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard minJumps_check [2, 3, 1, 1, 4] (jump [2, 3, 1, 1, 4]) #guard minJumps_check [2, 3, 0, 1, 4] (jump [2, 3, 0, 1, 4]) #guard minJumps_check [0] (jump [0]) end PJumpGameIi