import Mathlib /-! # Swap Nodes In Pairs Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.) ## Constraints - The number of nodes in the list is in the range [0, 100]. - 0 <= Node.val <= 100 ## Provided examples - `head = [1, 2, 3, 4]` → `[2, 1, 4, 3]` - `head = []` → `[]` - `head = [1]` → `[1]` ## Synthesized negative examples - invalid input: `head = [101]` ([structural] a predicate that admits 0 <= Node.val <= 100. one past the stated maximum value) - invalid input: `head = [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]` ([structural] a predicate that admits The number of nodes in the list is in the range [0, 100].. 101 nodes, one past the size ceiling) - invalid input: `head = [-1]` ([structural] a predicate that admits 0 <= Node.val <= 100. below the stated value floor) - `head = [1, 2, 3, 4]` → `[1, 2, 3, 4]` is wrong ([structural] no clause requires the output to be the swapped list; input is accepted as-is. returns input unchanged) - `head = []` → `[1]` is wrong ([structural] output length is not required to match input length. empty input; [1] has wrong length but satisfies other conditions) - `head = [1]` → `[]` is wrong ([structural] no requirement that the output retain the unpaired node. empty result drops the only node) -/ namespace PSwapNodesInPairs abbrev Input := List Int abbrev Output := List Nat /-! ### Specification helpers -/ /-- Position `i` of `result` holds the input value at the paired index `i ^^^ 1`, or at `i` itself when `i` is the unpaired tail. -/ def SwappedAt (head : List Int) (result : List Nat) (i : Nat) : Prop := result[i]? = ((head[i ^^^ 1]?).orElse fun _ => head[i]?).map Int.toNat /-! ### Validity predicate (V) -/ /-- Valid input: at most 100 nodes, and every node value between 0 and 100. -/ def isValidInput (input : Input) : Bool := input.length ≤ 100 && input.all (fun x => 0 ≤ x && x ≤ 100) /-! ### Ideal specification (P_spec) -/ /-- `result` has the same length as `head`, and every position carries the value from its adjacent-swapped counterpart. -/ def swapPairs_spec (head : Input) (result : Output) : Prop := result.length = head.length ∧ ∀ i, i < head.length → SwappedAt head result i /-! ### Decidable specification (P_check) -/ /-- Check the length clause and every swapped position over the finite index range. -/ def swapPairs_check (head : Input) (result : Output) : Bool := decide (result.length = head.length) && (List.range head.length).all (fun i => decide (result[i]? = ((head[i ^^^ 1]?).orElse fun _ => head[i]?).map Int.toNat)) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem swapPairs_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : swapPairs_check input result ↔ swapPairs_spec input result := by unfold swapPairs_check swapPairs_spec SwappedAt simp only [Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, List.mem_range] /-! ### Main algorithm (impl) -/ /-- Swap every two adjacent nodes by structural recursion on the list, emitting each pair in reverse order and leaving an odd tail element in place. -/ def swapAdjacentNodes : Input → Output | [] => [] | [x] => [x.toNat] | x :: y :: rest => y.toNat :: x.toNat :: swapAdjacentNodes rest /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem swapAdjacentNodes_correct (input : Input) (h : isValidInput input) : swapPairs_spec input (swapAdjacentNodes input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [1, 2, 3, 4] #guard isValidInput [] #guard isValidInput [1] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput [101]) #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]) #guard !(isValidInput [(-1)]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard swapPairs_check [1, 2, 3, 4] [2, 1, 4, 3] #guard swapPairs_check [] [] #guard swapPairs_check [1] [1] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(swapPairs_check [1, 2, 3, 4] [1, 2, 3, 4]) #guard !(swapPairs_check [] [1]) #guard !(swapPairs_check [1] []) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard swapAdjacentNodes [1, 2, 3, 4] == [2, 1, 4, 3] #guard swapAdjacentNodes [] == [] #guard swapAdjacentNodes [1] == [1] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard swapPairs_check [1, 2, 3, 4] (swapAdjacentNodes [1, 2, 3, 4]) #guard swapPairs_check [] (swapAdjacentNodes []) #guard swapPairs_check [1] (swapAdjacentNodes [1]) end PSwapNodesInPairs