import Mathlib /-! # Rotate List Given the head of a linked list, rotate the list to the right by k places. ## Constraints - The number of nodes in the list is in the range [0, 500]. - -100 <= Node.val <= 100 - 0 <= k <= 2 * 10^9 ## Provided examples - `head = [1, 2, 3, 4, 5], k = 2` → `[4, 5, 1, 2, 3]` - `head = [0, 1, 2], k = 4` → `[2, 0, 1]` - `head = [1], k = 0` → `[1]` ## Synthesized negative examples - invalid input: `head = [101], k = 0` ([structural] a predicate that admits -100 <= Node.val <= 100. one past the node value maximum) - invalid input: `head = [1], k = -1` ([structural] a predicate that admits 0 <= k <= 2 * 10^9. k negative, below the stated minimum) - invalid input: `head = [-101], k = 0` ([structural] a predicate that admits -100 <= Node.val <= 100. one below the node value minimum) - `head = [1, 2, 3, 4, 5], k = 2` → `[5, 1, 2, 3, 4]` is wrong ([structural] rotation amount is off by one; k-1 instead of k. right rotation by 1, one step less than k=2) - `head = [0, 1, 2], k = 4` → `[1, 2, 0]` is wrong ([structural] direction of rotation is unspecified; left rotation accepted. Rotated left by one, not right by k) - `head = [1], k = 0` → `[1, 1]` is wrong ([structural] output length is not required to match input length. one extra node repeats the only value; valid list) -/ namespace PRotateList abbrev Input := (List Int) × (Int) abbrev Output := List Int /-! ### Validity predicate (V) -/ /-- Valid input: at most 500 values in `[-100, 100]`, and `k` between `0` and `2·10^9`. -/ def isValidInput (input : Input) : Bool := input.1.length ≤ 500 && input.1.all (fun x => -100 ≤ x && x ≤ 100) && 0 ≤ input.2 && input.2 ≤ 2000000000 /-! ### Ideal specification (P_spec) -/ /-- `result` has `head`'s length and each `head[i]` moves cyclically to `(i + k.toNat) % head.length`. -/ def rotateRight_spec (input : Input) (result : Output) : Prop := result.length = input.1.length ∧ ∀ i : Nat, i < input.1.length → result[(i + input.2.toNat) % input.1.length]? = input.1[i]? /-! ### Decidable specification (P_check) -/ /-- Executable checker obtained mechanically from the specification. -/ def rotateRight_check (input : Input) (result : Output) : Bool := @decide (rotateRight_spec input result) (by unfold rotateRight_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem rotateRight_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : rotateRight_check input result ↔ rotateRight_spec input result := by simp [rotateRight_check] /-! ### Main algorithm (impl) -/ /-- Right rotation by cyclic shift: split at `n - (k.toNat % n)` and append the tail before the head. -/ def rotateListRight (input : Input) : Output := if input.1.length = 0 then [] else let n := input.1.length let r := input.2.toNat % n input.1.drop (n - r) ++ input.1.take (n - r) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem rotateListRight_correct (input : Input) (h : isValidInput input) : rotateRight_spec input (rotateListRight input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([1, 2, 3, 4, 5], 2) #guard isValidInput ([0, 1, 2], 4) #guard isValidInput ([1], 0) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([101], 0)) #guard !(isValidInput ([1], (-1))) #guard !(isValidInput ([(-101)], 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard rotateRight_check ([1, 2, 3, 4, 5], 2) [4, 5, 1, 2, 3] #guard rotateRight_check ([0, 1, 2], 4) [2, 0, 1] #guard rotateRight_check ([1], 0) [1] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(rotateRight_check ([1, 2, 3, 4, 5], 2) [5, 1, 2, 3, 4]) #guard !(rotateRight_check ([0, 1, 2], 4) [1, 2, 0]) #guard !(rotateRight_check ([1], 0) [1, 1]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard rotateListRight ([1, 2, 3, 4, 5], 2) == [4, 5, 1, 2, 3] #guard rotateListRight ([0, 1, 2], 4) == [2, 0, 1] #guard rotateListRight ([1], 0) == [1] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard rotateRight_check ([1, 2, 3, 4, 5], 2) (rotateListRight ([1, 2, 3, 4, 5], 2)) #guard rotateRight_check ([0, 1, 2], 4) (rotateListRight ([0, 1, 2], 4)) #guard rotateRight_check ([1], 0) (rotateListRight ([1], 0)) end PRotateList