import Mathlib /-! # Reverse Nodes In K Group Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is. You may not alter the values in the list's nodes, only nodes themselves may be changed. ## Constraints - The number of nodes in the list is n. - 1 <= k <= n <= 5000 - 0 <= Node.val <= 1000 ## Provided examples - `head = [1, 2, 3, 4, 5], k = 2` → `[2, 1, 4, 3, 5]` - `head = [1, 2, 3, 4, 5], k = 3` → `[3, 2, 1, 4, 5]` - `head = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21], k = 6` → `[6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, 18, 17, 16, 15, 14, 13, 19, 20, 21]` ## Synthesized negative examples - invalid input: `head = [1], k = 0` ([structural] a predicate that admits 1 <= k <= n <= 5000. k below positive bound; a predicate checking only k <= length accepts) - invalid input: `head = [1], k = 2` ([structural] a predicate that admits 1 <= k <= n <= 5000. k exceeds list length; a predicate checking k positive alone accepts) - invalid input: `head = [], k = 1` ([structural] a predicate that admits 1 <= k <= n <= 5000. empty list; a predicate checking only node values accepts) - `head = [1, 2, 3, 4, 5], k = 2` → `[1, 2, 3, 4, 5]` is wrong ([structural] nothing requires any group to be reversed. echoes the input; all other conditions hold) - `head = [1, 2, 3, 4, 5], k = 3` → `[2, 1, 3, 4, 5]` is wrong ([structural] group size is one less than k. reverses first two nodes; only k-at-a-time broken) - `head = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21], k = 6` → `[5, 4, 3, 2, 1, 10, 9, 8, 7, 6, 15, 14, 13, 12, 11, 20, 19, 18, 17, 16, 21]` is wrong ([structural] group size is k-1 instead of k. Groups of 5 reversed instead of 6; leftover 1 remains.) -/ namespace PReverseNodesInKGroup abbrev Input := (List Nat) × (Nat) abbrev Output := List Nat /-! ### Validity predicate (V) -/ /-- Valid input: `1 ≤ k ≤ length head ≤ 5000` and every node value is at most 1000. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.2 && input.2 ≤ input.1.length && input.1.length ≤ 5000 && input.1.all (fun v => v ≤ 1000) /-! ### Ideal specification (P_spec) -/ /-- `result` has the length of `head`, and at every index `i` with block `b = i / k` and position `p = i % k` it holds `head[b * k + (k - 1 - p)]` when the block is complete and `head[i]` when it is the trailing incomplete block. -/ def reverseKGroup_spec (input : Input) (result : Output) : Prop := result.length = input.1.length ∧ ∀ i : Nat, i < input.1.length → if (i / input.2 + 1) * input.2 ≤ input.1.length then result[i]? = input.1[i / input.2 * input.2 + (input.2 - 1 - i % input.2)]? else result[i]? = input.1[i]? /-! ### Decidable specification (P_check) -/ /-- Executable checker obtained mechanically from the specification. -/ def reverseKGroup_check (input : Input) (result : Output) : Bool := @decide (reverseKGroup_spec input result) (by unfold reverseKGroup_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem reverseKGroup_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : reverseKGroup_check input result ↔ reverseKGroup_spec input result := by simp [reverseKGroup_check] /-! ### Implementation helpers -/ /-- Reverses complete leading `k`-blocks of `l` while at least `k` of the `rem` remaining nodes persist. -/ def go (k rem : Nat) (l : List Nat) : List Nat := if k = 0 ∨ rem < k then l else (l.take k).reverse ++ go k (rem - k) (l.drop k) termination_by rem decreasing_by simp_wf omega /-! ### Main algorithm (impl) -/ /-- k-group reversal by chunked take/drop/reverse over the list with a remaining-node counter, O(n). -/ def reverseKGroupList (input : Input) : Output := go input.2 input.1.length input.1 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem reverseKGroupList_correct (input : Input) (h : isValidInput input) : reverseKGroup_spec input (reverseKGroupList input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([1, 2, 3, 4, 5], 2) #guard isValidInput ([1, 2, 3, 4, 5], 3) #guard isValidInput ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21], 6) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([1], 0)) #guard !(isValidInput ([1], 2)) #guard !(isValidInput ([], 1)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard reverseKGroup_check ([1, 2, 3, 4, 5], 2) [2, 1, 4, 3, 5] #guard reverseKGroup_check ([1, 2, 3, 4, 5], 3) [3, 2, 1, 4, 5] #guard reverseKGroup_check ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21], 6) [6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, 18, 17, 16, 15, 14, 13, 19, 20, 21] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(reverseKGroup_check ([1, 2, 3, 4, 5], 2) [1, 2, 3, 4, 5]) #guard !(reverseKGroup_check ([1, 2, 3, 4, 5], 3) [2, 1, 3, 4, 5]) #guard !(reverseKGroup_check ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21], 6) [5, 4, 3, 2, 1, 10, 9, 8, 7, 6, 15, 14, 13, 12, 11, 20, 19, 18, 17, 16, 21]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard reverseKGroupList ([1, 2, 3, 4, 5], 2) == [2, 1, 4, 3, 5] #guard reverseKGroupList ([1, 2, 3, 4, 5], 3) == [3, 2, 1, 4, 5] #guard reverseKGroupList ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21], 6) == [6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, 18, 17, 16, 15, 14, 13, 19, 20, 21] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard reverseKGroup_check ([1, 2, 3, 4, 5], 2) (reverseKGroupList ([1, 2, 3, 4, 5], 2)) #guard reverseKGroup_check ([1, 2, 3, 4, 5], 3) (reverseKGroupList ([1, 2, 3, 4, 5], 3)) #guard reverseKGroup_check ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21], 6) (reverseKGroupList ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21], 6)) end PReverseNodesInKGroup