import Mathlib /-! # 4Sum Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that: 0 <= a, b, c, d < n a, b, c, and d are distinct. nums[a] + nums[b] + nums[c] + nums[d] == target You may return the answer in any order. ## Constraints - 1 <= nums.length <= 200 - -10^9 <= nums[i] <= 10^9 - -10^9 <= target <= 10^9 ## Provided examples - `nums = [1, 0, -1, 0, -2, 2], target = 0` → `[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]` - `nums = [2, 2, 2, 2, 2], target = 8` → `[[2, 2, 2, 2]]` - `nums = [0, 0, 0, 0], target = 0` → `[[0, 0, 0, 0]]` ## Synthesized negative examples - invalid input: `nums = [], target = 0` ([structural] a predicate that admits 1 <= nums.length <= 200. empty where at least one element is required) - invalid input: `nums = [1000000001], target = 0` ([structural] a predicate that admits -10^9 <= nums[i] <= 10^9. one above the stated element maximum) - invalid input: `nums = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], target = 0` ([structural] a predicate that admits 1 <= nums.length <= 200. 201 entries, one above the maximum length) - `nums = [1, 0, -1, 0, -2, 2], target = 0` → `[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1], [-2, 0, 2]]` is wrong ([structural] members are not required to have four elements. a three-element list appears where a quadruplet is required) - `nums = [2, 2, 2, 2, 2], target = 8` → `[]` is wrong ([structural] nothing requires every valid quadruplet to appear. empty list misses the true quadruplet) - `nums = [0, 0, 0, 0], target = 0` → `[[0, 0, 0, 0], [0, 0, 0, 0]]` is wrong ([structural] uniqueness of quadruplets is not required. duplicates the single valid quadruplet) -/ namespace P4sum abbrev Input := (List Int) × (Int) abbrev Output := List (List Int) /-! ### Specification helpers -/ /-- `q` is a permutation of the values at four pairwise distinct indices of `nums` summing to `target`. -/ def IsValidQuadruplet (nums : List Int) (target : Int) (q : List Int) : Prop := ∃ a b c d : Fin nums.length, a ≠ b ∧ a ≠ c ∧ a ≠ d ∧ b ≠ c ∧ b ≠ d ∧ c ≠ d ∧ q.Perm [nums[a], nums[b], nums[c], nums[d]] ∧ nums[a] + nums[b] + nums[c] + nums[d] = target /-! ### Validity predicate (V) -/ /-- Valid input: length in [1, 200], every entry and the target within ±10^9. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 200 && input.1.all (fun x => -1000000000 ≤ x && x ≤ 1000000000) && -1000000000 ≤ input.2 && input.2 ≤ 1000000000 /-! ### Ideal specification (P_spec) -/ /-- `result` contains exactly the valid quadruplets of `input`, each represented once up to permutation, in any order. -/ def fourSum_spec (input : Input) (result : Output) : Prop := (∀ q ∈ result, IsValidQuadruplet input.1 input.2 q) ∧ result.Pairwise (fun q₁ q₂ => ¬ q₁.Perm q₂) ∧ ∀ q : List Int, IsValidQuadruplet input.1 input.2 q → ∃ r ∈ result, r.Perm q /-! ### Decidable specification (P_check) -/ /-- Strictly increasing quadruples of indices into a list of length `n`. -/ def indexQuadruples (n : Nat) : List (Fin n × Fin n × Fin n × Fin n) := (List.finRange n).flatMap fun a => (List.finRange n).flatMap fun b => if a < b then (List.finRange n).flatMap fun c => if b < c then (List.finRange n).filterMap fun d => if c < d then some (a, b, c, d) else none else [] else [] /-- The four values selected by an increasing index quadruple. -/ def quadValues (nums : List Int) (t : Fin nums.length × Fin nums.length × Fin nums.length × Fin nums.length) : List Int := [nums[t.1], nums[t.2.1], nums[t.2.2.1], nums[t.2.2.2]] /-- The sum of the four values selected by an increasing index quadruple. -/ def quadSum (nums : List Int) (t : Fin nums.length × Fin nums.length × Fin nums.length × Fin nums.length) : Int := nums[t.1] + nums[t.2.1] + nums[t.2.2.1] + nums[t.2.2.2] /-- Boolean test: `q` is a permutation of the values of some increasing index quadruple of `nums` whose sum is `target`. -/ def isValidQuadBool (nums : List Int) (target : Int) (q : List Int) : Bool := (indexQuadruples nums.length).any fun t => quadSum nums t == target && q.isPerm (quadValues nums t) /-- Boolean test: no two distinct entries of `l` are permutations of each other. -/ def noPermPairs (l : List (List Int)) : Bool := match l with | [] => true | x :: xs => xs.all (fun y => !x.isPerm y) && noPermPairs xs /-- Executable checker for `fourSum_spec` over increasing index quadruples. -/ def fourSum_check (input : Input) (result : Output) : Bool := result.all (fun q => isValidQuadBool input.1 input.2 q) && noPermPairs result && (indexQuadruples input.1.length).all fun t => !(quadSum input.1 t == input.2) || result.any (fun r => r.isPerm (quadValues input.1 t)) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem fourSum_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : fourSum_check input result ↔ fourSum_spec input result := by have getF (i : Fin input.1.length) : input.1[i] = input.1[i.val] := rfl have memq (a b c d : Fin input.1.length) : (a,b,c,d) ∈ indexQuadruples input.1.length ↔ a < b ∧ b < c ∧ c < d := by simp [indexQuadruples] have repr (q : List Int) : IsValidQuadruplet input.1 input.2 q ↔ ∃ t ∈ indexQuadruples input.1.length, quadSum input.1 t = input.2 ∧ q.Perm (quadValues input.1 t) := by constructor · rintro ⟨a,b,c,d,hab,hac,had,hbc,hbd,hcd,hp,hs⟩ simp only [getF] at hp hs have order : (a < b ∧ b < c ∧ c < d) ∨ (a < b ∧ b < d ∧ d < c) ∨ (a < c ∧ c < b ∧ b < d) ∨ (a < c ∧ c < d ∧ d < b) ∨ (a < d ∧ d < b ∧ b < c) ∨ (a < d ∧ d < c ∧ c < b) ∨ (b < a ∧ a < c ∧ c < d) ∨ (b < a ∧ a < d ∧ d < c) ∨ (b < c ∧ c < a ∧ a < d) ∨ (b < c ∧ c < d ∧ d < a) ∨ (b < d ∧ d < a ∧ a < c) ∨ (b < d ∧ d < c ∧ c < a) ∨ (c < a ∧ a < b ∧ b < d) ∨ (c < a ∧ a < d ∧ d < b) ∨ (c < b ∧ b < a ∧ a < d) ∨ (c < b ∧ b < d ∧ d < a) ∨ (c < d ∧ d < a ∧ a < b) ∨ (c < d ∧ d < b ∧ b < a) ∨ (d < a ∧ a < b ∧ b < c) ∨ (d < a ∧ a < c ∧ c < b) ∨ (d < b ∧ b < a ∧ a < c) ∨ (d < b ∧ b < c ∧ c < a) ∨ (d < c ∧ c < a ∧ a < b) ∨ (d < c ∧ c < b ∧ b < a) := by by_cases hba : b < a · by_cases hcb : c < b · by_cases hdc : d < c · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (⟨by omega,by omega,by omega⟩))))))))))))))))))))))) · by_cases hdb : d < b · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩)))))))))))))))))) · by_cases hda : d < a · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩)))))))))))))))) · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩))))))))))))))) · by_cases hca : c < a · by_cases hdb : d < b · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩)))))))))))))))))))))) · by_cases hdc : d < c · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩)))))))))))) · by_cases hda : d < a · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩)))))))))) · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩))))))))) · by_cases hdb : d < b · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩))))))))))))))))))))) · by_cases hda : d < a · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩))))))))))) · by_cases hdc : d < c · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩)))))))) · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩))))))) · by_cases hca : c < a · by_cases hdc : d < c · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩))))))))))))))))))))))) · by_cases hda : d < a · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩))))))))))))))))) · by_cases hdb : d < b · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩)))))))))))))) · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩))))))))))))) · by_cases hcb : c < b · by_cases hda : d < a · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩)))))))))))))))))))) · by_cases hdc : d < c · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩)))))) · by_cases hdb : d < b · exact Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩)))) · exact Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩))) · by_cases hda : d < a · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩))))))))))))))))))) · by_cases hdb : d < b · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inl (⟨by omega,by omega,by omega⟩))))) · by_cases hdc : d < c · exact Or.inr (Or.inl (⟨by omega,by omega,by omega⟩)) · exact Or.inl (⟨by omega,by omega,by omega⟩) rcases order with ho | ho | ho | ho | ho | ho | ho | ho | ho | ho | ho | ho | ho | ho | ho | ho | ho | ho | ho | ho | ho | ho | ho | ho · refine ⟨(a,b,c,d),(memq a b c d).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(a,b,d,c),(memq a b d c).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(a,c,b,d),(memq a c b d).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(a,c,d,b),(memq a c d b).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(a,d,b,c),(memq a d b c).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(a,d,c,b),(memq a d c b).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(b,a,c,d),(memq b a c d).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(b,a,d,c),(memq b a d c).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(b,c,a,d),(memq b c a d).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(b,c,d,a),(memq b c d a).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(b,d,a,c),(memq b d a c).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(b,d,c,a),(memq b d c a).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(c,a,b,d),(memq c a b d).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(c,a,d,b),(memq c a d b).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(c,b,a,d),(memq c b a d).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(c,b,d,a),(memq c b d a).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(c,d,a,b),(memq c d a b).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(c,d,b,a),(memq c d b a).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(d,a,b,c),(memq d a b c).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(d,a,c,b),(memq d a c b).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(d,b,a,c),(memq d b a c).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(d,b,c,a),(memq d b c a).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(d,c,a,b),(memq d c a b).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · refine ⟨(d,c,b,a),(memq d c b a).mpr ho,?_,?_⟩ · dsimp [quadSum]; omega · dsimp [quadValues] apply hp.trans rw [List.perm_iff_count] intro x simp only [List.count_cons,List.count_nil] <;> omega · rintro ⟨⟨a,b,c,d⟩,ht,hs,hp⟩ obtain ⟨hab,hbc,hcd⟩ := (memq a b c d).mp ht refine ⟨a,b,c,d,by omega,by omega,by omega,by omega,by omega,by omega,hp,hs⟩ have qb (q : List Int) : isValidQuadBool input.1 input.2 q = true ↔ IsValidQuadruplet input.1 input.2 q := by rw [repr] simp [isValidQuadBool,List.isPerm_iff] have np (l : List (List Int)) : noPermPairs l = true ↔ l.Pairwise (fun a b => ¬ a.Perm b) := by induction l with | nil => simp [noPermPairs] | cons a l ih => simp only [noPermPairs,Bool.and_eq_true,List.all_eq_true,Bool.not_eq_true',List.pairwise_cons,ih] have neg (b : List Int) : a.isPerm b = false ↔ ¬ a.Perm b := by rw [Bool.eq_false_iff] exact not_congr List.isPerm_iff simp only [neg] simp only [fourSum_check,Bool.and_eq_true,List.all_eq_true,qb,np, Bool.or_eq_true,Bool.not_eq_true',List.any_eq_true,List.isPerm_iff,beq_iff_eq,fourSum_spec] constructor · rintro ⟨⟨hv,hn⟩,hu⟩ refine ⟨hv,hn,?_⟩ intro q hq obtain ⟨t,ht,hs,hp⟩ := (repr q).mp hq rcases hu t ht with hf | ⟨r,hr,hperm⟩ · simp [hs] at hf · exact ⟨r,hr,hperm.trans hp.symm⟩ · rintro ⟨hv,hn,hu⟩ refine ⟨⟨hv,hn⟩,?_⟩ intro t ht by_cases hs : quadSum input.1 t = input.2 · right exact hu _ ((repr _).mpr ⟨t,ht,hs,List.Perm.refl _⟩) · left; simp [hs] /-! ### Implementation helpers -/ /-- Convert the input list to an ascending-sorted array for the two-pointer scan. -/ def toSortedArray (nums : List Int) : Array Int := nums.toArray.qsort (fun a b => a < b) /-- Two-pointer scan on `arr[lo .. hi]` for pairs summing to `rem`; mode 1 advances `lo` past duplicates of `v`, mode 2 advances `hi` past duplicates of `v`. -/ def twoSumFromPair (arr : Array Int) (lo hi mode : Nat) (v rem : Int) : List (Int × Int) := if h : lo < hi then let a := arr[lo]! let b := arr[hi]! if mode = 1 then if a == v then twoSumFromPair arr (lo + 1) hi 1 v rem else twoSumFromPair arr lo (hi - 1) 2 b rem else if mode = 2 && b == v then twoSumFromPair arr lo (hi - 1) 2 v rem else if a + b == rem then (a, b) :: twoSumFromPair arr (lo + 1) hi 1 a rem else if a + b < rem then twoSumFromPair arr (lo + 1) hi 0 0 rem else twoSumFromPair arr lo (hi - 1) 0 0 rem else [] termination_by hi - lo decreasing_by all_goals omega /-- For fixed first index `i`, scan second index `j` with duplicate skipping and collect all quadruplets. -/ def fourSumFromI (arr : Array Int) (target : Int) (i j : Nat) : Output := if h : j + 2 < arr.size then let quads := if i + 1 < j && arr[j]! == arr[j - 1]! then [] else let rem := target - arr[i]! - arr[j]! (twoSumFromPair arr (j + 1) (arr.size - 1) 0 0 rem).map (fun p => [arr[i]!, arr[j]!, p.1, p.2]) quads ++ fourSumFromI arr target i (j + 1) else [] termination_by arr.size - j decreasing_by omega /-- Outer loop over first index `i` with duplicate skipping. -/ def fourSumOuter (arr : Array Int) (target : Int) (i : Nat) : Output := if h : i + 3 < arr.size then let quads := if 0 < i && arr[i]! == arr[i - 1]! then [] else fourSumFromI arr target i (i + 1) quads ++ fourSumOuter arr target (i + 1) else [] termination_by arr.size - i decreasing_by omega /-- Drive the nested i/j loops over the sorted array and append each quadruplet found. -/ def fourSumSorted (arr : Array Int) (target : Int) : Output := fourSumOuter arr target 0 /-! ### Main algorithm (impl) -/ /-- Sort, then the standard O(n^3) two-pointer 4Sum with duplicate skipping at every level. -/ def findFourSum (input : Input) : Output := fourSumSorted (toSortedArray input.1) input.2 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findFourSum_correct (input : Input) (h : isValidInput input) : fourSum_spec input (findFourSum input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([1, 0, (-1), 0, (-2), 2], 0) #guard isValidInput ([2, 2, 2, 2, 2], 8) #guard isValidInput ([0, 0, 0, 0], 0) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], 0)) #guard !(isValidInput ([1000000001], 0)) #guard !(isValidInput ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard fourSum_check ([1, 0, (-1), 0, (-2), 2], 0) [[(-2), (-1), 1, 2], [(-2), 0, 0, 2], [(-1), 0, 0, 1]] #guard fourSum_check ([2, 2, 2, 2, 2], 8) [[2, 2, 2, 2]] #guard fourSum_check ([0, 0, 0, 0], 0) [[0, 0, 0, 0]] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(fourSum_check ([1, 0, (-1), 0, (-2), 2], 0) [[(-2), (-1), 1, 2], [(-2), 0, 0, 2], [(-1), 0, 0, 1], [(-2), 0, 2]]) #guard !(fourSum_check ([2, 2, 2, 2, 2], 8) []) #guard !(fourSum_check ([0, 0, 0, 0], 0) [[0, 0, 0, 0], [0, 0, 0, 0]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findFourSum ([1, 0, -1, 0, -2, 2], 0) == [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] #guard findFourSum ([2, 2, 2, 2, 2], 8) == [[2, 2, 2, 2]] #guard findFourSum ([0, 0, 0, 0], 0) == [[0, 0, 0, 0]] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard fourSum_check ([1, 0, -1, 0, -2, 2], 0) (findFourSum ([1, 0, -1, 0, -2, 2], 0)) #guard fourSum_check ([2, 2, 2, 2, 2], 8) (findFourSum ([2, 2, 2, 2, 2], 8)) #guard fourSum_check ([0, 0, 0, 0], 0) (findFourSum ([0, 0, 0, 0], 0)) end P4sum