import Mathlib /-! # Two Sum Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. ## Constraints - 2 <= nums.length <= 10^4 - -10^9 <= nums[i] <= 10^9 - -10^9 <= target <= 10^9 - Only one valid answer exists. ## Provided examples - `nums = [2, 7, 11, 15], target = 9` → `[0, 1]` - `nums = [3, 2, 4], target = 6` → `[1, 2]` - `nums = [3, 3], target = 6` → `[0, 1]` ## Synthesized negative examples - invalid input: `nums = [1], target = 1` ([structural] a predicate that admits 2 <= nums.length <= 10^4. one element where at least two are required) - invalid input: `nums = [1000000001, -1], target = 1000000000` ([structural] a predicate that admits -10^9 <= nums[i] <= 10^9. one past the stated maximum element value) - invalid input: `nums = [1, 1, 2, 2], target = 3` ([structural] a predicate that admits Only one valid answer exists.. range-only predicate accepts four answers) - `nums = [2, 7, 11, 15], target = 9` → `[1, 2]` is wrong ([structural] indices are one-based rather than zero-based. under 0-based indexing 7+11=18) - `nums = [3, 2, 4], target = 6` → `[0, 0]` is wrong ([structural] indices need not be distinct. uses the same element twice but still sums to 6) - `nums = [3, 3], target = 6` → `[1, 2]` is wrong ([structural] indices are one higher, allowed as 1-based positions. 1 and 2 are 1-based positions of the two 3s) -/ namespace PTwoSum abbrev Input := (List Int) × (Int) abbrev Output := List Nat /-! ### Validity predicate (V) -/ /-- Valid input: length in [2, 10^4], entries and target within ±10^9, and exactly one pair of distinct indices summing to the target. -/ def isValidInput (input : Input) : Bool := let nums := input.1 let target := input.2 let n := nums.length 2 ≤ n && n ≤ 10 ^ 4 && nums.all (fun x => -10 ^ 9 ≤ x && x ≤ 10 ^ 9) && -10 ^ 9 ≤ target && target ≤ 10 ^ 9 && ((List.range n).flatMap fun i => (List.range n).filter fun j => i < j && nums[i]! + nums[j]! == target).length == 1 /-! ### Ideal specification (P_spec) -/ /-- `result` is a pair of distinct in-bounds indices whose entries sum to the target. -/ def twoSum_spec (input : Input) (result : Output) : Prop := ∃ i j : Nat, result = [i, j] ∧ ∃ (hi : i < input.1.length) (hj : j < input.1.length), i ≠ j ∧ input.1[i]'hi + input.1[j]'hj = input.2 /-! ### Decidable specification (P_check) -/ /-- Decides the specification's existential. On any candidate pair the indices are bounded by `input.1.length`, so the statement is equivalent to an existential over `Fin input.1.length`; there `input.1[i]` is definitionally the specification's `getElem`, and the bounded quantifier is decided by `Fintype.decidableExistsFintype` together with the decidable equalities on `List Nat` and `Int`. -/ instance decTwoSum (input : Input) (result : Output) : Decidable (∃ i j : Nat, result = [i, j] ∧ ∃ (hi : i < input.1.length) (hj : j < input.1.length), i ≠ j ∧ input.1[i]'hi + input.1[j]'hj = input.2) := decidable_of_iff (∃ i : Fin input.1.length, ∃ j : Fin input.1.length, result = [i.val, j.val] ∧ i.val ≠ j.val ∧ input.1[i] + input.1[j] = input.2) (by constructor · rintro ⟨i, j, heq, hne, hsum⟩ exact ⟨i.val, j.val, heq, i.isLt, j.isLt, hne, hsum⟩ · rintro ⟨i, j, heq, hi, hj, hne, hsum⟩ exact ⟨⟨i, hi⟩, ⟨j, hj⟩, heq, hne, hsum⟩) /-- Executable checker obtained mechanically from the specification. -/ def twoSum_check (input : Input) (result : Output) : Bool := @decide (twoSum_spec input result) (by unfold twoSum_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem twoSum_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : twoSum_check input result ↔ twoSum_spec input result := by simp [twoSum_check] /-! ### Implementation helpers -/ /-- Tail-recursive scan returning the first seen-complement pair of indices that sums to `target`. -/ def twoSumLoop (target : Int) (seen : Std.HashMap Int Nat) (i : Nat) (nums : List Int) : Output := match nums with | [] => [] | x :: xs => match seen.get? (target - x) with | some j => [j, i] | none => twoSumLoop target (seen.insert x i) (i + 1) xs /-! ### Main algorithm (impl) -/ /-- Single-pass hash-map scan from seen values to indices for the two-sum pair. -/ def findTwoSum (input : Input) : Output := twoSumLoop input.2 ({} : Std.HashMap Int Nat) 0 input.1 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findTwoSum_correct (input : Input) (h : isValidInput input) : twoSum_spec input (findTwoSum input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([2, 7, 11, 15], 9) #guard isValidInput ([3, 2, 4], 6) #guard isValidInput ([3, 3], 6) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([1], 1)) #guard !(isValidInput ([1000000001, (-1)], 1000000000)) #guard !(isValidInput ([1, 1, 2, 2], 3)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard twoSum_check ([2, 7, 11, 15], 9) [0, 1] #guard twoSum_check ([3, 2, 4], 6) [1, 2] #guard twoSum_check ([3, 3], 6) [0, 1] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(twoSum_check ([2, 7, 11, 15], 9) [1, 2]) #guard !(twoSum_check ([3, 2, 4], 6) [0, 0]) #guard !(twoSum_check ([3, 3], 6) [1, 2]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findTwoSum ([2, 7, 11, 15], 9) == [0, 1] #guard findTwoSum ([3, 2, 4], 6) == [1, 2] #guard findTwoSum ([3, 3], 6) == [0, 1] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard twoSum_check ([2, 7, 11, 15], 9) (findTwoSum ([2, 7, 11, 15], 9)) #guard twoSum_check ([3, 2, 4], 6) (findTwoSum ([3, 2, 4], 6)) #guard twoSum_check ([3, 3], 6) (findTwoSum ([3, 3], 6)) end PTwoSum