import Mathlib /-! # Remove Element Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val. Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things: Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums. Return k. Custom Judge: The judge will test your solution with the following code: int[] nums = [...]; // Input array int val = ...; // Value to remove int[] expectedNums = [...]; // The expected answer with correct length. // It is sorted with no values equaling val. int k = removeElement(nums, val); // Calls your implementation assert k == expectedNums.length; sort(nums, 0, k); // Sort the first k elements of nums for (int i = 0; i < actualLength; i++) { assert nums[i] == expectedNums[i]; } If all assertions pass, then your solution will be accepted. ## Constraints - 0 <= nums.length <= 100 - 0 <= nums[i] <= 50 - 0 <= val <= 100 ## Provided examples - `nums = [], val = 1` → `0` - `nums = [42], val = 42` → `0` - `nums = [42], val = 100` → `1` ## Synthesized negative examples - 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], val = 1` ([structural] a predicate that admits 0 <= nums.length <= 100. length one past maximum; predicate checking element values and val but not length accepts it) - invalid input: `nums = [51], val = 1` ([structural] a predicate that admits 0 <= nums[i] <= 50. one past element maximum; predicate checking length and val but not element values accepts it) - invalid input: `nums = [1], val = 101` ([structural] a predicate that admits 0 <= val <= 100. one past val maximum; predicate checking length and elements but not val accepts it) - `nums = [], val = 1` → `1` is wrong ([structural] the returned count is not required to equal the number of elements not equal to val. empty array leaves prefix constraints vacuously satisfied) - `nums = [42], val = 42` → `1` is wrong ([structural] malformed_shape is inapplicable; the count ignores which elements equal val. returns 1, the number of entries, instead of 0) - `nums = [42], val = 100` → `0` is wrong ([structural] drops the completeness requirement that all non-val elements appear in the first k. empty prefix contains no val) -/ namespace PRemoveElement abbrev Input := (List Nat) × (Nat) abbrev Output := Nat /-! ### Validity predicate (V) -/ /-- Valid input has at most 100 entries, each at most 50, and `val` at most 100. -/ def isValidInput (input : Input) : Bool := input.1.length ≤ 100 && input.1.all (fun n => n ≤ 50) && input.2 ≤ 100 /-! ### Ideal specification (P_spec) -/ /-- `result` is the length of a kept list containing exactly the non-`val` entries of `nums`. -/ def countNotEqual_spec (input : Input) (result : Output) : Prop := ∃ keep rest : List Nat, List.Perm (keep ++ rest) input.1 ∧ keep.length = result ∧ (∀ x ∈ keep, x ≠ input.2) ∧ (∀ x ∈ rest, x = input.2) /-! ### Decidable specification (P_check) -/ /-- Decides the existential over the kept and removed lists in `countNotEqual_spec`: suitable lists exist exactly when `result` is the number of entries of `input.1` different from `input.2`. The two filtered halves of `input.1` witness the forward direction, while filtering both sides of the permutation by inequality with `input.2` gives the reverse length equation. -/ instance decCountNotEqualSpec (input : Input) (result : Output) : Decidable (∃ keep rest : List Nat, List.Perm (keep ++ rest) input.1 ∧ keep.length = result ∧ (∀ x ∈ keep, x ≠ input.2) ∧ (∀ x ∈ rest, x = input.2)) := decidable_of_iff (result = (input.1.filter (fun x => decide (x ≠ input.2))).length) (by constructor · intro h refine ⟨input.1.filter (fun x => decide (x ≠ input.2)), input.1.filter (fun x => !(decide (x ≠ input.2))), ?_, ?_, ?_, ?_⟩ · exact List.filter_append_perm (fun x => decide (x ≠ input.2)) input.1 · exact h.symm · intro x hx have hx' := (List.mem_filter.mp hx).2 simpa using hx' · intro x hx have hx' := (List.mem_filter.mp hx).2 by_contra hne simp [hne] at hx' · rintro ⟨keep, rest, hperm, hlen, hkeep, hrest⟩ have hkeep' : keep.filter (fun x => decide (x ≠ input.2)) = keep := List.filter_eq_self.mpr fun x hx => decide_eq_true_eq.mpr (hkeep x hx) have hrest' : rest.filter (fun x => decide (x ≠ input.2)) = [] := by rw [List.filter_eq_nil_iff] intro x hx simp [hrest x hx] have hp := hperm.filter (fun x => decide (x ≠ input.2)) rw [List.filter_append, hkeep', hrest', List.append_nil] at hp have hlen' := hp.length_eq exact hlen.symm.trans hlen') /-- Executable checker obtained mechanically from the specification. -/ def countNotEqual_check (input : Input) (result : Output) : Bool := @decide (countNotEqual_spec input result) (by unfold countNotEqual_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem countNotEqual_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : countNotEqual_check input result ↔ countNotEqual_spec input result := by simp [countNotEqual_check] /-! ### Implementation helpers -/ /-- The entries of `nums` that differ from `val`, in their original order. -/ def nonValEntries (nums : List Nat) (val : Nat) : List Nat := nums.filter (fun x => x != val) /-! ### Main algorithm (impl) -/ /-- Single-pass removal count: filter out entries equal to `val` and take the length. -/ def removeElement (input : Input) : Output := (nonValEntries input.1 input.2).length /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem removeElement_correct (input : Input) (h : isValidInput input) : countNotEqual_spec input (removeElement input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([], 1) #guard isValidInput ([42], 42) #guard isValidInput ([42], 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], 1)) #guard !(isValidInput ([51], 1)) #guard !(isValidInput ([1], 101)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard countNotEqual_check ([], 1) 0 #guard countNotEqual_check ([42], 42) 0 #guard countNotEqual_check ([42], 100) 1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(countNotEqual_check ([], 1) 1) #guard !(countNotEqual_check ([42], 42) 1) #guard !(countNotEqual_check ([42], 100) 0) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard removeElement ([], 1) == 0 #guard removeElement ([42], 42) == 0 #guard removeElement ([42], 100) == 1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard countNotEqual_check ([], 1) (removeElement ([], 1)) #guard countNotEqual_check ([42], 42) (removeElement ([42], 42)) #guard countNotEqual_check ([42], 100) (removeElement ([42], 100)) end PRemoveElement