import Mathlib /-! # Merge K Sorted Lists You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. ## Constraints - k == lists.length - 0 <= k <= 10^4 - 0 <= lists[i].length <= 500 - -10^4 <= lists[i][j] <= 10^4 - lists[i] is sorted in ascending order. - The sum of lists[i].length will not exceed 10^4. ## Provided examples - `lists = [[1, 4, 5], [1, 3, 4], [2, 6]]` → `[1, 1, 2, 3, 4, 4, 5, 6]` - `lists = []` → `[]` - `lists = [[]]` → `[]` ## Synthesized negative examples - invalid input: `lists = [[10001]]` ([structural] a predicate that admits -10^4 <= lists[i][j] <= 10^4. one past the maximum value) - invalid input: `lists = [[1, 3, 2]]` ([structural] a predicate that admits lists[i] is sorted in ascending order.. would pass a predicate checking only endpoints) - invalid input: `lists = [[-10001]]` ([structural] a predicate that admits -10^4 <= lists[i][j] <= 10^4. one below the minimum value) - `lists = [[1, 4, 5], [1, 3, 4], [2, 6]]` → `[1, 1, 2, 3, 4, 4, 5, 6, 6]` is wrong ([structural] unattainable does not apply; spec omits that the output must not contain extra elements, accepting one duplicate. sorted and contains all original elements, but has an extra 6) - `lists = []` → `[1]` is wrong ([structural] base case creates one node when k is zero. one node from zero inputs; count is one too high) - `lists = [[]]` → `[0]` is wrong ([structural] merge stated as preserving input values rather than excluding new ones. Extra node [0]; sorted and all zero input nodes present.) -/ namespace PMergeKSortedLists abbrev Input := List (List Int) abbrev Output := List Int /-! ### Validity predicate (V) -/ /-- Valid input: at most 10^4 lists, each sorted with length at most 500, all values in [-10^4, 10^4], and total length at most 10^4. -/ def isValidInput (input : Input) : Bool := input.length ≤ 10^4 && input.all (fun l => l.length ≤ 500 && l.all (fun x => -10^4 ≤ x && x ≤ 10^4) && (l.zipWith (fun a b => decide (a ≤ b)) l.tail).all id) && (input.map List.length).sum ≤ 10^4 /-! ### Ideal specification (P_spec) -/ /-- `result` holds exactly the elements of all input lists concatenated, in nondecreasing order. -/ def mergeKLists_spec (input : Input) (result : Output) : Prop := result.Perm input.flatten ∧ result.SortedLE /-! ### Decidable specification (P_check) -/ /-- Decides `Monotone l.get` for an `Int` list: it unfolds to a bounded quantification over the finite type `Fin l.length`, which `Fintype.decidableForallFintype` decides with `Int.decLe` at the leaves. -/ instance decMonotoneGetInt (l : List Int) : Decidable (Monotone l.get) := inferInstanceAs (Decidable (∀ a b : Fin l.length, a ≤ b → l.get a ≤ l.get b)) /-- Decides the `result.SortedLE` conjunct of `mergeKLists_spec`: in this environment `List.SortedLE` simplifies to `Monotone l.get`, decided above. -/ instance decSortedLEInt (l : List Int) : Decidable l.SortedLE := decidable_of_iff (Monotone l.get) (by simp [List.SortedLE]) /-- Executable checker obtained mechanically from the specification. -/ def mergeKLists_check (input : Input) (result : Output) : Bool := @decide (mergeKLists_spec input result) (by unfold mergeKLists_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem mergeKLists_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : mergeKLists_check input result ↔ mergeKLists_spec input result := by simp [mergeKLists_check] /-! ### Implementation helpers -/ /-- Merge two sorted integer lists into one sorted list in linear time. -/ def mergeTwoSorted : List Int → List Int → List Int | [], ys => ys | xs, [] => xs | x :: xs, y :: ys => if x ≤ y then x :: mergeTwoSorted xs (y :: ys) else y :: mergeTwoSorted (x :: xs) ys termination_by xs ys => xs.length + ys.length decreasing_by · simp_wf · simp_wf /-- Merge a list of sorted lists by recursively halving it and merging the halves. -/ def mergeKSortedListsAux (lists : List (List Int)) : List Int := if h : lists.length ≤ 1 then match lists with | [] => [] | l :: _ => l else mergeTwoSorted (mergeKSortedListsAux (lists.take (lists.length / 2))) (mergeKSortedListsAux (lists.drop (lists.length / 2))) termination_by lists.length decreasing_by · have h2 : 2 ≤ lists.length := by omega simp_wf omega · have h2 : 2 ≤ lists.length := by omega simp_wf omega /-! ### Main algorithm (impl) -/ /-- Merge k sorted lists by a balanced divide-and-conquer merge tree. -/ def mergeKSortedLists (input : Input) : Output := mergeKSortedListsAux input /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem mergeKSortedLists_correct (input : Input) (h : isValidInput input) : mergeKLists_spec input (mergeKSortedLists input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [[1, 4, 5], [1, 3, 4], [2, 6]] #guard isValidInput [] #guard isValidInput [[]] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput [[10001]]) #guard !(isValidInput [[1, 3, 2]]) #guard !(isValidInput [[(-10001)]]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard mergeKLists_check [[1, 4, 5], [1, 3, 4], [2, 6]] [1, 1, 2, 3, 4, 4, 5, 6] #guard mergeKLists_check [] [] #guard mergeKLists_check [[]] [] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(mergeKLists_check [[1, 4, 5], [1, 3, 4], [2, 6]] [1, 1, 2, 3, 4, 4, 5, 6, 6]) #guard !(mergeKLists_check [] [1]) #guard !(mergeKLists_check [[]] [0]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard mergeKSortedLists [[1, 4, 5], [1, 3, 4], [2, 6]] == [1, 1, 2, 3, 4, 4, 5, 6] #guard mergeKSortedLists [] == [] #guard mergeKSortedLists [[]] == [] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard mergeKLists_check [[1, 4, 5], [1, 3, 4], [2, 6]] (mergeKSortedLists [[1, 4, 5], [1, 3, 4], [2, 6]]) #guard mergeKLists_check [] (mergeKSortedLists []) #guard mergeKLists_check [[]] (mergeKSortedLists [[]]) end PMergeKSortedLists