import Mathlib /-! # Reverse Linked List Ii Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list. ## Constraints - The number of nodes in the list is n. - 1 <= n <= 500 - -500 <= Node.val <= 500 - 1 <= left <= right <= n ## Provided examples - `head = [1, 2, 3, 4, 5], left = 2, right = 4` → `[1, 4, 3, 2, 5]` - `head = [5], left = 1, right = 1` → `[5]` - `head = [1, 2, 3], left = 1, right = 3` → `[3, 2, 1]` ## Synthesized negative examples - invalid input: `head = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], left = 1, right = 1` ([structural] a predicate that admits 1 <= n <= 500. 501 nodes; one past the length ceiling) - invalid input: `head = [501], left = 1, right = 1` ([structural] a predicate that admits -500 <= Node.val <= 500. value one above the stated maximum) - invalid input: `head = [1], left = 0, right = 1` ([structural] a predicate that admits 1 <= left <= right <= n. left one below its minimum) - `head = [1, 2, 3, 4, 5], left = 2, right = 4` → `[1, 2, 4, 3, 5]` is wrong ([structural] range starts at left+1 rather than left; only positions 3 and 4 are reversed. segment begins one node too late) - `head = [5], left = 1, right = 1` → `[]` is wrong ([structural] nothing requires the output to contain the input's nodes. empty list does no reversal work) - `head = [1, 2, 3], left = 1, right = 3` → `[1, 3, 2]` is wrong ([structural] not_optimal does not apply; the reversed range starts at left+1 instead of left. Positions 2 and 3 reversed; position 1 unchanged.) -/ namespace PReverseLinkedListIi abbrev Input := (List Int) × (Nat) × (Nat) abbrev Output := List Int /-! ### Validity predicate (V) -/ /-- Valid input: 1 ≤ head.length ≤ 500, every entry between -500 and 500, and 1 ≤ left ≤ right ≤ head.length. -/ def isValidInput (input : Input) : Bool := let (head, left, right) := input 1 ≤ head.length && head.length ≤ 500 && head.all (fun x => -500 ≤ x && x ≤ 500) && 1 ≤ left && left ≤ right && right ≤ head.length /-! ### Ideal specification (P_spec) -/ /-- `result` has the same length as `head`, agrees with `head` at every position outside `left`–`right`, and carries the segment from `left` to `right` reversed. -/ def reverseBetween_spec (input : Input) (result : Output) : Prop := let (head, left, right) := input result.length = head.length ∧ ∀ i : Nat, i < result.length → (i + 1 < left ∨ right < i + 1 → result[i]? = head[i]?) ∧ (left ≤ i + 1 ∧ i + 1 ≤ right → result[i]? = head[left + right - (i + 1) - 1]?) /-! ### Decidable specification (P_check) -/ /-- Executable checker obtained mechanically from the specification. -/ def reverseBetween_check (input : Input) (result : Output) : Bool := @decide (reverseBetween_spec input result) (by unfold reverseBetween_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem reverseBetween_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : reverseBetween_check input result ↔ reverseBetween_spec input result := by simp [reverseBetween_check] /-! ### Main algorithm (impl) -/ /-- Reverses the 1-indexed segment `left`–`right` by slicing the list into prefix, segment, and suffix and reassembling with the segment reversed. -/ def reverseSublist (input : Input) : Output := let (head, left, right) := input let pre := head.take (left - 1) let middle := (head.drop (left - 1)).take (right - left + 1) let suffix := head.drop right pre ++ middle.reverse ++ suffix /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem reverseSublist_correct (input : Input) (h : isValidInput input) : reverseBetween_spec input (reverseSublist input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([1, 2, 3, 4, 5], 2, 4) #guard isValidInput ([5], 1, 1) #guard isValidInput ([1, 2, 3], 1, 3) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 1, 1)) #guard !(isValidInput ([501], 1, 1)) #guard !(isValidInput ([1], 0, 1)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard reverseBetween_check ([1, 2, 3, 4, 5], 2, 4) [1, 4, 3, 2, 5] #guard reverseBetween_check ([5], 1, 1) [5] #guard reverseBetween_check ([1, 2, 3], 1, 3) [3, 2, 1] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(reverseBetween_check ([1, 2, 3, 4, 5], 2, 4) [1, 2, 4, 3, 5]) #guard !(reverseBetween_check ([5], 1, 1) []) #guard !(reverseBetween_check ([1, 2, 3], 1, 3) [1, 3, 2]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard reverseSublist ([1, 2, 3, 4, 5], 2, 4) == [1, 4, 3, 2, 5] #guard reverseSublist ([5], 1, 1) == [5] #guard reverseSublist ([1, 2, 3], 1, 3) == [3, 2, 1] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard reverseBetween_check ([1, 2, 3, 4, 5], 2, 4) (reverseSublist ([1, 2, 3, 4, 5], 2, 4)) #guard reverseBetween_check ([5], 1, 1) (reverseSublist ([5], 1, 1)) #guard reverseBetween_check ([1, 2, 3], 1, 3) (reverseSublist ([1, 2, 3], 1, 3)) end PReverseLinkedListIi