import Mathlib /-! # Remove Duplicates From Sorted List Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well. ## Constraints - The number of nodes in the list is in the range [0, 300]. - -100 <= Node.val <= 100 - The list is guaranteed to be sorted in ascending order. ## Provided examples - `head = [1, 1, 2]` → `[1, 2]` - `head = [1, 1, 2, 3, 3]` → `[1, 2, 3]` - `head = [1]` → `[1]` ## Synthesized negative examples - invalid input: `head = [100, 101]` ([structural] a predicate that admits -100 <= Node.val <= 100. one above the stated maximum) - invalid input: `head = [1, 0]` ([structural] a predicate that admits The list is guaranteed to be sorted in ascending order.. first pair descending) - invalid input: `head = [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, 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, 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, 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, 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, 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, 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]` ([structural] a predicate that admits The number of nodes in the list is in the range [0, 300].. one past the maximum node count) - `head = [1, 1, 2]` → `[1, 1, 2]` is wrong ([structural] duplicate-free clause is dropped. sorted and complete but contains a repeat) - `head = [1, 1, 2, 3, 3]` → `[]` is wrong ([structural] nothing requires every distinct input value to appear. empty list is valid if completeness is omitted) - `head = [1]` → `[]` is wrong ([structural] no requirement that every distinct input value be retained. empty list is sorted and duplicate-free but drops the only node) -/ namespace PRemoveDuplicatesFromSortedList abbrev Input := List Int abbrev Output := List Int /-! ### Validity predicate (V) -/ /-- Valid input: at most 300 node values, each between -100 and 100, in nondecreasing order. -/ def isValidInput (input : Input) : Bool := decide (input.length ≤ 300) && input.all (fun x => decide (-100 ≤ x ∧ x ≤ 100)) && (input.zip input.tail).all (fun p => decide (p.1 ≤ p.2)) /-! ### Ideal specification (P_spec) -/ /-- `result` is sorted in nondecreasing order, has no duplicates, and contains exactly the values that occur in `input`. -/ def deleteDuplicates_spec (input : Input) (result : Output) : Prop := result.SortedLE ∧ result.Nodup ∧ ∀ v : Int, v ∈ result ↔ v ∈ input /-! ### Decidable specification (P_check) -/ /-- Executable checker for `deleteDuplicates_spec`: adjacent-pairs sortedness, no duplicates, and the membership biconditional restricted to the values occurring in `result` or `input`. -/ def deleteDuplicates_check (input : Input) (result : Output) : Bool := (result.zip result.tail).all (fun p => decide (p.1 ≤ p.2)) && decide result.Nodup && (result ++ input).all (fun v => decide (v ∈ result ↔ v ∈ input)) theorem sortedLEBool_iff_isChain (xs : List Int) : (xs.zip xs.tail).all (fun p => decide (p.1 ≤ p.2)) = true ↔ List.IsChain (· ≤ ·) xs := by induction xs with | nil => simp | cons a t ih => cases t with | nil => simp | cons b u => simp only [List.tail_cons, List.zip_cons_cons, List.all_cons, Bool.and_eq_true, decide_eq_true_eq, List.isChain_cons_cons] at ih ⊢ exact and_congr_right fun _ => ih theorem sortedLEBool_iff_sortedLE (xs : List Int) : (xs.zip xs.tail).all (fun p => decide (p.1 ≤ p.2)) = true ↔ xs.SortedLE := (sortedLEBool_iff_isChain xs).trans List.sortedLE_iff_isChain.symm theorem mem_bound_iff (result input : List Int) : (result ++ input).all (fun v => decide (v ∈ result ↔ v ∈ input)) = true ↔ ∀ v : Int, v ∈ result ↔ v ∈ input := by constructor · intro hall v by_cases hv : v ∈ result ++ input · exact decide_eq_true_eq.mp (List.all_eq_true.mp hall v hv) · simp only [List.mem_append, not_or] at hv simp [hv.1, hv.2] · intro hv apply List.all_eq_true.mpr intro v _ exact decide_eq_true_eq.mpr (hv v) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem deleteDuplicates_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : deleteDuplicates_check input result ↔ deleteDuplicates_spec input result := by unfold deleteDuplicates_check deleteDuplicates_spec simp only [Bool.and_eq_true, decide_eq_true_eq] rw [sortedLEBool_iff_sortedLE, mem_bound_iff] exact and_assoc /-! ### Main algorithm (impl) -/ /-- Removes duplicate node values from the sorted input using `List.dedup`. -/ def removeDuplicatesFromSortedList (input : Input) : Output := input.dedup /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem removeDuplicatesFromSortedList_correct (input : Input) (h : isValidInput input) : deleteDuplicates_spec input (removeDuplicatesFromSortedList input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [1, 1, 2] #guard isValidInput [1, 1, 2, 3, 3] #guard isValidInput [1] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput [100, 101]) #guard !(isValidInput [1, 0]) #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, 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, 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, 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, 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, 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, 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]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard deleteDuplicates_check [1, 1, 2] [1, 2] #guard deleteDuplicates_check [1, 1, 2, 3, 3] [1, 2, 3] #guard deleteDuplicates_check [1] [1] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(deleteDuplicates_check [1, 1, 2] [1, 1, 2]) #guard !(deleteDuplicates_check [1, 1, 2, 3, 3] []) #guard !(deleteDuplicates_check [1] []) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard removeDuplicatesFromSortedList [1, 1, 2] == [1, 2] #guard removeDuplicatesFromSortedList [1, 1, 2, 3, 3] == [1, 2, 3] #guard removeDuplicatesFromSortedList [1] == [1] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard deleteDuplicates_check [1, 1, 2] (removeDuplicatesFromSortedList [1, 1, 2]) #guard deleteDuplicates_check [1, 1, 2, 3, 3] (removeDuplicatesFromSortedList [1, 1, 2, 3, 3]) #guard deleteDuplicates_check [1] (removeDuplicatesFromSortedList [1]) end PRemoveDuplicatesFromSortedList