import Mathlib /-! # Merge Sorted Array You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively. Merge nums1 and nums2 into a single array sorted in non-decreasing order. The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n. ## Constraints - nums1.length == m + n - nums2.length == n - 0 <= m, n <= 200 - 1 <= m + n <= 200 - -10^9 <= nums1[i], nums2[j] <= 10^9 ## Provided examples - `nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3` → `[1, 2, 2, 3, 5, 6]` - `nums1 = [1], m = 1, nums2 = [], n = 0` → `[1]` - `nums1 = [0], m = 0, nums2 = [1], n = 1` → `[1]` ## Synthesized negative examples - invalid input: `nums1 = [1, 2], m = 1, nums2 = [], n = 0` ([structural] a predicate that admits nums1.length == m + n. extra element in nums1; length relation broken) - invalid input: `nums1 = [], m = 0, nums2 = [], n = 0` ([structural] a predicate that admits 1 <= m + n <= 200. zero total elements below minimum) - invalid input: `nums1 = [1000000001], m = 1, nums2 = [], n = 0` ([structural] a predicate that admits -10^9 <= nums1[i], nums2[j] <= 10^9. nums1 value one above upper bound) - `nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3` → `[1, 2, 3, 2, 5, 6]` is wrong ([structural] sortedness is not required of the final array. same multiset and length; only order is wrong.) - `nums1 = [1], m = 1, nums2 = [], n = 0` → `[]` is wrong ([structural] no requirement that every input element appear in the result. empty list is sorted and uses no outside elements, but omits 1) - `nums1 = [0], m = 0, nums2 = [1], n = 1` → `[0]` is wrong ([structural] input echoed back; no requirement to include nums2. returns the padding zero unchanged) -/ namespace PMergeSortedArray abbrev Input := (List Int) × (Nat) × (List Int) × (Nat) abbrev Output := List Int /-! ### Validity predicate (V) -/ /-- Adjacent-pair check: every element is at most the next one. -/ def sortedNondecreasing : List Int → Bool | [] => true | [_] => true | x :: y :: xs => decide (x ≤ y) && sortedNondecreasing (y :: xs) /-- Valid input: lengths match `m + n` and `n`, bounds hold, prefixes are sorted, and the tail of `nums1` is zeros. -/ def isValidInput (input : Input) : Bool := let (nums1, m, nums2, n) := input nums1.length == m + n && nums2.length == n && decide (m ≤ 200) && decide (n ≤ 200) && decide (1 ≤ m + n) && decide (m + n ≤ 200) && sortedNondecreasing (List.take m nums1) && sortedNondecreasing nums2 && (nums1.drop m).all (· == 0) && nums1.all (fun x => decide (-1000000000 ≤ x ∧ x ≤ 1000000000)) && nums2.all (fun x => decide (-1000000000 ≤ x ∧ x ≤ 1000000000)) /-! ### Ideal specification (P_spec) -/ /-- `result` is the sorted merge: a permutation of the first `m` entries of `nums1` together with `nums2`, in non-decreasing order. -/ def mergeSortedArrays_spec (input : Input) (result : Output) : Prop := let (nums1, m, nums2, _) := input result.Perm (List.take m nums1 ++ nums2) ∧ result.SortedLE /-! ### Decidable specification (P_check) -/ /-- Decides the `result.SortedLE` half of the specification. `List.SortedLE l` unfolds to `Monotone l.get`, i.e. `∀ a b : Fin l.length, a ≤ b → l.get a ≤ l.get b`. That is a bounded quantification over the finite type `Fin l.length`, so Lean's own `Fintype.decidableForallFintype` (with the decidable `≤` on `Fin` and `Int`) decides it once the goal is restated in the unfolded form; the equivalence is definitional. -/ instance decSortedLE (l : List Int) : Decidable (List.SortedLE l) := decidable_of_iff (∀ a b : Fin l.length, a ≤ b → l.get a ≤ l.get b) (by first | exact Iff.rfl | (simp only [List.SortedLE, Monotone]; exact Iff.rfl)) /-- Executable checker obtained mechanically from the specification. -/ def mergeSortedArrays_check (input : Input) (result : Output) : Bool := @decide (mergeSortedArrays_spec input result) (by unfold mergeSortedArrays_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem mergeSortedArrays_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : mergeSortedArrays_check input result ↔ mergeSortedArrays_spec input result := by simp [mergeSortedArrays_check] /-! ### Implementation helpers -/ /-- Merges two sorted lists by repeatedly emitting the smaller head and recursing on the rest. -/ def mergeTwoLists : List Int → List Int → List Int | [], ys => ys | xs, [] => xs | x :: xs, y :: ys => if x ≤ y then x :: mergeTwoLists xs (y :: ys) else y :: mergeTwoLists (x :: xs) ys termination_by xs ys => xs.length + ys.length decreasing_by all_goals simp_wf all_goals omega /-! ### Main algorithm (impl) -/ /-- Two-pointer merge of the first `m` entries of `nums1` with `nums2`, in O(m + n). -/ def mergeTwoSortedArrays (input : Input) : Output := let (nums1, m, nums2, _) := input mergeTwoLists (List.take m nums1) nums2 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem mergeTwoSortedArrays_correct (input : Input) (h : isValidInput input) : mergeSortedArrays_spec input (mergeTwoSortedArrays input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3) #guard isValidInput ([1], 1, [], 0) #guard isValidInput ([0], 0, [1], 1) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([1, 2], 1, [], 0)) #guard !(isValidInput ([], 0, [], 0)) #guard !(isValidInput ([1000000001], 1, [], 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard mergeSortedArrays_check ([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3) [1, 2, 2, 3, 5, 6] #guard mergeSortedArrays_check ([1], 1, [], 0) [1] #guard mergeSortedArrays_check ([0], 0, [1], 1) [1] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(mergeSortedArrays_check ([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3) [1, 2, 3, 2, 5, 6]) #guard !(mergeSortedArrays_check ([1], 1, [], 0) []) #guard !(mergeSortedArrays_check ([0], 0, [1], 1) [0]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard mergeTwoSortedArrays ([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3) == [1, 2, 2, 3, 5, 6] #guard mergeTwoSortedArrays ([1], 1, [], 0) == [1] #guard mergeTwoSortedArrays ([0], 0, [1], 1) == [1] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard mergeSortedArrays_check ([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3) (mergeTwoSortedArrays ([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3)) #guard mergeSortedArrays_check ([1], 1, [], 0) (mergeTwoSortedArrays ([1], 1, [], 0)) #guard mergeSortedArrays_check ([0], 0, [1], 1) (mergeTwoSortedArrays ([0], 0, [1], 1)) end PMergeSortedArray