import Mathlib /-! # Merge Two Sorted Lists You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list. ## Constraints - The number of nodes in both lists is in the range [0, 50]. - -100 <= Node.val <= 100 - Both list1 and list2 are sorted in non-decreasing order. ## Provided examples - `list1 = [1, 2, 4], list2 = [1, 3, 4]` → `[1, 1, 2, 3, 4, 4]` - `list1 = [], list2 = []` → `[]` - `list1 = [], list2 = [0]` → `[0]` ## Synthesized negative examples - invalid input: `list1 = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], list2 = []` ([structural] a predicate that admits The number of nodes in both lists is in the range [0, 50].. 51 nodes in one list exceeds ceiling) - invalid input: `list1 = [101], list2 = []` ([structural] a predicate that admits -100 <= Node.val <= 100. one above the stated maximum) - invalid input: `list1 = [2, 1], list2 = []` ([structural] a predicate that admits Both list1 and list2 are sorted in non-decreasing order.. list1 decreases from 2 to 1) - `list1 = [1, 2, 4], list2 = [1, 3, 4]` → `[1, 1, 2, 3, 4]` is wrong ([structural] the output is allowed to be one node short, so the last 4 may be dropped. sorted and drawn from inputs, but lacks one copy of 4) - `list1 = [], list2 = []` → `[0]` is wrong ([structural] omits that no new nodes may be added. empty input, so extra node still satisfies sortedness and completeness) - `list1 = [], list2 = [0]` → `[0, 0]` is wrong ([structural] no requirement that the output length equal the combined input length. one extra node, still sorted and contains 0) -/ namespace PMergeTwoSortedLists abbrev Input := (List Int) × (List Int) abbrev Output := List Int /-! ### Validity predicate (V) -/ /-- Computational adjacency check: every element is ≤ the next one. -/ def isSortedLE : List Int → Bool | [] => true | [_] => true | x :: y :: xs => decide (x ≤ y) && isSortedLE (y :: xs) /-- Valid input: both lists have at most 50 elements in [-100, 100] and are sorted in non-decreasing order. -/ def isValidInput (input : Input) : Bool := input.1.length ≤ 50 && input.2.length ≤ 50 && input.1.all (fun x => -100 ≤ x && x ≤ 100) && input.2.all (fun x => -100 ≤ x && x ≤ 100) && isSortedLE input.1 && isSortedLE input.2 /-! ### Ideal specification (P_spec) -/ /-- `result` is the merge of the two input lists: a permutation of their concatenation, and the sorted one. -/ def mergeTwoLists_spec (input : Input) (result : Output) : Prop := result.Perm (input.1 ++ input.2) ∧ List.SortedLE result /-! ### Decidable specification (P_check) -/ /-- Executable checker for `mergeTwoLists_spec`: the permutation clause decided by `DecidableEq Int`, the sortedness clause by the spec's own `isSortedLE`. -/ def mergeTwoLists_check (input : Input) (result : Output) : Bool := decide (result.Perm (input.1 ++ input.2)) && isSortedLE result theorem isSortedLE_iff_sortedLE (xs : List Int) : isSortedLE xs = true ↔ xs.SortedLE := by rw [List.sortedLE_iff_isChain] induction xs with | nil => simp [isSortedLE] | cons a t ih => cases t with | nil => simp [isSortedLE] | cons b u => simp only [isSortedLE, Bool.and_eq_true, decide_eq_true_eq, List.isChain_cons_cons] exact and_congr_right fun _ => ih /-- On valid input the checker accepts exactly the specified outputs. -/ theorem mergeTwoLists_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : mergeTwoLists_check input result ↔ mergeTwoLists_spec input result := by simp only [mergeTwoLists_check, mergeTwoLists_spec, Bool.and_eq_true, decide_eq_true_eq, isSortedLE_iff_sortedLE] /-! ### Main algorithm (impl) -/ /-- Standard two-finger merge of two sorted lists into one sorted list. -/ def mergeSortedLists : Input → Output | ([], ys) => ys | (xs, []) => xs | (x :: xs, y :: ys) => if x ≤ y then x :: mergeSortedLists (xs, y :: ys) else y :: mergeSortedLists (x :: xs, ys) termination_by input => input.1.length + input.2.length decreasing_by all_goals (simp_wf <;> omega) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem mergeSortedLists_correct (input : Input) (h : isValidInput input) : mergeTwoLists_spec input (mergeSortedLists input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([1, 2, 4], [1, 3, 4]) #guard isValidInput ([], []) #guard isValidInput ([], [0]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #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], [])) #guard !(isValidInput ([101], [])) #guard !(isValidInput ([2, 1], [])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard mergeTwoLists_check ([1, 2, 4], [1, 3, 4]) [1, 1, 2, 3, 4, 4] #guard mergeTwoLists_check ([], []) [] #guard mergeTwoLists_check ([], [0]) [0] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(mergeTwoLists_check ([1, 2, 4], [1, 3, 4]) [1, 1, 2, 3, 4]) #guard !(mergeTwoLists_check ([], []) [0]) #guard !(mergeTwoLists_check ([], [0]) [0, 0]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard mergeSortedLists ([1, 2, 4], [1, 3, 4]) == [1, 1, 2, 3, 4, 4] #guard mergeSortedLists ([], []) == [] #guard mergeSortedLists ([], [0]) == [0] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard mergeTwoLists_check ([1, 2, 4], [1, 3, 4]) (mergeSortedLists ([1, 2, 4], [1, 3, 4])) #guard mergeTwoLists_check ([], []) (mergeSortedLists ([], [])) #guard mergeTwoLists_check ([], [0]) (mergeSortedLists ([], [0])) end PMergeTwoSortedLists