import Mathlib /-! # Sort Colors Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively. You must solve this problem without using the library's sort function. ## Constraints - n == nums.length - 1 <= n <= 300 - nums[i] is either 0, 1, or 2. ## Provided examples - `nums = [2, 0, 2, 1, 1, 0]` → `[0, 0, 1, 1, 2, 2]` - `nums = [2, 0, 1]` → `[0, 1, 2]` - `nums = [1]` → `[1]` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= n <= 300. empty where at least one element is required) - invalid input: `nums = [-1]` ([structural] a predicate that admits nums[i] is either 0, 1, or 2.. negative color below the allowed set) - invalid input: `nums = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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 1 <= n <= 300. one past the maximum length) - `nums = [2, 0, 2, 1, 1, 0]` → `[2, 0, 2, 1, 1, 0]` is wrong ([structural] nothing requires the output to be sorted. input echoed back, no sorting performed) - `nums = [2, 0, 1]` → `[0, 1, 1]` is wrong ([structural] result not required to preserve the multiset of input colors. sorted length 3 but two 1s and no 2) - `nums = [2, 0, 2, 1, 1, 0]` → `[1, 0, 0, 1, 2, 2]` is wrong ([structural] the result differs from the required one in at least one position. amended 2026-08-18: second mutation of a screened positive to reach quota) -/ namespace PSortColors abbrev Input := List Int abbrev Output := List Int /-! ### Validity predicate (V) -/ /-- Valid input: a list of length 1 to 300 whose every element is 0, 1, or 2. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 300 && input.all (fun x => x == 0 || x == 1 || x == 2) /-! ### Ideal specification (P_spec) -/ /-- `result` has the same length as `input`, is a permutation of it, and is sorted in nondecreasing order. -/ def sortColors_spec (input : Input) (result : Output) : Prop := result.length = input.length ∧ result.Perm input ∧ result.SortedLE /-! ### Decidable specification (P_check) -/ /-- Boolean sortedness test: every adjacent pair is nondecreasing. -/ def adjacentLE : List Int → Bool | [] => true | [_] => true | a :: b :: rest => decide (a ≤ b) && adjacentLE (b :: rest) /-- Executable checker for `sortColors_spec`, deciding each conjunct with the computable library instances. -/ def sortColors_check (input : Input) (result : Output) : Bool := decide (result.length = input.length) && @decide (result.Perm input) (List.decidablePerm result input) && adjacentLE result theorem root_of_bridges (bridge : ∀ xs : List Int, adjacentLE xs = true ↔ xs.SortedLE) (input : Input) (result : Output) : sortColors_check input result ↔ sortColors_spec input result := by simp [sortColors_check, sortColors_spec, bridge, and_assoc] theorem adjacentLE_iff_sortedLE (xs : List Int) : adjacentLE xs = true ↔ xs.SortedLE := by rw [List.sortedLE_iff_isChain] induction xs with | nil => simp [adjacentLE] | cons a xs ih => cases xs with | nil => simp [adjacentLE] | cons b xs => simpa only [adjacentLE, Bool.and_eq_true, decide_eq_true_eq, List.isChain_cons_cons] using and_congr Iff.rfl ih /-- On valid input the checker accepts exactly the specified outputs. -/ theorem sortColors_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : sortColors_check input result ↔ sortColors_spec input result := by exact root_of_bridges adjacentLE_iff_sortedLE input result /-! ### Implementation helpers -/ /-- One-pass traversal counting the occurrences of 0, 1, and 2 in `xs`. -/ def countColors : List Int → Nat × Nat × Nat | [] => (0, 0, 0) | x :: xs => let (n0, n1, n2) := countColors xs if x == 0 then (n0 + 1, n1, n2) else if x == 1 then (n0, n1 + 1, n2) else (n0, n1, n2 + 1) /-- Builds the sorted list from three counts: that many 0s, then 1s, then 2s. -/ def makeSortedResult (n0 n1 n2 : Nat) : List Int := List.replicate n0 0 ++ List.replicate n1 1 ++ List.replicate n2 2 /-! ### Main algorithm (impl) -/ /-- Counting sort specialized to the three colors: count, then rebuild in order. -/ def sortColorsImpl (input : Input) : Output := let (n0, n1, n2) := countColors input makeSortedResult n0 n1 n2 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem sortColorsImpl_correct (input : Input) (h : isValidInput input) : sortColors_spec input (sortColorsImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [2, 0, 2, 1, 1, 0] #guard isValidInput [2, 0, 1] #guard isValidInput [1] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [(-1)]) #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, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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 sortColors_check [2, 0, 2, 1, 1, 0] [0, 0, 1, 1, 2, 2] #guard sortColors_check [2, 0, 1] [0, 1, 2] #guard sortColors_check [1] [1] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(sortColors_check [2, 0, 2, 1, 1, 0] [2, 0, 2, 1, 1, 0]) #guard !(sortColors_check [2, 0, 1] [0, 1, 1]) #guard !(sortColors_check [2, 0, 2, 1, 1, 0] [1, 0, 0, 1, 2, 2]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard sortColorsImpl [2, 0, 2, 1, 1, 0] == [0, 0, 1, 1, 2, 2] #guard sortColorsImpl [2, 0, 1] == [0, 1, 2] #guard sortColorsImpl [1] == [1] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard sortColors_check [2, 0, 2, 1, 1, 0] (sortColorsImpl [2, 0, 2, 1, 1, 0]) #guard sortColors_check [2, 0, 1] (sortColorsImpl [2, 0, 1]) #guard sortColors_check [1] (sortColorsImpl [1]) end PSortColors