import Mathlib /-! # Remove Duplicates From Sorted List Ii Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. 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, 1, 2, 3]` → `[2, 3]` - `head = [1]` → `[1]` - `head = [-100, 100]` → `[-100, 100]` ## Synthesized negative examples - 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]` ([structural] a predicate that admits The number of nodes in the list is in the range [0, 300].. 301 nodes, one past the stated maximum.) - invalid input: `head = [101]` ([structural] a predicate that admits -100 <= Node.val <= 100. one above the stated value maximum.) - invalid input: `head = [100, -100]` ([structural] a predicate that admits The list is guaranteed to be sorted in ascending order.. descending pair; a predicate ignoring order accepts it.) - `head = [1, 1, 1, 2, 3]` → `[]` is wrong ([structural] nothing requires the output to contain every distinct number. empty list passes a completeness-free spec) - `head = [1]` → `[]` is wrong ([structural] nothing requires every distinct element to appear. empty list misses the only non-duplicate) - `head = [-100, 100]` → `[100, -100]` is wrong ([structural] sortedness is not required. reversed output accepted when order is dropped) -/ namespace PRemoveDuplicatesFromSortedListIi abbrev Input := List Int abbrev Output := List Int /-! ### Specification helpers -/ /-- `sortedAsc l` decides whether `l` is in non-decreasing order. -/ def sortedAsc : List Int → Bool | [] => true | [_] => true | a :: b :: t => a ≤ b && sortedAsc (b :: t) /-- `x` appears in `l` exactly once. -/ def OccursExactlyOnce (l : List Int) (x : Int) : Prop := l.count x = 1 /-! ### Validity predicate (V) -/ /-- Valid input: at most 300 values, each between -100 and 100, sorted ascending. -/ def isValidInput (input : Input) : Bool := input.length ≤ 300 && input.all (fun x => -100 ≤ x && x ≤ 100) && sortedAsc input /-! ### Ideal specification (P_spec) -/ /-- `result` is exactly the subsequence of `input` keeping the values that occur exactly once in `input`: every kept value occurs once, and none is omitted. -/ def deleteDuplicates_spec (input : Input) (result : Output) : Prop := (result.Sublist input ∧ ∀ x ∈ result, OccursExactlyOnce input x) ∧ ∀ x ∈ input, OccursExactlyOnce input x → x ∈ result /-! ### Decidable specification (P_check) -/ /-- Decides the exact-once condition by reducing it to the decidable equality `l.count x = 1`. -/ instance instDecidableOccursExactlyOnce (l : List Int) (x : Int) : Decidable (OccursExactlyOnce l x) := by unfold OccursExactlyOnce infer_instance /-- Decides the whole specification componentwise: list sublist, bounded quantifiers over the input and result lists, and list membership are all decidable for integer lists. -/ instance instDecidableDeleteDuplicatesSpec (input : Input) (result : Output) : Decidable (deleteDuplicates_spec input result) := by unfold deleteDuplicates_spec infer_instance /-- Executable checker obtained mechanically from the specification. -/ def deleteDuplicates_check (input : Input) (result : Output) : Bool := @decide (deleteDuplicates_spec input result) (by unfold deleteDuplicates_spec; infer_instance) /-- 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 simp [deleteDuplicates_check] /-! ### Implementation helpers -/ /-- Drops the maximal prefix of `l` whose elements all equal `x`. -/ def dropRun (x : Int) : List Int → List Int | [] => [] | y :: t => if y == x then dropRun x t else y :: t /-- Keeps the head of each maximal contiguous run of equal values whose length is exactly one. -/ def keepSingletons : List Int → List Int | [] => [] | x :: t => if dropRun x t = t then x :: keepSingletons (dropRun x t) else keepSingletons (dropRun x t) termination_by l => l.length decreasing_by all_goals simp_wf have key : ∀ (z : Int) (l : List Int), (dropRun z l).length ≤ l.length := by intro z l induction l with | nil => simp [dropRun] | cons a as ih => cases h : a == z with | false => simp [dropRun, h] | true => simp [dropRun, h] omega have h := key x t omega /-! ### Main algorithm (impl) -/ /-- Single-pass run-length scan over the sorted list, keeping exactly the values whose maximal contiguous run of equal values has length one. -/ def deleteDuplicateNodes (input : Input) : Output := keepSingletons input /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem deleteDuplicateNodes_correct (input : Input) (h : isValidInput input) : deleteDuplicates_spec input (deleteDuplicateNodes input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [1, 1, 1, 2, 3] #guard isValidInput [1] #guard isValidInput [(-100), 100] /-! ### 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, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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 [100, (-100)]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard deleteDuplicates_check [1, 1, 1, 2, 3] [2, 3] #guard deleteDuplicates_check [1] [1] #guard deleteDuplicates_check [(-100), 100] [(-100), 100] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(deleteDuplicates_check [1, 1, 1, 2, 3] []) #guard !(deleteDuplicates_check [1] []) #guard !(deleteDuplicates_check [(-100), 100] [100, (-100)]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard deleteDuplicateNodes [1, 1, 1, 2, 3] == [2, 3] #guard deleteDuplicateNodes [1] == [1] #guard deleteDuplicateNodes [(-100), 100] == [(-100), 100] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard deleteDuplicates_check [1, 1, 1, 2, 3] (deleteDuplicateNodes [1, 1, 1, 2, 3]) #guard deleteDuplicates_check [1] (deleteDuplicateNodes [1]) #guard deleteDuplicates_check [(-100), 100] (deleteDuplicateNodes [(-100), 100]) end PRemoveDuplicatesFromSortedListIi