import Mathlib /-! # Arithmetic Slices An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same. For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences. Given an integer array nums, return the number of arithmetic subarrays of nums. A subarray is a contiguous subsequence of the array. ## Constraints - 1 <= nums.length <= 5000 - -1000 <= nums[i] <= 1000 ## Provided examples - `nums = [1, 2, 3, 4]` → `3` - `nums = [1]` → `0` - `nums = [2]` → `0` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= nums.length <= 5000. empty where at least one element is required) - invalid input: `nums = [-1001]` ([structural] a predicate that admits -1000 <= nums[i] <= 1000. one below the minimum element value) - invalid input: `nums = [1001]` ([structural] a predicate that admits -1000 <= nums[i] <= 1000. one above the maximum element value) - `nums = [1, 2, 3, 4]` → `2` is wrong ([structural] proper-subarrays-only reading omits the whole array. only the two length-3 subarrays are counted) - `nums = [1]` → `1` is wrong ([structural] the at-least-three-element condition is omitted. counts [1] as an arithmetic subarray) - `nums = [2]` → `-1` is wrong ([structural] count initialized one below zero. returns -1 when no arithmetic subarrays) -/ namespace PArithmeticSlices abbrev Input := List Int abbrev Output := Int /-! ### Specification helpers -/ /-- Indices `i` and `j` delimit a contiguous subarray `nums[i..j-1]` of length at least three whose consecutive differences are all equal. -/ def IsArithmeticSubarray (nums : List Int) (i j : Nat) : Prop := i + 3 ≤ j ∧ j ≤ nums.length ∧ ∃ d : Int, ((nums.drop i).take (j - i)).Chain' (fun a b => b - a = d) /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty list of at most 5000 elements, each in [-1000, 1000]. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 5000 && input.all (fun x => -1000 ≤ x && x ≤ 1000) /-! ### Ideal specification (P_spec) -/ /-- `result` is the count of arithmetic subarrays of `input`: it equals, as an integer, the cardinality of a finite set of index pairs that contains a pair exactly when that pair delimits an arithmetic subarray. -/ def countArithmeticSubarrays_spec (input : Input) (result : Output) : Prop := ∃ s : Finset (Nat × Nat), result = (s.card : Int) ∧ ∀ i j : Nat, (i, j) ∈ s ↔ IsArithmeticSubarray input i j /-! ### Decidable specification (P_check) -/ /-- Decides `List.Chain'` over `Int` for a decidable relation, by structural recursion: a chain on `a :: b :: l` is the first link plus the chain on `b :: l`, and inversion goes through the `cons_cons` constructor. This decides the consecutive-difference condition of `IsArithmeticSubarray` once the common difference is fixed. -/ instance decChain (R : Int → Int → Prop) [DecidableRel R] : (l : List Int) → Decidable (List.Chain' R l) | [] => isTrue (by constructor) | [a] => isTrue (by constructor) | a :: b :: l => match decChain R (b :: l) with | isTrue h2 => if h1 : R a b then isTrue (by constructor · exact h1 · exact h2) else isFalse (fun h => by cases h with | cons_cons h1' _ => exact h1 h1') | isFalse h2 => isFalse (fun h => by cases h with | cons_cons _ h2' => exact h2 h2') /-- Decides `∃ d : Int, l.Chain' (fun a b => b - a = d)`: for a list with at least two elements the common difference is forced to be the difference of the first two, so the unbounded `Int` existential reduces to a single decidable chain check; shorter lists satisfy `Chain'` trivially via its constructors. -/ instance decExistsChain : (l : List Int) → Decidable (∃ d : Int, List.Chain' (fun a b => b - a = d) l) | [] => isTrue ⟨0, by constructor⟩ | [a] => isTrue ⟨0, by constructor⟩ | a :: b :: t => match decChain (fun x y => y - x = b - a) (b :: t) with | isTrue h => isTrue ⟨b - a, by constructor · exact rfl · exact h⟩ | isFalse h => isFalse (fun hde => by obtain ⟨d, hd⟩ := hde cases hd with | cons_cons h1 h2 => have h1' : b - a = d := h1 subst h1' exact h h2) /-- Decides `IsArithmeticSubarray nums i j`: the index bounds are decidable `Nat` inequalities and the constant-difference condition on the explicit finite sublist `(nums.drop i).take (j - i)` is decided by `decExistsChain`. -/ instance decIsArith (nums : List Int) (i j : Nat) : Decidable (PArithmeticSlices.IsArithmeticSubarray nums i j) := inferInstanceAs (Decidable (i + 3 ≤ j ∧ j ≤ nums.length ∧ ∃ d : Int, List.Chain' (fun a b => b - a = d) ((nums.drop i).take (j - i)))) /-- Decides the ideal specification. Any pair delimiting an arithmetic subarray satisfies `i + 3 ≤ j ≤ nums.length`, so every such pair lies in the finite rectangle `[0, n] × [0, n]`, and a finset satisfying the membership equivalence must be exactly the arithmetic-subarray pairs of that rectangle. The specification therefore holds iff `result` equals the cardinality of the filtered rectangle, a decidable `Int` equality. -/ instance decCountSpec (input : List Int) (result : Int) : Decidable (∃ s : Finset (Nat × Nat), result = (s.card : Int) ∧ ∀ i j : Nat, (i, j) ∈ s ↔ PArithmeticSlices.IsArithmeticSubarray input i j) := decidable_of_iff (result = ((((Finset.range (input.length + 1)) ×ˢ (Finset.range (input.length + 1))).filter (fun p => PArithmeticSlices.IsArithmeticSubarray input p.1 p.2)).card : Int)) (by have memF : ∀ i j : Nat, ((i, j) ∈ ((Finset.range (input.length + 1)) ×ˢ (Finset.range (input.length + 1))).filter (fun p => PArithmeticSlices.IsArithmeticSubarray input p.1 p.2)) ↔ PArithmeticSlices.IsArithmeticSubarray input i j := by intro i j constructor · intro h exact (Finset.mem_filter.mp h).2 · intro hA apply Finset.mem_filter.mpr refine ⟨?_, hA⟩ rw [Finset.mem_product, Finset.mem_range, Finset.mem_range] show i < input.length + 1 ∧ j < input.length + 1 have h1 : i + 3 ≤ j := hA.1 have h2 : j ≤ input.length := hA.2.1 constructor <;> omega constructor · intro h exact ⟨_, h, memF⟩ · rintro ⟨s, hs, hiff⟩ have key : s = ((Finset.range (input.length + 1)) ×ˢ (Finset.range (input.length + 1))).filter (fun p => PArithmeticSlices.IsArithmeticSubarray input p.1 p.2) := by ext ⟨i, j⟩ rw [memF i j] exact hiff i j rw [key] at hs exact hs) /-- Executable checker obtained mechanically from the specification. -/ def countArithmeticSubarrays_check (input : Input) (result : Output) : Bool := @decide (countArithmeticSubarrays_spec input result) (by unfold countArithmeticSubarrays_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem countArithmeticSubarrays_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : countArithmeticSubarrays_check input result ↔ countArithmeticSubarrays_spec input result := by simp [countArithmeticSubarrays_check] /-! ### Implementation helpers -/ /-- One pass over the remaining list carrying the last two elements, the count `dp` of arithmetic subarrays ending at the previous element, and the running total. -/ def countArithmeticAux (prev2 prev1 : Int) (dp total : Nat) : List Int → Nat | [] => total | c :: rest => let newDp := if c - prev1 = prev1 - prev2 then dp + 1 else 0 countArithmeticAux prev1 c newDp (total + newDp) rest /-! ### Main algorithm (impl) -/ /-- Counts arithmetic subarrays by the single-pass arithmetic-slices DP: each element extends the run of equal consecutive differences or restarts it. -/ def numberOfArithmeticSubarrays (nums : Input) : Output := match nums with | a :: b :: rest => (countArithmeticAux a b 0 0 rest : Int) | _ => 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem numberOfArithmeticSubarrays_correct (input : Input) (h : isValidInput input) : countArithmeticSubarrays_spec input (numberOfArithmeticSubarrays input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [1, 2, 3, 4] #guard isValidInput [1] #guard isValidInput [2] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [(-1001)]) #guard !(isValidInput [1001]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard countArithmeticSubarrays_check [1, 2, 3, 4] 3 #guard countArithmeticSubarrays_check [1] 0 #guard countArithmeticSubarrays_check [2] 0 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(countArithmeticSubarrays_check [1, 2, 3, 4] 2) #guard !(countArithmeticSubarrays_check [1] 1) #guard !(countArithmeticSubarrays_check [2] (-1)) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard numberOfArithmeticSubarrays [1, 2, 3, 4] == 3 #guard numberOfArithmeticSubarrays [1] == 0 #guard numberOfArithmeticSubarrays [2] == 0 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard countArithmeticSubarrays_check [1, 2, 3, 4] (numberOfArithmeticSubarrays [1, 2, 3, 4]) #guard countArithmeticSubarrays_check [1] (numberOfArithmeticSubarrays [1]) #guard countArithmeticSubarrays_check [2] (numberOfArithmeticSubarrays [2]) end PArithmeticSlices