import Mathlib /-! # 3Sum Closest Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution. ## Constraints - 3 <= nums.length <= 500 - -1000 <= nums[i] <= 1000 - -10^4 <= target <= 10^4 ## Provided examples - `nums = [-1, 2, 1, -4], target = 1` → `2` - `nums = [0, 0, 0], target = 1` → `0` - `nums = [1, 1, 1, 1], target = 3` → `3` ## Synthesized negative examples - invalid input: `nums = [0, 0], target = 0` ([structural] a predicate that admits 3 <= nums.length <= 500. two elements; one below the minimum length) - invalid input: `nums = [1001, 0, 0], target = 0` ([structural] a predicate that admits -1000 <= nums[i] <= 1000. 1001; one above the element maximum) - invalid input: `nums = [10000, 0, 0], target = 0` ([structural] a predicate that admits -1000 <= nums[i] <= 1000. 10000; an order of magnitude above the element maximum) - `nums = [-1, 2, 1, -4], target = 1` → `1` is wrong ([structural] drops the distinctness condition on the chosen elements. 1 = 1+1+(-1) reuses the element 1; no distinct triple sums to 1) - `nums = [0, 0, 0], target = 1` → `1` is wrong ([structural] malformed_shape not applicable; answer need not be a triple sum. target 1 is closer than 0 but no triple sums to 1) - `nums = [1, 1, 1, 1], target = 3` → `2` is wrong ([structural] sums two integers instead of three. two ones sum to 2, one below the true three-integer sum) -/ namespace P3sumClosest abbrev Input := (List Int) × (Int) abbrev Output := Int /-! ### Specification helpers -/ /-- Indices `i`, `j`, `k` are in bounds for `nums` and pairwise distinct, and `s` is the sum of the three entries at those indices. -/ def IsSumOfDistinctTriple (nums : List Int) (i j k : Nat) (s : Int) : Prop := i < nums.length ∧ j < nums.length ∧ k < nums.length ∧ i ≠ j ∧ j ≠ k ∧ i ≠ k ∧ ∃ a b c : Int, nums[i]? = some a ∧ nums[j]? = some b ∧ nums[k]? = some c ∧ s = a + b + c /-! ### Validity predicate (V) -/ /-- Valid input: 3 to 500 entries each in [-1000, 1000], target in [-10000, 10000], and all triple sums closest to the target agree. -/ def isValidInput (input : Input) : Bool := let nums := input.1 let target := input.2 let n := nums.length let sums := (List.range n).flatMap fun i => (List.range n).flatMap fun j => (List.range n).flatMap fun k => if i ≠ j ∧ j ≠ k ∧ i ≠ k then [nums[i]! + nums[j]! + nums[k]!] else [] let uniqueClosest := match sums.map fun s => (s - target).natAbs with | [] => false | d :: ds => let dmin := ds.foldl Nat.min d match sums.filter (fun s => (s - target).natAbs = dmin) with | [] => false | w :: ws => ws.all fun s => s == w 3 ≤ n && n ≤ 500 && nums.all (fun x => -1000 ≤ x && x ≤ 1000) && -10000 ≤ target && target ≤ 10000 && uniqueClosest /-! ### Ideal specification (P_spec) -/ /-- `result` is the sum of three entries at pairwise distinct indices, and no such sum has a smaller absolute distance to the target. -/ def threeSumClosest_spec (input : Input) (result : Output) : Prop := (∃ i j k : Nat, IsSumOfDistinctTriple input.1 i j k result) ∧ IsLeast {d : Int | ∃ i j k : Nat, ∃ s : Int, IsSumOfDistinctTriple input.1 i j k s ∧ d = |s - input.2|} |result - input.2| /-! ### Decidable specification (P_check) -/ /-- The sums of all triples of entries at pairwise distinct indices of `nums`. -/ def tripleSums (nums : List Int) : List Int := (List.range nums.length).flatMap fun i => (List.range nums.length).flatMap fun j => (List.range nums.length).flatMap fun k => if i ≠ j ∧ j ≠ k ∧ i ≠ k then [nums[i]! + nums[j]! + nums[k]!] else [] /-- Executable checker for `threeSumClosest_spec`: `result` is a distinct-triple sum and no such sum is closer to the target. -/ def threeSumClosest_check (input : Input) (result : Output) : Bool := let sums := tripleSums input.1 sums.any (· == result) && sums.all fun s => (result - input.2).natAbs ≤ (s - input.2).natAbs theorem closest_root (input : Input) (result : Output) (bridge : ∀ (nums : List Int) (s : Int), s ∈ tripleSums nums ↔ ∃ i j k : Nat, IsSumOfDistinctTriple nums i j k s) : threeSumClosest_check input result ↔ threeSumClosest_spec input result := by have dist (a b : Int) : a.natAbs ≤ b.natAbs ↔ |a| ≤ |b| := by simp only [← Int.natCast_natAbs, Int.ofNat_le] simp only [threeSumClosest_check, Bool.and_eq_true, List.any_eq_true, List.all_eq_true, beq_iff_eq, decide_eq_true_eq] simp only [exists_eq_right, dist] constructor · rintro ⟨hr, hall⟩ obtain ⟨i, j, k, hs⟩ := (bridge input.1 result).mp hr refine ⟨⟨i, j, k, hs⟩, ⟨⟨i, j, k, result, hs, rfl⟩, ?_⟩⟩ rintro d ⟨i', j', k', s, hs', rfl⟩ exact hall s ((bridge input.1 s).mpr ⟨i', j', k', hs'⟩) · rintro ⟨hr, hleast⟩ refine ⟨(bridge input.1 result).mpr hr, ?_⟩ intro s hs obtain ⟨i, j, k, ht⟩ := (bridge input.1 s).mp hs exact hleast.2 ⟨i, j, k, s, ht, rfl⟩ theorem triple_mem (nums : List Int) (s : Int) : s ∈ tripleSums nums ↔ ∃ i j k : Nat, IsSumOfDistinctTriple nums i j k s := by simp only [tripleSums, List.mem_flatMap, List.mem_range] constructor · rintro ⟨i, hi, j, hj, k, hk, hm⟩ split at hm · rename_i hd simp only [List.mem_singleton] at hm refine ⟨i, j, k, hi, hj, hk, hd.1, hd.2.1, hd.2.2, nums[i], nums[j], nums[k], ?_, ?_, ?_, ?_⟩ · simp [hi] · simp [hj] · simp [hk] · simpa [List.getElem!_eq_getElem?_getD, hi, hj, hk] using hm · simp at hm · rintro ⟨i, j, k, hi, hj, hk, hij, hjk, hik, a, b, c, ha, hb, hc, heq⟩ refine ⟨i, hi, j, hj, k, hk, ?_⟩ rw [if_pos ⟨hij, hjk, hik⟩] simpa [List.getElem!_eq_getElem?_getD, ha, hb, hc] using heq /-- On valid input the checker accepts exactly the specified outputs. -/ theorem threeSumClosest_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : threeSumClosest_check input result ↔ threeSumClosest_spec input result := by exact closest_root input result triple_mem /-! ### Implementation helpers -/ /-- Inserts `x` into an ascending list, keeping it ascending. -/ def insertSorted (x : Int) : List Int → List Int | [] => [x] | y :: ys => if x ≤ y then x :: y :: ys else y :: insertSorted x ys /-- Sorts a list of integers into ascending order by insertion sorting. -/ def sortAscending (nums : List Int) : List Int := nums.foldl (fun acc x => insertSorted x acc) [] /-- The absolute distance between `s` and `target` as a natural number. -/ def distToTarget (target s : Int) : Nat := (s - target).natAbs /-- Returns whichever of `best` and `s` lies closer to `target`, keeping `best` on a tie. -/ def updateClosest (target best s : Int) : Int := if distToTarget target s < distToTarget target best then s else best /-- Two-pointer scan of the sorted suffix for fixed first index `i`, returning the triple sum closest to `target` seen so far. -/ def twoPointerSearch (arr : Array Int) (target : Int) (i lo hi : Nat) (best : Int) : Int := if h : lo < hi ∧ hi < arr.size ∧ i < arr.size then let s := arr[i]! + arr[lo]! + arr[hi]! let best := updateClosest target best s if s = target then s else if s < target then twoPointerSearch arr target i (lo + 1) hi best else twoPointerSearch arr target i lo (hi - 1) best else best termination_by hi - lo decreasing_by all_goals simp_wf all_goals omega /-- Iterates over the candidate first indices, carrying the best sum seen so far. -/ def searchFirstIndices (arr : Array Int) (target : Int) (best : Int) : List Nat → Int | [] => best | i :: is => searchFirstIndices arr target (twoPointerSearch arr target i (i + 1) (arr.size - 1) best) is /-! ### Main algorithm (impl) -/ /-- Closest triple sum by sorting, then a two-pointer scan of the suffix for each first index, in O(n^2). -/ def findClosestThreeSum (input : Input) : Output := let arr := (sortAscending input.1).toArray let target := input.2 if 3 ≤ arr.size then let best := arr[0]! + arr[1]! + arr[2]! searchFirstIndices arr target best (List.range (arr.size - 2)) else 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findClosestThreeSum_correct (input : Input) (h : isValidInput input) : threeSumClosest_spec input (findClosestThreeSum input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([(-1), 2, 1, (-4)], 1) #guard isValidInput ([0, 0, 0], 1) #guard isValidInput ([1, 1, 1, 1], 3) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([0, 0], 0)) #guard !(isValidInput ([1001, 0, 0], 0)) #guard !(isValidInput ([10000, 0, 0], 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard threeSumClosest_check ([(-1), 2, 1, (-4)], 1) 2 #guard threeSumClosest_check ([0, 0, 0], 1) 0 #guard threeSumClosest_check ([1, 1, 1, 1], 3) 3 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(threeSumClosest_check ([(-1), 2, 1, (-4)], 1) 1) #guard !(threeSumClosest_check ([0, 0, 0], 1) 1) #guard !(threeSumClosest_check ([1, 1, 1, 1], 3) 2) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findClosestThreeSum ([(-1), 2, 1, (-4)], 1) == 2 #guard findClosestThreeSum ([0, 0, 0], 1) == 0 #guard findClosestThreeSum ([1, 1, 1, 1], 3) == 3 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard threeSumClosest_check ([(-1), 2, 1, (-4)], 1) (findClosestThreeSum ([(-1), 2, 1, (-4)], 1)) #guard threeSumClosest_check ([0, 0, 0], 1) (findClosestThreeSum ([0, 0, 0], 1)) #guard threeSumClosest_check ([1, 1, 1, 1], 3) (findClosestThreeSum ([1, 1, 1, 1], 3)) end P3sumClosest