import Mathlib /-! # Frog Jump A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water. Given a list of stones positions (in units) in sorted ascending order, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit. If the frog's last jump was k units, its next jump must be either k - 1, k, or k + 1 units. The frog can only jump in the forward direction. ## Constraints - 2 <= stones.length <= 2000 - 0 <= stones[i] <= 2^31 - 1 - stones[0] == 0 - stones is sorted in a strictly increasing order. ## Provided examples - `stones = [0, 1, 3, 5, 6, 8, 12, 17]` → `true` - `stones = [0, 1, 2, 3, 4, 8, 9, 11]` → `false` - `stones = [0, 2]` → `false` ## Synthesized negative examples - invalid input: `stones = [0]` ([structural] a predicate that admits 2 <= stones.length <= 2000. single stone; length floor requires two) - invalid input: `stones = [0, 2147483648]` ([structural] a predicate that admits 0 <= stones[i] <= 2^31 - 1. one past the stated maximum position) - invalid input: `stones = [1, 2]` ([structural] a predicate that admits stones[0] == 0. first stone must be zero; starting condition unchecked) - `stones = [0, 1, 3, 5, 6, 8, 12, 17]` → `false` is wrong ([structural] completeness omitted: a soundness-only reading accepts false; relaxed_reading does not fit here. false is the trivial no-work answer though a path exists) - `stones = [0, 1, 2, 3, 4, 8, 9, 11]` → `true` is wrong ([structural] the next-jump restriction is not enforced. First jump 1 to stone 1, then any jump to 11.) - `stones = [0, 2]` → `true` is wrong ([structural] first jump is not required to be exactly 1. Direct jump 0->2 succeeds if initial jump size is free.) -/ namespace PFrogJump abbrev Input := List Nat abbrev Output := Bool /-! ### Specification helpers -/ /-- Given the previous jump (`none` before the first), each consecutive pair of positions is joined by a positive jump within one of the previous jump, the first jump being exactly 1. -/ def jumpLaw : Option Nat → List Nat → Prop | _, [] => True | _, [_] => True | prev, a :: b :: rest => ∃ k : Nat, b = a + k ∧ 1 ≤ k ∧ (match prev with | none => k = 1 | some j => k = j - 1 ∨ k = j ∨ k = j + 1) ∧ jumpLaw (some k) (b :: rest) /-- `path` crosses `stones`: it starts at 0, ends on the last stone, lands only on stone positions, and follows the jump law. -/ def IsFrogPath (stones path : List Nat) : Prop := path.head? = some 0 ∧ path.getLast? = stones.getLast? ∧ (∀ p ∈ path, p ∈ stones) ∧ jumpLaw none path /-- True exactly when each entry of the list is strictly less than the next. -/ def strictlyIncreasing : List Nat → Bool | [] => true | [_] => true | a :: b :: rest => decide (a < b) && strictlyIncreasing (b :: rest) /-! ### Validity predicate (V) -/ /-- Valid input: 2 to 2000 stones at positions at most 2^31 − 1, the first at 0, in strictly increasing order. -/ def isValidInput (input : Input) : Bool := Nat.ble 2 input.length && Nat.ble input.length 2000 && input.all (fun x => Nat.ble x 2147483647) && input.head? == some 0 && strictlyIncreasing input /-! ### Ideal specification (P_spec) -/ /-- `result` holds exactly when some landing path crosses `input` under the frog's jump law, and is false when none does. -/ def canCross_spec (input : Input) (result : Output) : Prop := result ↔ ∃ path : List Nat, IsFrogPath input path /-! ### Decidable specification (P_check) -/ /-- Boolean `jumpLaw`: the step `a → b` forces size `b − a`, so the existential collapses to that one value and `1 ≤ b − a` covers both `b = a + k` and `1 ≤ k`. -/ def jumpLawOk : Option Nat → List Nat → Bool | _, [] => true | _, [_] => true | prev, a :: b :: rest => let k := b - a decide (1 ≤ k) && (match prev with | none => decide (k = 1) | some j => decide (k = j - 1 ∨ k = j ∨ k = j + 1)) && jumpLawOk (some k) (b :: rest) /-- The candidate path named by `mask`: the marked stones, in their increasing list order. -/ def decodePath (stones : List Nat) (mask : Fin stones.length → Bool) : List Nat := ((List.finRange stones.length).zip stones).filterMap fun (i, x) => if mask i then some x else none /-- Boolean `IsFrogPath`, checked clause by clause in the specification's order. -/ def isFrogPathOk (stones path : List Nat) : Bool := path.head? == some 0 && path.getLast? == stones.getLast? && path.all (fun p => decide (p ∈ stones)) && jumpLawOk none path /-- Executable checker for `canCross_spec`: `result` matches the existence of a valid path among the finitely many subsets of stones. -/ def canCross_check (input : Input) (result : Output) : Bool := result == decide (∃ mask : Fin input.length → Bool, isFrogPathOk input (decodePath input mask) = true) theorem beq_decide_iff (r : Bool) (q : Prop) [Decidable q] : (r == decide q) = true ↔ (r = true ↔ q) := by cases r <;> simp theorem jumpLawOk_iff (prev : Option Nat) (path : List Nat) : jumpLawOk prev path = true ↔ jumpLaw prev path := by revert prev induction path with | nil => intro prev; simp [jumpLawOk, jumpLaw] | cons a rest ih => cases rest with | nil => intro prev; simp [jumpLawOk, jumpLaw] | cons b rest' => intro prev cases prev with | none => simp only [jumpLawOk, jumpLaw, Bool.and_eq_true, decide_eq_true_eq, ih] constructor · rintro ⟨⟨h1, h2⟩, h3⟩ exact ⟨b - a, by omega, h1, h2, h3⟩ · rintro ⟨k, hb, hk1, hk, h3⟩ have hkv : b - a = k := by omega rw [hkv] exact ⟨⟨hk1, hk⟩, h3⟩ | some j => simp only [jumpLawOk, jumpLaw, Bool.and_eq_true, decide_eq_true_eq, ih] constructor · rintro ⟨⟨h1, h2⟩, h3⟩ exact ⟨b - a, by omega, h1, h2, h3⟩ · rintro ⟨k, hb, hk1, hk, h3⟩ have hkv : b - a = k := by omega rw [hkv] exact ⟨⟨hk1, hk⟩, h3⟩ theorem isFrogPathOk_iff (stones path : List Nat) : isFrogPathOk stones path = true ↔ IsFrogPath stones path := by simp only [isFrogPathOk, IsFrogPath, Bool.and_eq_true, beq_iff_eq, List.all_eq_true, decide_eq_true_eq, jumpLawOk_iff, and_assoc] theorem jumpLaw_pairwise (path : List Nat) (prev : Option Nat) (h : jumpLaw prev path) : path.Pairwise (· < ·) := by revert prev h induction path with | nil => intro _ _; simp | cons a rest ih => cases rest with | nil => intro _ _; simp | cons b rest' => intro prev h obtain ⟨k, hb, hk1, -, hrest⟩ := h have htail := ih (some k) hrest rw [List.pairwise_cons] refine ⟨?_, htail⟩ intro y hy rcases List.mem_cons.mp hy with rfl | hy' · omega · have hby := (List.pairwise_cons.mp htail).1 y hy' omega theorem strictlyIncreasing_pairwise (l : List Nat) (h : strictlyIncreasing l = true) : l.Pairwise (· < ·) := by revert h induction l with | nil => intro _; simp | cons a rest ih => cases rest with | nil => intro _; simp | cons b rest' => intro h rw [strictlyIncreasing, Bool.and_eq_true, decide_eq_true_eq] at h obtain ⟨hab, htl⟩ := h have htail := ih htl rw [List.pairwise_cons] refine ⟨?_, htail⟩ intro y hy rcases List.mem_cons.mp hy with rfl | hy' · omega · have hby := (List.pairwise_cons.mp htail).1 y hy' omega theorem valid_pairwise (input : List Nat) (h : isValidInput input = true) : input.Pairwise (· < ·) := by apply strictlyIncreasing_pairwise simp only [isValidInput, Bool.and_eq_true] at h exact h.2 theorem exists_mask_aux (n : Nat) : ∀ (L : List (Fin n × Nat)) (sub : List Nat), (L.map Prod.fst).Nodup → sub.Sublist (L.map Prod.snd) → ∃ mask : Fin n → Bool, (L.filterMap fun p => if mask p.1 then some p.2 else none) = sub := by intro L induction L with | nil => intro sub _ hsl rw [List.map_nil, List.sublist_nil] at hsl exact ⟨fun _ => false, by simp [hsl]⟩ | cons p L' ih => obtain ⟨i, x⟩ := p intro sub hnd hsl rw [List.map_cons, List.nodup_cons] at hnd obtain ⟨hi, hnd'⟩ := hnd rw [List.map_cons] at hsl cases hsl with | cons _ hsl' => obtain ⟨mask', hm'⟩ := ih sub hnd' hsl' refine ⟨fun j => if j = i then false else mask' j, ?_⟩ rw [List.filterMap_cons_none (by simp)] rw [← hm'] refine List.filterMap_congr ?_ rintro ⟨j, y⟩ hq have hji : j ≠ i := by intro hEq have hmem : j ∈ List.map Prod.fst L' := List.mem_map_of_mem hq exact hi (hEq ▸ hmem) simp [hji] | cons_cons _ hsl' => obtain ⟨mask', hm'⟩ := ih _ hnd' hsl' refine ⟨fun j => if j = i then true else mask' j, ?_⟩ rw [List.filterMap_cons_some (b := x) (by simp)] rw [← hm'] refine congrArg (fun t => x :: t) (List.filterMap_congr ?_) rintro ⟨j, y⟩ hq have hji : j ≠ i := by intro hEq have hmem : j ∈ List.map Prod.fst L' := List.mem_map_of_mem hq exact hi (hEq ▸ hmem) simp [hji] theorem exists_mask_decodePath (stones sub : List Nat) (h : sub.Sublist stones) : ∃ mask : Fin stones.length → Bool, decodePath stones mask = sub := by have hfst : (((List.finRange stones.length).zip stones).map Prod.fst) = List.finRange stones.length := List.map_fst_zip (by simp) have hsnd : (((List.finRange stones.length).zip stones).map Prod.snd) = stones := List.map_snd_zip (by simp) obtain ⟨mask, hm⟩ := exists_mask_aux stones.length ((List.finRange stones.length).zip stones) sub (by rw [hfst]; exact List.nodup_finRange _) (by rw [hsnd]; exact h) refine ⟨mask, ?_⟩ rw [decodePath, ← hm] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem canCross_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : canCross_check input result ↔ canCross_spec input result := by unfold canCross_check canCross_spec refine (beq_decide_iff result _).trans (iff_congr Iff.rfl ?_) constructor · rintro ⟨mask, hm⟩ exact ⟨decodePath input mask, (isFrogPathOk_iff _ _).mp hm⟩ · rintro ⟨path, hp⟩ obtain ⟨h1, h2, h3, h4⟩ := hp have hpw : path.Pairwise (· < ·) := jumpLaw_pairwise path none h4 have hspw : input.Pairwise (· < ·) := valid_pairwise input h have hss : path ⊆ input := fun x hx => h3 x hx have hsub : path.Sublist input := List.sublist_of_subperm_of_pairwise (List.subperm_of_subset hpw.nodup hss) hpw hspw obtain ⟨mask, hmask⟩ := exists_mask_decodePath input path hsub refine ⟨mask, ?_⟩ rw [hmask] exact (isFrogPathOk_iff _ _).mpr ⟨h1, h2, h3, h4⟩ /-! ### Implementation helpers -/ /-- Index of `target` within `arr[lo], …, arr[hi − 1]` when `arr` is sorted, by binary search. -/ def binFind (arr : Array Nat) (target lo hi : Nat) : Option Nat := if lo < hi then if arr[(lo + hi) / 2]! = target then some ((lo + hi) / 2) else if arr[(lo + hi) / 2]! < target then binFind arr target ((lo + hi) / 2 + 1) hi else binFind arr target lo ((lo + hi) / 2) else none termination_by hi - lo decreasing_by all_goals omega /-- Position-to-index lookup built once from the input: the stone array queried by binary search. -/ def stoneIndexMap (stones : List Nat) : Nat → Option Nat := let arr := stones.toArray fun target => binFind arr target 0 arr.size /-- From stone `i` reached by jump `k`, record each lawful positive next jump at its target stone. -/ def propagate (arr : Array Nat) (lookup : Nat → Option Nat) (i k : Nat) (acc : Array (List Nat)) : Array (List Nat) := [k - 1, k, k + 1].foldl (fun a k' => let q := arr[i]! + k' if jumpLawOk (some k) [arr[i]!, q] then match lookup q with | some j => if (a[j]!).contains k' then a else a.setIfInBounds j (k' :: a[j]!) | none => a else a) acc /-- Left-to-right sweep of the table: at stone `i`, expand every jump length stored for it. -/ def dpLoop (arr : Array Nat) (lookup : Nat → Option Nat) (i : Nat) (acc : Array (List Nat)) : Array (List Nat) := if i < arr.size then let acc := (acc[i]!).foldl (fun a k => propagate arr lookup i k a) acc dpLoop arr lookup (i + 1) acc else acc termination_by arr.size - i decreasing_by all_goals omega /-- Reachable last-jump lengths per stone index, seeded with the forced first jump of 1 and swept left to right. -/ def reachableJumps (stones : List Nat) : Array (List Nat) := let arr := stones.toArray let lookup := stoneIndexMap stones let seed : Array (List Nat) := match lookup (arr[0]! + 1) with | some j => (Array.replicate arr.size []).setIfInBounds j [1] | none => Array.replicate arr.size [] dpLoop arr lookup 0 seed /-! ### Main algorithm (impl) -/ /-- From stone `i` reached by jump `k`, try each lawful positive next jump, recording its landing stone in the flat reachability table; the returned flag is set when one of the jumps lands on the last stone. -/ def frogStep (arr : Array Nat) (lookup : Nat → Option Nat) (n width i k : Nat) (reach : Array Bool) : Array Bool × Bool := [k - 1, k, k + 1].foldl (fun (p : Array Bool × Bool) k' => let (reach, done) := p if done then p else if k' = 0 then p else match lookup (arr[i]! + k') with | none => p | some j => if j = n - 1 then (reach, true) else let idx := j * width + k' if h : idx < reach.size then (reach.set idx true h, false) else (reach, false)) (reach, false) /-- Scan every jump length that could have landed on stone `i` and expand the reachable ones. -/ def frogScanStone (arr : Array Nat) (lookup : Nat → Option Nat) (n width i k : Nat) (reach : Array Bool) : Array Bool × Bool := if k ≤ n then if reach[i * width + k]! then let (reach, done) := frogStep arr lookup n width i k reach if done then (reach, true) else frogScanStone arr lookup n width i (k + 1) reach else frogScanStone arr lookup n width i (k + 1) reach else (reach, false) termination_by n + 1 - k decreasing_by all_goals omega /-- Sweep the stones left to right; true as soon as a lawful jump lands on the last stone. -/ def frogSweepAll (arr : Array Nat) (lookup : Nat → Option Nat) (n width i : Nat) (reach : Array Bool) : Bool := if i < n then let (reach, done) := frogScanStone arr lookup n width i 1 reach if done then true else frogSweepAll arr lookup n width (i + 1) reach else false termination_by n - i decreasing_by all_goals omega /-- Dynamic programming over reachable (stone, last-jump) states kept in one flat boolean table with O(1) membership; true exactly when some jump lands on the last stone. -/ def canCrossFrog (input : Input) : Output := let arr := input.toArray let n := arr.size if n < 2 then false else let width := n + 2 let lookup : Nat → Option Nat := fun target => binFind arr target 0 n let reach : Array Bool := Array.replicate (n * width) false match lookup (arr[0]! + 1) with | none => false | some j => if j = n - 1 then true else let idx := j * width + 1 if h : idx < reach.size then frogSweepAll arr lookup n width 1 (reach.set idx true h) else false /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem canCrossFrog_correct (input : Input) (h : isValidInput input) : canCross_spec input (canCrossFrog input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [0, 1, 3, 5, 6, 8, 12, 17] #guard isValidInput [0, 1, 2, 3, 4, 8, 9, 11] #guard isValidInput [0, 2] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput [0]) #guard !(isValidInput [0, 2147483648]) #guard !(isValidInput [1, 2]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard canCross_check [0, 1, 3, 5, 6, 8, 12, 17] true #guard canCross_check [0, 1, 2, 3, 4, 8, 9, 11] false #guard canCross_check [0, 2] false /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(canCross_check [0, 1, 3, 5, 6, 8, 12, 17] false) #guard !(canCross_check [0, 1, 2, 3, 4, 8, 9, 11] true) #guard !(canCross_check [0, 2] true) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard canCrossFrog [0, 1, 3, 5, 6, 8, 12, 17] == true #guard canCrossFrog [0, 1, 2, 3, 4, 8, 9, 11] == false #guard canCrossFrog [0, 2] == false /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard canCross_check [0, 1, 3, 5, 6, 8, 12, 17] (canCrossFrog [0, 1, 3, 5, 6, 8, 12, 17]) #guard canCross_check [0, 1, 2, 3, 4, 8, 9, 11] (canCrossFrog [0, 1, 2, 3, 4, 8, 9, 11]) #guard canCross_check [0, 2] (canCrossFrog [0, 2]) end PFrogJump