import Mathlib /-! # Add Strings Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string. You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly. ## Constraints - 1 <= num1.length, num2.length <= 10^4 - num1 and num2 consist of only digits. - num1 and num2 don't have any leading zeros except for the zero itself. ## Provided examples - `num1 = "11", num2 = "123"` → `"134"` - `num1 = "456", num2 = "77"` → `"533"` - `num1 = "0", num2 = "0"` → `"0"` ## Synthesized negative examples - invalid input: `num1 = "", num2 = "0"` ([structural] a predicate that admits 1 <= num1.length, num2.length <= 10^4. empty num1; a predicate checking only num2 length accepts it) - invalid input: `num1 = "1a", num2 = "0"` ([structural] a predicate that admits num1 and num2 consist of only digits.. non-digit letter; a predicate checking only length and leading zeros accepts it) - invalid input: `num1 = "01", num2 = "0"` ([structural] a predicate that admits num1 and num2 don't have any leading zeros except for the zero itself.. leading zero; a predicate checking only length and digits accepts it) - `num1 = "11", num2 = "123"` → `"133"` is wrong ([structural] the output is not required to equal the true sum exactly; an off-by-one approximation is accepted. one less than true sum; exactness not required) - `num1 = "456", num2 = "77"` → `"1000010101"` is wrong ([structural] output is not required to be in base 10; binary representation accepted. 1000010101 is 533 in binary, not decimal) - `num1 = "0", num2 = "0"` → `"1"` is wrong ([structural] the sum is specified with an off-by-one error, returning one more than the true sum. 0+0=0, but output is 1) -/ namespace PAddStrings abbrev Input := (String) × (String) abbrev Output := String /-! ### Specification helpers -/ /-- `s` is a decimal numeral (digits only, leading zeros allowed) whose place-value interpretation equals `n`. -/ def StringDenotes (s : String) (n : Nat) : Prop := (∀ c ∈ s.toList, c.isDigit) ∧ Nat.ofDigits 10 ((s.toList.map fun c => c.toNat - '0'.toNat).reverse) = n /-- `s` is the canonical decimal spelling of a natural number: nonempty, all digits, and no leading zero unless `s = "0"`. -/ def IsCanonicalDecimal (s : String) : Prop := s ≠ "" ∧ (∀ c ∈ s.toList, c.isDigit) ∧ (s.toList.head? = some '0' → s = "0") /-! ### Validity predicate (V) -/ /-- Valid input: both strings are nonempty digit strings of length at most 10^4 with no leading zero except the string "0" itself. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 10 ^ 4 && 1 ≤ input.2.length && input.2.length ≤ 10 ^ 4 && input.1.toList.all Char.isDigit && input.2.toList.all Char.isDigit && (input.1 == "0" || input.1.toList.head? != some '0') && (input.2 == "0" || input.2.toList.head? != some '0') /-! ### Ideal specification (P_spec) -/ /-- `result` is the canonical decimal string denoting the sum of the natural numbers denoted by `input.1` and `input.2`. -/ def addStrings_spec (input : Input) (result : Output) : Prop := (∀ n1 n2 : Nat, StringDenotes input.1 n1 → StringDenotes input.2 n2 → StringDenotes result (n1 + n2)) ∧ IsCanonicalDecimal result /-! ### Decidable specification (P_check) -/ /-- Executable checker obtained mechanically from the specification. -/ def addStrings_check (input : Input) (result : Output) : Bool := let digitsOf : String → List Nat := fun s => s.toList.map fun c => c.toNat - '0'.toNat input.1.toList.all Char.isDigit && input.2.toList.all Char.isDigit && result.toList.all Char.isDigit && result != "" && (result == "0" || result.toList.head? != some '0') && Nat.ofDigits 10 (digitsOf result).reverse == Nat.ofDigits 10 (digitsOf input.1).reverse + Nat.ofDigits 10 (digitsOf input.2).reverse theorem addStrings_valid_digits (input : Input) (h : isValidInput input) : (∀ c ∈ input.1.toList, c.isDigit) ∧ (∀ c ∈ input.2.toList, c.isDigit) := by unfold isValidInput at h simp only [Bool.and_eq_true, List.all_eq_true, decide_eq_true_eq, Bool.or_eq_true, beq_iff_eq, bne_iff_ne, ne_eq] at h constructor <;> tauto /-- On valid input the checker accepts exactly the specified outputs. -/ theorem addStrings_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : addStrings_check input result ↔ addStrings_spec input result := by obtain ⟨hd1, hd2⟩ := addStrings_valid_digits input h unfold addStrings_check addStrings_spec StringDenotes IsCanonicalDecimal simp constructor · rintro ⟨⟨⟨⟨⟨-, -⟩, hrd⟩, hne⟩, hhead⟩, hsum⟩ refine ⟨?_, hne, hrd, ?_⟩ · intro n1 n2 _ hn1 _ hn2 subst hn1 subst hn2 exact ⟨hrd, hsum⟩ · intro hh rcases hhead with h0 | hne0 · exact h0 · exact absurd hh hne0 · rintro ⟨hall, hne, hrd, hhead⟩ obtain ⟨-, hval⟩ := hall _ _ hd1 rfl hd2 rfl refine ⟨⟨⟨⟨⟨hd1, hd2⟩, hrd⟩, hne⟩, ?_⟩, hval⟩ by_cases hh : (String.toList result).head? = some '0' · exact Or.inl (hhead hh) · exact Or.inr hh /-! ### Implementation helpers -/ /-- Adds two decimal digits and an incoming carry, returning the result digit and the outgoing carry. -/ def addOneColumn (d1 d2 carry : Nat) : Nat × Nat := let s := d1 + d2 + carry (s % 10, s / 10) /-- Adds two little-endian digit lists with an incoming carry, returning the little-endian digit list of the sum. -/ def addDigitLists : List Nat → List Nat → Nat → List Nat | [], [], 0 => [] | [], [], c => [c] | d1 :: r1, [], c => let (s, c') := addOneColumn d1 0 c s :: addDigitLists r1 [] c' | [], d2 :: r2, c => let (s, c') := addOneColumn 0 d2 c s :: addDigitLists [] r2 c' | d1 :: r1, d2 :: r2, c => let (s, c') := addOneColumn d1 d2 c s :: addDigitLists r1 r2 c' termination_by ds1 ds2 _c => ds1.length + ds2.length decreasing_by all_goals simp only [List.length_cons, List.length_nil, Nat.zero_add, Nat.add_zero] omega /-! ### Main algorithm (impl) -/ /-- Right-to-left column addition with carry over the reversed digit lists, linear in the longer input. -/ def stringSum (input : Input) : Output := let digitsOf : String → List Nat := fun s => (s.toList.map fun c => c.toNat - '0'.toNat).reverse let sumDigits := addDigitLists (digitsOf input.1) (digitsOf input.2) 0 if sumDigits.isEmpty then "0" else String.mk ((sumDigits.map fun d => Char.ofNat ('0'.toNat + d)).reverse) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem stringSum_correct (input : Input) (h : isValidInput input) : addStrings_spec input (stringSum input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("11", "123") #guard isValidInput ("456", "77") #guard isValidInput ("0", "0") /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("", "0")) #guard !(isValidInput ("1a", "0")) #guard !(isValidInput ("01", "0")) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard addStrings_check ("11", "123") "134" #guard addStrings_check ("456", "77") "533" #guard addStrings_check ("0", "0") "0" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(addStrings_check ("11", "123") "133") #guard !(addStrings_check ("456", "77") "1000010101") #guard !(addStrings_check ("0", "0") "1") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard stringSum ("11", "123") == "134" #guard stringSum ("456", "77") == "533" #guard stringSum ("0", "0") == "0" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard addStrings_check ("11", "123") (stringSum ("11", "123")) #guard addStrings_check ("456", "77") (stringSum ("456", "77")) #guard addStrings_check ("0", "0") (stringSum ("0", "0")) end PAddStrings