import Mathlib /-! # Remove Nth Node From End Of List Given the head of a linked list, remove the nth node from the end of the list and return its head. ## Constraints - The number of nodes in the list is sz. - 1 <= sz <= 30 - 0 <= Node.val <= 100 - 1 <= n <= sz ## Provided examples - `head = [1, 2, 3, 4, 5], n = 2` → `[1, 2, 3, 5]` - `head = [1], n = 1` → `[]` - `head = [1, 2], n = 1` → `[1]` ## Synthesized negative examples - invalid input: `head = [-1], n = 1` ([structural] a predicate that admits 0 <= Node.val <= 100. negative node value; catches a predicate that checks only the maximum) - invalid input: `head = [101], n = 1` ([structural] a predicate that admits 0 <= Node.val <= 100. one past the stated maximum; catches a predicate that checks only the minimum) - invalid input: `head = [1], n = 2` ([structural] a predicate that admits 1 <= n <= sz. n one past list length; checking each parameter alone accepts it) - `head = [1, 2, 3, 4, 5], n = 2` → `[1, 2, 3, 4]` is wrong ([structural] the node to remove is one position off from the stated nth-from-end. removed the 1st from end instead of the 2nd) - `head = [1], n = 1` → `[1]` is wrong ([structural] misreads 'return its head' as returning the original head, not the head of the resulting list. returns the original head after removal) - `head = [1, 2], n = 1` → `[1, 3]` is wrong ([structural] does not forbid extra nodes in output. removed 2 but appended extra 3) -/ namespace PRemoveNthNodeFromEndOfList abbrev Input := (List Int) × (Nat) abbrev Output := List Nat /-! ### Specification helpers -/ /-- `k` is the index of the node to remove: the nth node from the end sits at position `k`. -/ def IsRemovalIndex (head : List Int) (n k : Nat) : Prop := k + n = head.length /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 30 nodes, every value between 0 and 100 inclusive, and `1 ≤ n ≤ length`. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 30 && input.1.all (fun v => 0 ≤ v && v ≤ 100) && 1 ≤ input.2 && input.2 ≤ input.1.length /-! ### Ideal specification (P_spec) -/ /-- `result` is `head` with the nth node from the end removed: for the index `k` with `k + n = head.length`, `result` has one fewer element and each position `j` copies `head[j]` below `k` and `head[j + 1]` at or past `k`, coerced to `Nat`. -/ def removeNthFromEnd_spec (input : Input) (result : Output) : Prop := ∃ k : Nat, IsRemovalIndex input.1 input.2 k ∧ result.length + 1 = input.1.length ∧ ∀ j : Nat, j < result.length → result[j]? = (if j < k then input.1[j]? else input.1[j + 1]?).map Int.toNat /-! ### Decidable specification (P_check) -/ /-- Executable checker for `removeNthFromEnd_spec`, scanning the removal index over `0 … head.length`. -/ def removeNthFromEnd_check (input : Input) (result : Output) : Bool := (List.range (input.1.length + 1)).any fun k => k + input.2 == input.1.length && result.length + 1 == input.1.length && (List.range result.length).all fun j => result[j]? == (if j < k then input.1[j]? else input.1[j + 1]?).map Int.toNat /-- On valid input the checker accepts exactly the specified outputs. -/ theorem removeNthFromEnd_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : removeNthFromEnd_check input result ↔ removeNthFromEnd_spec input result := by simp only [removeNthFromEnd_check, removeNthFromEnd_spec, IsRemovalIndex, List.any_eq_true, List.all_eq_true, List.mem_range, Bool.and_eq_true, beq_iff_eq, decide_eq_true_eq] constructor · rintro ⟨k, _hkw, ⟨⟨hkn, hlen⟩, hall⟩⟩ exact ⟨k, hkn, hlen, fun j hj => hall j hj⟩ · rintro ⟨k, hkn, hlen, hall⟩ exact ⟨k, by omega, ⟨⟨hkn, hlen⟩, fun j hj => hall j hj⟩⟩ /-! ### Implementation helpers -/ /-- Rebuilds `head` without the node at index `head.length - n`, coercing values to `Nat`. -/ def removeAtFromEnd (head : List Int) (n : Nat) : List Nat := let k := head.length - n (head.take k ++ head.drop (k + 1)).map Int.toNat /-! ### Main algorithm (impl) -/ /-- Removes the nth node from the end in O(sz) by concatenating the prefix before index `head.length - n` with the suffix after it. -/ def removeNthFromEndImpl (input : Input) : Output := removeAtFromEnd input.1 input.2 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem removeNthFromEndImpl_correct (input : Input) (h : isValidInput input) : removeNthFromEnd_spec input (removeNthFromEndImpl input) := by simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true] at h refine ⟨input.1.length - input.2, ?_, ?_, ?_⟩ · unfold IsRemovalIndex omega · simp [removeNthFromEndImpl, removeAtFromEnd, List.length_take, List.length_drop] omega · intro j hj simp only [removeNthFromEndImpl, removeAtFromEnd, List.getElem?_map, List.getElem?_append, List.length_take, List.getElem?_take, List.getElem?_drop] have hk : input.1.length - input.2 ≤ input.1.length := Nat.sub_le _ _ rw [Nat.min_eq_left hk] split <;> simp_all <;> congr 2 <;> omega /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([1, 2, 3, 4, 5], 2) #guard isValidInput ([1], 1) #guard isValidInput ([1, 2], 1) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([(-1)], 1)) #guard !(isValidInput ([101], 1)) #guard !(isValidInput ([1], 2)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard removeNthFromEnd_check ([1, 2, 3, 4, 5], 2) [1, 2, 3, 5] #guard removeNthFromEnd_check ([1], 1) [] #guard removeNthFromEnd_check ([1, 2], 1) [1] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(removeNthFromEnd_check ([1, 2, 3, 4, 5], 2) [1, 2, 3, 4]) #guard !(removeNthFromEnd_check ([1], 1) [1]) #guard !(removeNthFromEnd_check ([1, 2], 1) [1, 3]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard removeNthFromEndImpl ([1, 2, 3, 4, 5], 2) == [1, 2, 3, 5] #guard removeNthFromEndImpl ([1], 1) == [] #guard removeNthFromEndImpl ([1, 2], 1) == [1] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard removeNthFromEnd_check ([1, 2, 3, 4, 5], 2) (removeNthFromEndImpl ([1, 2, 3, 4, 5], 2)) #guard removeNthFromEnd_check ([1], 1) (removeNthFromEndImpl ([1], 1)) #guard removeNthFromEnd_check ([1, 2], 1) (removeNthFromEndImpl ([1, 2], 1)) end PRemoveNthNodeFromEndOfList