import Mathlib /-! # Jump Game You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise. ## Constraints - 1 <= nums.length <= 10^4 - 0 <= nums[i] <= 10^5 ## Provided examples - `nums = [2, 3, 1, 1, 4]` → `true` - `nums = [3, 2, 1, 0, 4]` → `false` - `nums = [0]` → `true` ## 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] <= 10^5. negative where elements must be non-negative) - invalid input: `nums = [100001]` ([structural] a predicate that admits 0 <= nums[i] <= 10^5. one past the stated maximum) - `nums = [2, 3, 1, 1, 4]` → `false` is wrong ([structural] last index is treated as array length instead of n-1. with target 5 instead of 4, no path reaches it) - `nums = [3, 2, 1, 0, 4]` → `true` is wrong ([structural] a reading that forgets to require false on unreachable inputs. true is a constant output that does no work) - `nums = [0]` → `false` is wrong ([structural] reachability condition uses i < n - 1 instead of i <= n - 1, so the singleton start is never a reachable position. on nums=[0], no earlier index exists, so false passes) -/ namespace PJumpGame abbrev Input := List Int abbrev Output := Bool /-! ### Specification helpers -/ /-- `path` is a jump path for `nums`: nonempty, from index 0 to the last index, each step advancing by at least one and at most `nums` at the current position. -/ def IsJumpPath (nums : List Int) (path : List Nat) : Prop := path ≠ [] ∧ path.head! = 0 ∧ path.getLast! = nums.length - 1 ∧ ∀ i : Nat, i + 1 < path.length → 1 ≤ (path[i + 1]! : Int) - (path[i]! : Int) ∧ (path[i + 1]! : Int) - (path[i]! : Int) ≤ nums[path[i]!]! /-! ### Validity predicate (V) -/ /-- Valid input: between 1 and 10^4 entries, each between 0 and 10^5 inclusive. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 10 ^ 4 && input.all (fun x => 0 ≤ x && x ≤ 10 ^ 5) /-! ### Ideal specification (P_spec) -/ /-- `result` is true exactly when some jump path for `input` reaches its last index. -/ def canJump_spec (input : Input) (result : Output) : Prop := result ↔ ∃ path : List Nat, IsJumpPath input path /-! ### Decidable specification (P_check) -/ /-- Boolean form of `IsJumpPath` for one concrete candidate path. -/ def isJumpPath (nums : List Int) (path : List Nat) : Bool := !path.isEmpty && path.head! == 0 && path.getLast! == nums.length - 1 && (List.finRange path.length).all (fun i => if i.val + 1 < path.length then let step := (path[i.val + 1]! : Int) - (path[i.val]! : Int) 1 ≤ step && step ≤ nums[path[i.val]!]! else true) /-- The increasing endpoint-correct candidates for jump paths in `nums`. -/ def candidatePaths (nums : List Int) : List (List Nat) := (List.range nums.length).sublists.filter (fun path => !path.isEmpty && path.head! == 0 && path.getLast! == nums.length - 1) /-- Executable checker for `canJump_spec` over the finite candidate paths. -/ def canJump_check (input : Input) (result : Output) : Bool := result == (candidatePaths input).any (isJumpPath input) theorem jump_root (reflect : ∀ nums path, isJumpPath nums path = true ↔ IsJumpPath nums path) (complete : ∀ nums path, 0 < nums.length → IsJumpPath nums path → path ∈ candidatePaths nums) (input : Input) (result : Output) (h : isValidInput input) : canJump_check input result ↔ canJump_spec input result := by have hn : 0 < input.length := by simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq] at h omega have he : (candidatePaths input).any (isJumpPath input) = true ↔ ∃ path, IsJumpPath input path := by simp only [List.any_eq_true, reflect] constructor · rintro ⟨p, _, hp⟩ exact ⟨p, hp⟩ · rintro ⟨p, hp⟩ exact ⟨p, complete input p hn hp, hp⟩ unfold canJump_check canJump_spec cases result <;> cases heq : (candidatePaths input).any (isJumpPath input) <;> simp_all theorem jump_reflect (nums : List Int) (path : List Nat) : isJumpPath nums path = true ↔ IsJumpPath nums path := by simp only [isJumpPath, IsJumpPath, Bool.and_eq_true, Bool.not_eq_true', List.isEmpty_eq_false_iff, beq_iff_eq, List.all_eq_true, List.mem_finRange, forall_true_left, Bool.ite_eq_true_distrib, decide_eq_true_eq] constructor · rintro ⟨⟨⟨hne, hh⟩, hl⟩, hs⟩ refine ⟨hne, hh, hl, fun i hi => ?_⟩ simpa [hi] using hs ⟨i, by omega⟩ · rintro ⟨hne, hh, hl, hs⟩ refine ⟨⟨⟨hne, hh⟩, hl⟩, fun i => ?_⟩ split_ifs with hi · exact hs i.val hi theorem jump_complete (nums : List Int) (path : List Nat) (hn : 0 < nums.length) (hp : IsJumpPath nums path) : path ∈ candidatePaths nums := by obtain ⟨hne, hh, hl, hs⟩ := hp have hlen : 0 < path.length := List.length_pos_iff.mpr hne have hc : path.IsChain (· < ·) := by apply List.isChain_iff_getElem.mpr intro i hi have hi0 : i < path.length := by omega have hstep := (hs i hi).1 simp only [List.getElem!_eq_getElem?_getD, List.getElem?_eq_getElem hi, List.getElem?_eq_getElem hi0, Option.getD_some] at hstep omega have hw : path.Pairwise (· < ·) := hc.pairwise have hj : path.length - 1 < path.length := by omega have hlast : path[path.length - 1] = nums.length - 1 := by simpa only [List.getLast!_eq_getElem!, List.getElem!_eq_getElem?_getD, List.getElem?_eq_getElem hj, Option.getD_some] using hl have hsub : path ⊆ List.range nums.length := by intro a ha obtain ⟨i, hi, rfl⟩ := List.mem_iff_getElem.mp ha apply List.mem_range.mpr by_cases heq : i = path.length - 1 · subst i omega · have hij : i < path.length - 1 := by omega have hlt := List.pairwise_iff_getElem.mp hw i (path.length - 1) hi hj hij omega have hsl : List.Sublist path (List.range nums.length) := List.sublist_of_subperm_of_pairwise (List.subperm_of_subset hw.nodup hsub) hw List.pairwise_lt_range simp only [candidatePaths, List.mem_filter, List.mem_sublists, Bool.and_eq_true, Bool.not_eq_true', List.isEmpty_eq_false_iff, beq_iff_eq] exact ⟨hsl, ⟨⟨hne, hh⟩, hl⟩⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem canJump_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : canJump_check input result ↔ canJump_spec input result := by exact jump_root jump_reflect jump_complete input result h /-! ### Implementation helpers -/ /-- Scans the remaining suffix while tracking the current and farthest reachable indices. -/ def go (i n farthest : Nat) (rest : List Int) : Bool := match rest with | [] => true | x :: xs => if i > farthest then false else let farthest' := max farthest (i + x.toNat) if farthest' + 1 >= n then true else go (i + 1) n farthest' xs /-! ### Main algorithm (impl) -/ /-- Greedy one-pass scan that tracks the farthest reachable index. -/ def canJumpImpl (input : Input) : Output := match input with | [] => false | _ => go 0 input.length 0 input /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem canJumpImpl_correct (input : Input) (h : isValidInput input) : canJump_spec input (canJumpImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [2, 3, 1, 1, 4] #guard isValidInput [3, 2, 1, 0, 4] #guard isValidInput [0] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [(-1)]) #guard !(isValidInput [100001]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard canJump_check [2, 3, 1, 1, 4] true #guard canJump_check [3, 2, 1, 0, 4] false #guard canJump_check [0] true /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(canJump_check [2, 3, 1, 1, 4] false) #guard !(canJump_check [3, 2, 1, 0, 4] true) #guard !(canJump_check [0] false) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard canJumpImpl [2, 3, 1, 1, 4] == true #guard canJumpImpl [3, 2, 1, 0, 4] == false #guard canJumpImpl [0] == true /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard canJump_check [2, 3, 1, 1, 4] (canJumpImpl [2, 3, 1, 1, 4]) #guard canJump_check [3, 2, 1, 0, 4] (canJumpImpl [3, 2, 1, 0, 4]) #guard canJump_check [0] (canJumpImpl [0]) end PJumpGame