import Mathlib /-! # Plus One Linked List Given a non-negative integer represented as a linked list of digits, plus one to the integer. The digits are stored such that the most significant digit is at the head of the list. ## Constraints - The number of nodes in the linked list is in the range [1, 100]. - 0 <= Node.val <= 9 - The number represented by the linked list does not contain leading zeros except for the zero itself. ## Provided examples - `head = [1, 2, 3]` → `[1, 2, 4]` - `head = [0]` → `[1]` - `head = [1]` → `[2]` ## Synthesized negative examples - invalid input: `head = []` ([structural] a predicate that admits The number of nodes in the linked list is in the range [1, 100].. empty list where at least one node is required) - invalid input: `head = [-1]` ([structural] a predicate that admits 0 <= Node.val <= 9. negative digit below the allowed floor) - invalid input: `head = [0, 1]` ([structural] a predicate that admits The number represented by the linked list does not contain leading zeros except for the zero itself.. leading zero before a nonzero digit) - `head = [1, 2, 3]` → `[0, 1, 2, 4]` is wrong ([structural] no leading zero restriction stated. zero prepended to the correct value) - `head = [0]` → `[2]` is wrong ([structural] minimality stated as achievability alone. 2 is >0 but not the least successor) - `head = [1]` → `[3]` is wrong ([structural] the increment amount is specified as adding two instead of one. one step above the true value but still a valid digit list) -/ namespace PPlusOneLinkedList abbrev Input := List Int abbrev Output := List Nat /-! ### Specification helpers -/ /-- `l` is a canonical base-10 representation of `n`: every digit is 0..9, there is no leading zero unless `l = [0]`, and the decimal value of the most-significant-first list is `n`. -/ def Represents (l : List Nat) (n : Nat) : Prop := (∀ d ∈ l, d ≤ 9) ∧ (l.head? = some 0 → l = [0]) ∧ Nat.ofDigits 10 l.reverse = n /-- `Represents` for a list of integer digits, where an entry counts as a digit only when `0 ≤ d ≤ 9`. -/ def RepresentsInt (l : List Int) (n : Nat) : Prop := (∀ d ∈ l, 0 ≤ d ∧ d ≤ 9) ∧ (l.head? = some 0 → l = [0]) ∧ Nat.ofDigits 10 (l.map Int.toNat).reverse = n /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 100 integer digits, each between 0 and 9, with no leading zero unless the list is `[0]`. -/ def isValidInput (input : Input) : Bool := decide (1 ≤ input.length) && decide (input.length ≤ 100) && input.all (fun d => decide (0 ≤ d) && decide (d ≤ 9)) && (!(input.head? == some 0) || input == [0]) /-! ### Ideal specification (P_spec) -/ /-- `result` is a canonical decimal representation of the number denoted by `input` plus one, and every canonical representation of that number equals `result`. -/ def plusOne_spec (input : Input) (result : Output) : Prop := (∃ n, RepresentsInt input n ∧ Represents result (n + 1)) ∧ ∀ n r, RepresentsInt input n → Represents r (n + 1) → r = result /-! ### Decidable specification (P_check) -/ /-- Executable form of `plusOne_spec`, using the input's unique decimal denotation. -/ def plusOne_check (input : Input) (result : Output) : Bool := let n := Nat.ofDigits 10 (input.map Int.toNat).reverse input.all (fun d => decide (0 ≤ d) && decide (d ≤ 9)) && (!(input.head? == some 0) || input == [0]) && result.all (fun d => decide (d ≤ 9)) && (!(result.head? == some 0) || result == [0]) && Nat.ofDigits 10 result.reverse == n + 1 theorem root_of_bridges (uniq : ∀ (n : Nat) (a b : List Nat), Represents a (n + 1) → Represents b (n + 1) → a = b) (input : Input) (result : Output) : plusOne_check input result ↔ plusOne_spec input result := by have hu := uniq (Nat.ofDigits 10 (input.map Int.toNat).reverse) simp [plusOne_check, plusOne_spec, RepresentsInt, Represents, List.all_eq_true] at * grind only [] theorem rep_digits (n : Nat) (l : List Nat) (hl : Represents l (n + 1)) : Nat.digits 10 (n + 1) = l.reverse := by rcases hl with ⟨hd, hz, hv⟩ rw [← hv] apply Nat.digits_ofDigits 10 (by decide) · intro d hm have := hd d (List.mem_reverse.mp hm) omega · intro hn rw [List.getLast_reverse] cases l with | nil => simp at hn | cons a t => simp only [List.head_cons] intro ha have he : a :: t = [0] := hz (by simp [ha]) simp [he, Nat.ofDigits] at hv theorem rep_unique (n : Nat) (a b : List Nat) (ha : Represents a (n + 1)) (hb : Represents b (n + 1)) : a = b := by have he := (rep_digits n a ha).symm.trans (rep_digits n b hb) simpa using congrArg List.reverse he /-- On valid input the checker accepts exactly the specified outputs. -/ theorem plusOne_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : plusOne_check input result ↔ plusOne_spec input result := by exact root_of_bridges rep_unique input result /-! ### Main algorithm (impl) -/ /-- Reads the digit list as a natural number, adds one, and expands back to base-10 digits. -/ def plusOneDigits (input : Input) : Output := (Nat.digits 10 (Nat.ofDigits 10 (input.map Int.toNat).reverse + 1)).reverse /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem plusOneDigits_correct (input : Input) (h : isValidInput input) : plusOne_spec input (plusOneDigits input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [1, 2, 3] #guard isValidInput [0] #guard isValidInput [1] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [-1]) #guard !(isValidInput [0, 1]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard plusOne_check [1, 2, 3] [1, 2, 4] #guard plusOne_check [0] [1] #guard plusOne_check [1] [2] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(plusOne_check [1, 2, 3] [0, 1, 2, 4]) #guard !(plusOne_check [0] [2]) #guard !(plusOne_check [1] [3]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard plusOneDigits [1, 2, 3] == [1, 2, 4] #guard plusOneDigits [0] == [1] #guard plusOneDigits [1] == [2] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard plusOne_check [1, 2, 3] (plusOneDigits [1, 2, 3]) #guard plusOne_check [0] (plusOneDigits [0]) #guard plusOne_check [1] (plusOneDigits [1]) end PPlusOneLinkedList