import Mathlib /-! # Partition List Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions. ## Constraints - The number of nodes in the list is in the range [0, 200]. - -100 <= Node.val <= 100 - -200 <= x <= 200 ## Provided examples - `head = [1, 4, 3, 2, 5, 2], x = 3` → `[1, 2, 2, 4, 3, 5]` - `head = [2, 1], x = 2` → `[1, 2]` - `head = [-100, 100, 0], x = 0` → `[-100, 100, 0]` ## 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], x = 0` ([structural] a predicate that admits The number of nodes in the list is in the range [0, 200].. 201 nodes, one past the stated maximum) - invalid input: `head = [-101, 0], x = 0` ([structural] a predicate that admits -100 <= Node.val <= 100. head value below the allowed minimum) - invalid input: `head = [0, 0, 101], x = 0` ([structural] a predicate that admits -100 <= Node.val <= 100. invalid tail value; a head-only checker accepts it) - `head = [1, 4, 3, 2, 5, 2], x = 3` → `[1, 4, 3, 2, 5, 2]` is wrong ([structural] the all-less-before-greater condition is not enforced. echoes input; valid only if partition does nothing) - `head = [2, 1], x = 2` → `[2, 1]` is wrong ([structural] partition condition dropped; original order alone is accepted. preserves original order but puts 2 before 1) - `head = [-100, 100, 0], x = 0` → `[-100, 100]` is wrong ([structural] output length need not equal input length. Missing equal-to-x node; partition and order still hold.) -/ namespace PPartitionList abbrev Input := (List Int) × (Int) abbrev Output := List Int /-! ### Specification helpers -/ /-- `result` is the stable partition of `head` around `x`: a permutation of `head` where every value below `x` precedes every value at least `x` and each of the two groups keeps its original order from `head`. -/ def IsStablePartition (head : List Int) (x : Int) (result : List Int) : Prop := head.Perm result ∧ result.Pairwise (fun a b => x ≤ a → x ≤ b) ∧ result.filter (fun v => decide (v < x)) = head.filter (fun v => decide (v < x)) ∧ result.filter (fun v => decide (x ≤ v)) = head.filter (fun v => decide (x ≤ v)) /-! ### Validity predicate (V) -/ /-- Valid input: at most 200 nodes, every node value in [-100, 100], and x in [-200, 200]. -/ def isValidInput (input : Input) : Bool := decide (input.1.length ≤ 200) && input.1.all (fun v => decide (-100 ≤ v ∧ v ≤ 100)) && decide (-200 ≤ input.2 ∧ input.2 ≤ 200) /-! ### Ideal specification (P_spec) -/ /-- `result` is the stable partition of the input's list around its threshold `x`. -/ def partitionList_spec (input : Input) (result : Output) : Prop := IsStablePartition input.1 input.2 result /-! ### Decidable specification (P_check) -/ /-- Executable checker obtained mechanically from the specification. -/ def partitionList_check (input : Input) (result : Output) : Bool := result == input.1.filter (fun v => decide (v < input.2)) ++ input.1.filter (fun v => decide (input.2 ≤ v)) theorem pl_split_of_pairwise (x : Int) : ∀ l : List Int, l.Pairwise (fun a b => x ≤ a → x ≤ b) → l = l.filter (fun v => decide (v < x)) ++ l.filter (fun v => decide (x ≤ v)) := by intro l induction l with | nil => intro _; simp | cons a t ih => intro hp rw [List.pairwise_cons] at hp obtain ⟨hall, ht⟩ := hp by_cases ha : a < x · have h2 : ¬ (x ≤ a) := not_le.mpr ha simp only [List.filter_cons] rw [if_pos (by simpa using ha), if_neg (by simpa using h2), List.cons_append] exact congrArg (List.cons a) (ih ht) · have hxa : x ≤ a := not_lt.mp ha have hnil : t.filter (fun v => decide (v < x)) = [] := by refine List.filter_eq_nil_iff.mpr ?_ intro b hb simp only [decide_eq_true_eq, not_lt] exact hall b hb hxa have hself : t.filter (fun v => decide (x ≤ v)) = t := by refine List.filter_eq_self.mpr ?_ intro b hb simp only [decide_eq_true_eq] exact hall b hb hxa simp only [List.filter_cons] rw [if_neg (by simpa using ha), if_pos (by simpa using hxa), hnil, hself, List.nil_append] theorem pl_perm_split (x : Int) (l : List Int) : l.Perm (l.filter (fun v => decide (v < x)) ++ l.filter (fun v => decide (x ≤ v))) := by have hfe : (fun v : Int => !decide (v < x)) = (fun v : Int => decide (x ≤ v)) := by funext v by_cases hv : v < x · simp [hv, not_le.mpr hv] · simp [hv, not_lt.mp hv] have hperm := List.filter_append_perm (fun v : Int => decide (v < x)) l rw [hfe] at hperm exact hperm.symm theorem pl_split_pairwise (x : Int) (l : List Int) : (l.filter (fun v => decide (v < x)) ++ l.filter (fun v => decide (x ≤ v))).Pairwise (fun a b => x ≤ a → x ≤ b) := by refine List.pairwise_append.mpr ⟨?_, ?_, ?_⟩ · refine List.pairwise_of_forall_mem_list ?_ intro a ha b _ hxa have hax : a < x := by simpa using (List.mem_filter.mp ha).2 exact absurd hxa (not_le.mpr hax) · refine List.pairwise_of_forall_mem_list ?_ intro a _ b hb _ simpa using (List.mem_filter.mp hb).2 · intro a _ b hb _ simpa using (List.mem_filter.mp hb).2 theorem pl_split_filter_lt (x : Int) (l : List Int) : (l.filter (fun v => decide (v < x)) ++ l.filter (fun v => decide (x ≤ v))).filter (fun v => decide (v < x)) = l.filter (fun v => decide (v < x)) := by have h1 : (l.filter (fun v => decide (v < x))).filter (fun v => decide (v < x)) = l.filter (fun v => decide (v < x)) := by refine List.filter_eq_self.mpr ?_ intro a ha exact (List.mem_filter.mp ha).2 have h2 : (l.filter (fun v => decide (x ≤ v))).filter (fun v => decide (v < x)) = [] := by refine List.filter_eq_nil_iff.mpr ?_ intro a ha have hxa : x ≤ a := by simpa using (List.mem_filter.mp ha).2 simp only [decide_eq_true_eq, not_lt] exact hxa rw [List.filter_append, h1, h2, List.append_nil] theorem pl_split_filter_ge (x : Int) (l : List Int) : (l.filter (fun v => decide (v < x)) ++ l.filter (fun v => decide (x ≤ v))).filter (fun v => decide (x ≤ v)) = l.filter (fun v => decide (x ≤ v)) := by have h1 : (l.filter (fun v => decide (v < x))).filter (fun v => decide (x ≤ v)) = [] := by refine List.filter_eq_nil_iff.mpr ?_ intro a ha have hax : a < x := by simpa using (List.mem_filter.mp ha).2 simp only [decide_eq_true_eq, not_le] exact hax have h2 : (l.filter (fun v => decide (x ≤ v))).filter (fun v => decide (x ≤ v)) = l.filter (fun v => decide (x ≤ v)) := by refine List.filter_eq_self.mpr ?_ intro a ha exact (List.mem_filter.mp ha).2 rw [List.filter_append, h1, h2, List.nil_append] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem partitionList_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : partitionList_check input result ↔ partitionList_spec input result := by unfold partitionList_check partitionList_spec IsStablePartition rw [beq_iff_eq] constructor · rintro rfl exact ⟨pl_perm_split input.2 input.1, pl_split_pairwise input.2 input.1, pl_split_filter_lt input.2 input.1, pl_split_filter_ge input.2 input.1⟩ · rintro ⟨-, hpw, h3, h4⟩ rw [← h3, ← h4] exact pl_split_of_pairwise input.2 result hpw /-! ### Main algorithm (impl) -/ /-- Stable partition by two ordered filters: values below `x` in original order, then values at least `x` in original order. -/ def partitionListValues (input : Input) : Output := input.1.filter (fun v => decide (v < input.2)) ++ input.1.filter (fun v => decide (input.2 ≤ v)) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem partitionListValues_correct (input : Input) (h : isValidInput input) : partitionList_spec input (partitionListValues input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([1, 4, 3, 2, 5, 2], 3) #guard isValidInput ([2, 1], 2) #guard isValidInput ([-100, 100, 0], 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, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 0], 0)) #guard !(isValidInput ([0, 0, 101], 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard partitionList_check ([1, 4, 3, 2, 5, 2], 3) [1, 2, 2, 4, 3, 5] #guard partitionList_check ([2, 1], 2) [1, 2] #guard partitionList_check ([(-100), 100, 0], 0) [(-100), 100, 0] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(partitionList_check ([1, 4, 3, 2, 5, 2], 3) [1, 4, 3, 2, 5, 2]) #guard !(partitionList_check ([2, 1], 2) [2, 1]) #guard !(partitionList_check ([(-100), 100, 0], 0) [(-100), 100]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard partitionListValues ([1, 4, 3, 2, 5, 2], 3) == [1, 2, 2, 4, 3, 5] #guard partitionListValues ([2, 1], 2) == [1, 2] #guard partitionListValues ([(-100), 100, 0], 0) == [(-100), 100, 0] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard partitionList_check ([1, 4, 3, 2, 5, 2], 3) (partitionListValues ([1, 4, 3, 2, 5, 2], 3)) #guard partitionList_check ([2, 1], 2) (partitionListValues ([2, 1], 2)) #guard partitionList_check ([(-100), 100, 0], 0) (partitionListValues ([(-100), 100, 0], 0)) end PPartitionList