import Mathlib /-! # Circular Array Loop You are playing a game involving a circular array of non-zero integers nums. Each nums[i] denotes the number of indices forward/backward you must move if you are located at index i: If nums[i] is positive, move nums[i] steps forward, and If nums[i] is negative, move |nums[i]| steps backward. Since the array is circular, you may assume that moving forward from the last element puts you on the first element, and moving backwards from the first element puts you on the last element. A cycle in the array consists of a sequence of indices seq of length k where: Following the movement rules above results in the repeating index sequence seq[0] -> seq[1] -> ... -> seq[k - 1] -> seq[0] -> ... Every nums[seq[j]] is either all positive or all negative. k > 1 Return true if there is a cycle in nums, or false otherwise. ## Constraints - 1 <= nums.length <= 5000 - -1000 <= nums[i] <= 1000 - nums[i] != 0 ## Provided examples - `nums = [2, -1, 1, 2, 2]` → `true` - `nums = [-1, -2, -3, -4, -5, 6]` → `false` - `nums = [1, -1, 5, 1, 4]` → `true` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= nums.length <= 5000. empty array where at least one element is required) - invalid input: `nums = [1001]` ([structural] a predicate that admits -1000 <= nums[i] <= 1000. one past the upper value bound; forgot ceiling) - invalid input: `nums = [0]` ([structural] a predicate that admits nums[i] != 0. zero where every element must be non-zero) - `nums = [2, -1, 1, 2, 2]` → `false` is wrong ([structural] nothing requires the answer to be true when a cycle exists. false is the default returned without finding the cycle) - `nums = [-1, -2, -3, -4, -5, 6]` → `true` is wrong ([structural] does not require the indices in seq to be distinct, so the self-loop at index 5 is accepted as a length-2 cycle. seq [5,5] satisfies k>1 and sign; distinctness alone rejects) - `nums = [1, -1, 5, 1, 4]` → `false` is wrong ([structural] movement is not required to wrap around the array. cycle 3->4 depends on wrapping; linear reading finds none) -/ namespace PCircularArrayLoop abbrev Input := List Int abbrev Output := Bool /-! ### Specification helpers -/ /-- The index reached from `i` by moving `nums[i]` steps around the circular array, or 0 when `i` is out of bounds. -/ def nextIndex (nums : List Int) (i : ℕ) : ℕ := if h : i < nums.length then (((i : ℤ) + nums[i]) % (nums.length : ℤ)).toNat else 0 /-- A cycle exists in `nums`: two or more pairwise distinct indices, each reached from its predecessor and the first from the last by the movement rule, with every visited value positive or every one negative. -/ def IsCycle (nums : List Int) : Prop := ∃ seq : List ℕ, ∃ hlen : 2 ≤ seq.length, ∃ hvalid : ∀ i ∈ seq, i < nums.length, seq.Pairwise (· ≠ ·) ∧ (∀ j : ℕ, ∀ hj : j < seq.length, nextIndex nums (seq[j]'hj) = seq[(j + 1) % seq.length]'(Nat.mod_lt _ (by omega))) ∧ ((∀ i : ℕ, ∀ hi : i ∈ seq, 0 < nums[i]'(hvalid i hi)) ∨ (∀ i : ℕ, ∀ hi : i ∈ seq, nums[i]'(hvalid i hi) < 0)) /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 5000 non-zero integers, each between -1000 and 1000 inclusive. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 5000 && input.all (fun x => x ≠ 0 && -1000 ≤ x && x ≤ 1000) /-! ### Ideal specification (P_spec) -/ /-- `result` is true exactly when `input` contains a cycle. -/ def hasCycle_spec (input : Input) (result : Output) : Prop := result ↔ IsCycle input /-! ### Decidable specification (P_check) -/ /-- The `len`-element candidate cycle from `start`: the iterates of the specification's `nextIndex`. -/ def cycleCandidate (nums : List Int) (start len : ℕ) : List ℕ := (List.range len).map fun k => Nat.iterate (nextIndex nums) k start /-- Whether `seq` satisfies the `IsCycle` clauses: length, valid indices, distinctness, movement with wrap-around, one sign. -/ def cycleSeqOk (nums : List Int) (seq : List ℕ) : Bool := 2 ≤ seq.length && seq.all (fun i => i < nums.length) && decide (seq.Pairwise (· ≠ ·)) && (List.finRange seq.length).all (fun j => nextIndex nums seq[j.val]! == seq[(j.val + 1) % seq.length]!) && (seq.all (fun i => 0 < nums.getD i 0) || seq.all (fun i => nums.getD i 0 < 0)) /-- Whether some `(start, len)` code with `2 ≤ len ≤ nums.length` decodes to a cycle of `nums`. -/ def cycleExistsBounded (nums : List Int) : Bool := (List.finRange nums.length).any fun start => (List.range' 2 (nums.length - 1)).any fun len => cycleSeqOk nums (cycleCandidate nums start.val len) /-- Executable checker for `hasCycle_spec`: `result` matches bounded cycle existence. -/ def hasCycle_check (input : Input) (result : Output) : Bool := result == cycleExistsBounded input /-- The orbit of `nextIndex` from `seq[0]` reproduces `seq`. -/ theorem cal_orbit_eq (nums : List Int) (seq : List ℕ) (hlen : 0 < seq.length) (hmove : ∀ j : ℕ, ∀ hj : j < seq.length, nextIndex nums (seq[j]'hj) = seq[(j + 1) % seq.length]'(Nat.mod_lt _ hlen)) : ∀ j : ℕ, ∀ hj : j < seq.length, (nextIndex nums)^[j] (seq[0]'hlen) = seq[j]'hj := by intro j induction j with | zero => intro hj; simp | succ j ih => intro hj have hjlt : j < seq.length := by omega rw [Function.iterate_succ_apply', ih hjlt, hmove j hjlt] exact getElem_congr_idx (Nat.mod_eq_of_lt hj) /-- The candidate enumerated from `seq[0]` at length `seq.length` is `seq` itself. -/ theorem cal_cycleCandidate_eq (nums : List Int) (seq : List ℕ) (hlen : 0 < seq.length) (hmove : ∀ j : ℕ, ∀ hj : j < seq.length, nextIndex nums (seq[j]'hj) = seq[(j + 1) % seq.length]'(Nat.mod_lt _ hlen)) : cycleCandidate nums (seq[0]'hlen) seq.length = seq := by apply List.ext_getElem · simp [cycleCandidate] · intro j h1 h2 have hstep : (cycleCandidate nums (seq[0]'hlen) seq.length)[j]'h1 = (nextIndex nums)^[j] (seq[0]'hlen) := by simp [cycleCandidate] rw [hstep] exact cal_orbit_eq nums seq hlen hmove j h2 /-- A duplicate-free list of naturals below `n` has at most `n` entries. -/ theorem cal_nodup_length_le (seq : List ℕ) (n : ℕ) (hnd : seq.Pairwise (· ≠ ·)) (hlt : ∀ i ∈ seq, i < n) : seq.length ≤ n := by have hnd' : seq.Nodup := hnd have hsub : seq.toFinset ⊆ Finset.range n := by intro x hx rw [List.mem_toFinset] at hx rw [Finset.mem_range] exact hlt x hx have hcard := Finset.card_le_card hsub rwa [List.toFinset_card_of_nodup hnd', Finset.card_range] at hcard /-- `cycleSeqOk` accepting `seq` makes `seq` a witness for `IsCycle`. -/ theorem cal_cycleSeqOk_sound (nums : List Int) (seq : List ℕ) (h : cycleSeqOk nums seq = true) : IsCycle nums := by unfold cycleSeqOk at h simp only [Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, Bool.or_eq_true, beq_iff_eq] at h obtain ⟨⟨⟨⟨hlen, hvalid⟩, hnd⟩, hmv⟩, hsign⟩ := h have hmvN : ∀ j : ℕ, j < seq.length → nextIndex nums seq[j]! = seq[(j + 1) % seq.length]! := fun j hj => hmv ⟨j, hj⟩ (List.mem_finRange _) refine ⟨seq, hlen, hvalid, hnd, ?_, ?_⟩ · intro j hj have hstep := hmvN j hj rwa [getElem!_pos seq j hj, getElem!_pos seq ((j + 1) % seq.length) (Nat.mod_lt _ (by omega))] at hstep · rcases hsign with hpos | hneg · left intro i hi rw [← List.getD_eq_getElem nums 0 (hvalid i hi)] exact hpos i hi · right intro i hi rw [← List.getD_eq_getElem nums 0 (hvalid i hi)] exact hneg i hi /-- A witness for `IsCycle` is accepted by `cycleSeqOk`. -/ theorem cal_cycleSeqOk_complete (nums : List Int) (seq : List ℕ) (hlen : 2 ≤ seq.length) (hvalid : ∀ i ∈ seq, i < nums.length) (hnd : seq.Pairwise (· ≠ ·)) (hmove : ∀ j : ℕ, ∀ hj : j < seq.length, nextIndex nums (seq[j]'hj) = seq[(j + 1) % seq.length]'(Nat.mod_lt _ (by omega))) (hsign : (∀ i : ℕ, ∀ hi : i ∈ seq, 0 < nums[i]'(hvalid i hi)) ∨ (∀ i : ℕ, ∀ hi : i ∈ seq, nums[i]'(hvalid i hi) < 0)) : cycleSeqOk nums seq = true := by unfold cycleSeqOk simp only [Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, Bool.or_eq_true, beq_iff_eq] refine ⟨⟨⟨⟨hlen, fun i hi => hvalid i hi⟩, hnd⟩, ?_⟩, ?_⟩ · intro j _ have hj : j.val < seq.length := j.isLt rw [getElem!_pos seq j.val hj, getElem!_pos seq ((j.val + 1) % seq.length) (Nat.mod_lt _ (by omega))] exact hmove j.val hj · rcases hsign with hpos | hneg · left intro i hi rw [List.getD_eq_getElem nums 0 (hvalid i hi)] exact hpos i hi · right intro i hi rw [List.getD_eq_getElem nums 0 (hvalid i hi)] exact hneg i hi /-- The bounded enumeration decides `IsCycle` on a nonempty array. -/ theorem cal_cycleExistsBounded_iff (nums : List Int) (hne : 1 ≤ nums.length) : cycleExistsBounded nums = true ↔ IsCycle nums := by constructor · intro hc unfold cycleExistsBounded at hc rw [List.any_eq_true] at hc obtain ⟨start, _, hc⟩ := hc rw [List.any_eq_true] at hc obtain ⟨len, _, hc⟩ := hc exact cal_cycleSeqOk_sound nums _ hc · intro hcyc obtain ⟨seq, hlen, hvalid, hnd, hmove, hsign⟩ := hcyc have h0 : 0 < seq.length := by omega have hstart : seq[0]'h0 < nums.length := hvalid _ (List.getElem_mem h0) have hle : seq.length ≤ nums.length := cal_nodup_length_le seq nums.length hnd hvalid unfold cycleExistsBounded rw [List.any_eq_true] refine ⟨⟨seq[0]'h0, hstart⟩, List.mem_finRange _, ?_⟩ rw [List.any_eq_true] refine ⟨seq.length, ?_, ?_⟩ · rw [List.mem_range'_1] omega · rw [cal_cycleCandidate_eq nums seq h0 hmove] exact cal_cycleSeqOk_complete nums seq hlen hvalid hnd hmove hsign /-- On valid input the checker accepts exactly the specified outputs. -/ theorem hasCycle_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : hasCycle_check input result ↔ hasCycle_spec input result := by have hlenpos : 1 ≤ input.length := by simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq] at h omega have key := cal_cycleExistsBounded_iff input hlenpos unfold hasCycle_check hasCycle_spec cases result <;> cases hb : cycleExistsBounded input <;> simp_all /-! ### Implementation helpers -/ /-- The index reached from `i` by moving `arr[i]!` steps around `arr`, with O(1) array lookup. -/ def nextIndexArr (arr : Array Int) (i : Nat) : Nat := (((i : Int) + arr[i]!) % (arr.size : Int)).toNat /-- Number of zero (unmarked) entries of the token array; the termination measure for `advance`. -/ def unvisitedCount (visited : Array Nat) : Nat := visited.toList.count 0 /-- Walk from `cur` marking fresh nodes with token `t + 1`, returning the new marks and whether the walk re-entered its own token before a self-loop or sign change. -/ def advance (arr : Array Int) (signPos : Bool) (t : Nat) (visited : Array Nat) (cur : Nat) (h : cur < visited.size) (hsz : visited.size = arr.size) : { v : Array Nat // v.size = arr.size } × Bool := if hzero : visited[cur] = 0 then if nextIndexArr arr cur = cur then (⟨visited.set cur (t + 1) h, by simpa using hsz⟩, false) else if decide (0 < arr[cur]!) == signPos then have hnxt : nextIndexArr arr cur < (visited.set cur (t + 1) h).size := by rw [Array.size_set] have hpos : (0 : Int) < (arr.size : Int) := by have hs : 0 < arr.size := by omega exact_mod_cast hs have h1 : 0 ≤ ((cur : Int) + arr[cur]!) % (arr.size : Int) := Int.emod_nonneg _ (by omega) have h2 : ((cur : Int) + arr[cur]!) % (arr.size : Int) < (arr.size : Int) := Int.emod_lt_of_pos _ hpos have h3 : (((cur : Int) + arr[cur]!) % (arr.size : Int)).toNat < arr.size := (Int.toNat_lt h1).mpr h2 have h4 : nextIndexArr arr cur < arr.size := h3 omega advance arr signPos t (visited.set cur (t + 1) h) (nextIndexArr arr cur) hnxt (by simpa using hsz) else (⟨visited, hsz⟩, false) else (⟨visited, hsz⟩, visited[cur] == t + 1) termination_by unvisitedCount visited decreasing_by have key : ∀ (l : List Nat) (i : Nat) (hi : i < l.length) (b : Nat), l[i] = 0 → b ≠ 0 → (l.set i b).count 0 < l.count 0 := by intro l induction l with | nil => intro i hi b _ _; simp at hi | cons a l ih => intro i hi b hget hb cases i with | zero => simp only [List.getElem_cons_zero] at hget subst hget have hb0 : (b == 0) = false := by cases hbq : (b == 0) with | false => rfl | true => exact absurd (beq_iff_eq.mp hbq) hb have hb0' : ((0 : Nat) == b) = false := by cases hbq : ((0 : Nat) == b) with | false => rfl | true => exact absurd (beq_iff_eq.mp hbq).symm hb simp only [List.set_cons_zero, List.count_cons, hb0, hb0', beq_self_eq_true] simp_all <;> omega | succ i => simp only [List.length_cons] at hi have hi' : i < l.length := by omega simp only [List.getElem_cons_succ] at hget have hrec := ih i hi' b hget hb simp only [List.set_cons_succ, List.count_cons] split <;> omega have hz : visited.toList[cur]'(by simpa using h) = 0 := by simp_all have hk := key visited.toList cur (by simpa using h) (t + 1) hz (by omega) simp_all [unvisitedCount, Array.toList_set] /-! ### Main algorithm (impl) -/ /-- Token-marking traversal of the index functional graph: true iff some start's walk meets its own token again, an O(n) cycle detection. -/ def hasCircularArrayLoop (input : Input) : Output := let arr := input.toArray let init : { v : Array Nat // v.size = arr.size } × Bool := (⟨Array.replicate arr.size 0, by simp⟩, false) ((List.range arr.size).foldl (fun (acc : { v : Array Nat // v.size = arr.size } × Bool) (i : Nat) => if acc.2 then acc else if h : i < arr.size then advance arr (decide (0 < arr[i]!)) i acc.1.1 i (by rwa [acc.1.2]) acc.1.2 else acc) init).2 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem hasCircularArrayLoop_correct (input : Input) (h : isValidInput input) : hasCycle_spec input (hasCircularArrayLoop input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [2, (-1), 1, 2, 2] #guard isValidInput [(-1), (-2), (-3), (-4), (-5), 6] #guard isValidInput [1, (-1), 5, 1, 4] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [1001]) #guard !(isValidInput [0]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard hasCycle_check [2, (-1), 1, 2, 2] true #guard hasCycle_check [(-1), (-2), (-3), (-4), (-5), 6] false #guard hasCycle_check [1, (-1), 5, 1, 4] true /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(hasCycle_check [2, (-1), 1, 2, 2] false) #guard !(hasCycle_check [(-1), (-2), (-3), (-4), (-5), 6] true) #guard !(hasCycle_check [1, (-1), 5, 1, 4] false) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard hasCircularArrayLoop [2, (-1), 1, 2, 2] == true #guard hasCircularArrayLoop [(-1), (-2), (-3), (-4), (-5), 6] == false #guard hasCircularArrayLoop [1, (-1), 5, 1, 4] == true /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard hasCycle_check [2, (-1), 1, 2, 2] (hasCircularArrayLoop [2, (-1), 1, 2, 2]) #guard hasCycle_check [(-1), (-2), (-3), (-4), (-5), 6] (hasCircularArrayLoop [(-1), (-2), (-3), (-4), (-5), 6]) #guard hasCycle_check [1, (-1), 5, 1, 4] (hasCircularArrayLoop [1, (-1), 5, 1, 4]) end PCircularArrayLoop