import Mathlib /-! # Plus One You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The representation has no leading zeros, except that zero itself is represented by [0]. Increment the large integer by one and return the resulting array of digits. ## Constraints - 1 <= digits.length <= 100 - 0 <= digits[i] <= 9 - digits has no leading zeros unless digits == [0]. ## Provided examples - `digits = [1, 2, 3]` → `[1, 2, 4]` - `digits = [4, 3, 2, 1]` → `[4, 3, 2, 2]` - `digits = [9]` → `[1, 0]` ## Synthesized negative examples - invalid input: `digits = []` ([structural] a predicate that admits 1 <= digits.length <= 100. empty where at least one digit is required) - invalid input: `digits = [-1]` ([structural] a predicate that admits 0 <= digits[i] <= 9. one below the allowed digit range) - invalid input: `digits = [10]` ([structural] a predicate that admits 0 <= digits[i] <= 9. one above the allowed digit range) - `digits = [1, 2, 3]` → `[1, 2, 5]` is wrong ([structural] unattainable not applicable; off_by_one accepts adding two. one greater than true value) - `digits = [4, 3, 2, 1]` → `[4, 3, 2, 3]` is wrong ([structural] output may be any value larger than the input, not necessarily exactly one more. One extra in the last digit passes a spec that only demands an increase.) - `digits = [9]` → `[1, 1]` is wrong ([structural] increment amount is off by one, adding two instead. 11 is one more than true 10, valid digits, no leading zero) -/ namespace PPlusOne abbrev Input := List Int abbrev Output := List Nat /-! ### Specification helpers -/ /-- `decimalValue ds` is the positional decimal value of `ds` read most significant digit first. -/ def decimalValue (ds : List Int) : Int := ds.foldl (fun acc d => 10 * acc + d) 0 /-- `Represents ds n` means `ds` is a nonempty decimal digit sequence with entries in `0..9`, no leading zero, and positional decimal value `n`. -/ def Represents (ds : List Int) (n : Nat) : Prop := ds ≠ [] ∧ (∀ d ∈ ds, 0 ≤ d ∧ d ≤ 9) ∧ ds.head? ≠ some 0 ∧ decimalValue ds = n /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 100 digits, each between 0 and 9 inclusive, with no leading zero except for the single digit zero. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 100 && input.all (fun d => 0 ≤ d && d ≤ 9) && (input.length == 1 || input.head? ≠ some 0) /-! ### Ideal specification (P_spec) -/ /-- `result` is the unique no-leading-zero decimal digit list whose value is one more than the decimal value of `input`. -/ def plusOne_spec (input : Input) (result : Output) : Prop := Represents (result.map Int.ofNat) ((decimalValue input).toNat + 1) ∧ ∀ l : List Int, Represents l ((decimalValue input).toNat + 1) → l = result.map Int.ofNat /-! ### Decidable specification (P_check) -/ /-- The length-`k` decimal digit list of `n`, most significant digit first, padded with leading zeros when `n` has fewer than `k` digits. -/ def digitsOfLen (n : Nat) (k : Nat) : List Int := (List.range k).map fun i => Int.ofNat ((n / 10 ^ (k - 1 - i)) % 10) /-- `Represents` is decidable: unfold the definition and let instance resolution handle the conjunction, the bounded list membership quantifier, and the equalities. -/ instance representsDecidable (ds : List Int) (n : Nat) : Decidable (Represents ds n) := by unfold Represents infer_instance /-- Executable checker for `plusOne_spec`: candidates for the universal are the length-`k` digit lists of the target value for `k ≤ 101`. -/ def plusOne_check (input : Input) (result : Output) : Bool := let m := (decimalValue input).toNat + 1 decide (Represents (result.map Int.ofNat) m) && (List.range 102).all fun k => decide (Represents (digitsOfLen m k) m → digitsOfLen m k = result.map Int.ofNat) theorem decimalFold_pos (xs : List Int) (z : Int) (hz : 0 < z) (hxs : ∀ x ∈ xs, 0 ≤ x) : 0 < xs.foldl (fun acc d => 10 * acc + d) z := by induction xs generalizing z with | nil => simpa using hz | cons x xs ih => simp only [List.foldl_cons] apply ih · have hx : 0 ≤ x := hxs x (by simp) omega · intro y hy exact hxs y (by simp [hy]) theorem decimalValue_pos {ds : List Int} (hne : ds ≠ []) (hdigits : ∀ d ∈ ds, 0 ≤ d ∧ d ≤ 9) (hhead : ds.head? ≠ some 0) : 0 < decimalValue ds := by cases ds with | nil => contradiction | cons d ds => have hd : 0 ≤ d := (hdigits d (by simp)).1 have hdnz : d ≠ 0 := by intro h apply hhead simp [h] have hdpos : 0 < d := by omega simp only [decimalValue, List.foldl_cons] norm_num apply decimalFold_pos ds d hdpos intro x hx exact (hdigits x (by simp [hx])).1 theorem decimalValue_append_singleton (xs : List Int) (d : Int) : decimalValue (xs ++ [d]) = 10 * decimalValue xs + d := by simp [decimalValue, List.foldl_append] theorem normalized_decimalValue_injective : ∀ a : List Int, (∀ d ∈ a, 0 ≤ d ∧ d ≤ 9) → (a = [] ∨ a.head? ≠ some 0) → ∀ b : List Int, (∀ d ∈ b, 0 ≤ d ∧ d ≤ 9) → (b = [] ∨ b.head? ≠ some 0) → decimalValue a = decimalValue b → a = b := by intro a induction a using List.reverseRecOn with | nil => intro haDigits haNorm b hbDigits hbNorm hval by_cases hbEmpty : b = [] · exact hbEmpty.symm · have hbHead : b.head? ≠ some 0 := hbNorm.resolve_left hbEmpty have hbPos : 0 < decimalValue b := decimalValue_pos hbEmpty hbDigits hbHead have hz : decimalValue b = 0 := by simpa [decimalValue] using hval.symm omega | append_singleton a d ih => intro haDigits haNorm b hbDigits hbNorm hval rcases b.eq_nil_or_concat' with hbEmpty | ⟨bs, e, rfl⟩ · subst b have haNe : a ++ [d] ≠ [] := by simp have haHead : (a ++ [d]).head? ≠ some 0 := haNorm.resolve_left haNe have haPos : 0 < decimalValue (a ++ [d]) := decimalValue_pos haNe haDigits haHead have hz : decimalValue (a ++ [d]) = 0 := by simpa [decimalValue] using hval omega · have hd0 : 0 ≤ d := (haDigits d (by simp)).1 have hd9 : d ≤ 9 := (haDigits d (by simp)).2 have he0 : 0 ≤ e := (hbDigits e (by simp)).1 have he9 : e ≤ 9 := (hbDigits e (by simp)).2 rw [decimalValue_append_singleton, decimalValue_append_singleton] at hval have hp : decimalValue a = decimalValue bs := by omega have hde : d = e := by omega have haPrefixDigits : ∀ x ∈ a, 0 ≤ x ∧ x ≤ 9 := by intro x hx exact haDigits x (by simp [hx]) have hbPrefixDigits : ∀ x ∈ bs, 0 ≤ x ∧ x ≤ 9 := by intro x hx exact hbDigits x (by simp [hx]) have haPrefixNorm : a = [] ∨ a.head? ≠ some 0 := by by_cases haEmpty : a = [] · exact Or.inl haEmpty · right have hwhole : (a ++ [d]).head? ≠ some 0 := haNorm.resolve_left (by simp) rw [List.head?_append_of_ne_nil a haEmpty] at hwhole exact hwhole have hbPrefixNorm : bs = [] ∨ bs.head? ≠ some 0 := by by_cases hbEmpty : bs = [] · exact Or.inl hbEmpty · right have hwhole : (bs ++ [e]).head? ≠ some 0 := hbNorm.resolve_left (by simp) rw [List.head?_append_of_ne_nil bs hbEmpty] at hwhole exact hwhole have hab : a = bs := ih haPrefixDigits haPrefixNorm bs hbPrefixDigits hbPrefixNorm hp subst bs subst e rfl theorem represents_unique {a b : List Int} {n : Nat} (ha : Represents a n) (hb : Represents b n) : a = b := by apply normalized_decimalValue_injective a ha.2.1 (Or.inr ha.2.2.1) b hb.2.1 (Or.inr hb.2.2.1) exact ha.2.2.2.trans hb.2.2.2.symm /-- 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 simp only [plusOne_check, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, plusOne_spec] constructor · rintro ⟨hr, _⟩ exact ⟨hr, fun l hl => represents_unique hl hr⟩ · rintro ⟨hr, hu⟩ exact ⟨hr, fun k _ => hu _⟩ /-! ### Implementation helpers -/ /-- Increment the reversed digit list: 9 emits 0 and carries on, the first other digit absorbs the carry, and an empty list means the carry survived every digit. -/ def addOneRev : List Int → List Nat | [] => [1] | d :: ds => if d = 9 then 0 :: addOneRev ds else (d + 1).toNat :: ds.map Int.toNat /-! ### Main algorithm (impl) -/ /-- Increment by reversing to least-significant-first, propagating a carry through the digits, and reversing back. -/ def incrementDigits (digits : Input) : Output := (addOneRev digits.reverse).reverse /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem incrementDigits_correct (input : Input) (h : isValidInput input) : plusOne_spec input (incrementDigits input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [1, 2, 3] #guard isValidInput [4, 3, 2, 1] #guard isValidInput [9] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [(-1)]) #guard !(isValidInput [10]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard plusOne_check [1, 2, 3] [1, 2, 4] #guard plusOne_check [4, 3, 2, 1] [4, 3, 2, 2] #guard plusOne_check [9] [1, 0] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(plusOne_check [1, 2, 3] [1, 2, 5]) #guard !(plusOne_check [4, 3, 2, 1] [4, 3, 2, 3]) #guard !(plusOne_check [9] [1, 1]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard incrementDigits [1, 2, 3] == [1, 2, 4] #guard incrementDigits [4, 3, 2, 1] == [4, 3, 2, 2] #guard incrementDigits [9] == [1, 0] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard plusOne_check [1, 2, 3] (incrementDigits [1, 2, 3]) #guard plusOne_check [4, 3, 2, 1] (incrementDigits [4, 3, 2, 1]) #guard plusOne_check [9] (incrementDigits [9]) end PPlusOne