import Mathlib /-! # Multiply Strings Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. Note: You must not use any built-in BigInteger library or convert the inputs to integer directly. ## Constraints - 1 <= num1.length, num2.length <= 200 - num1 and num2 consist of digits only. - Both num1 and num2 do not contain any leading zero, except the number 0 itself. ## Provided examples - `num1 = "2", num2 = "3"` → `"6"` - `num1 = "123", num2 = "456"` → `"56088"` - `num1 = "1", num2 = "1"` → `"1"` ## Synthesized negative examples - invalid input: `num1 = "", num2 = "1"` ([structural] a predicate that admits 1 <= num1.length, num2.length <= 200. empty string below minimum length) - invalid input: `num1 = "1", num2 = "a"` ([structural] a predicate that admits num1 and num2 consist of digits only.. letter outside digit alphabet) - invalid input: `num1 = "01", num2 = "1"` ([structural] a predicate that admits Both num1 and num2 do not contain any leading zero, except the number 0 itself.. leading zero; a predicate converting to int accepts this) - `num1 = "2", num2 = "3"` → `"5"` is wrong ([structural] multiplication stated as addition. 2+3 is one less than the product, but is a valid digit string.) - `num1 = "123", num2 = "456"` → `"056088"` is wrong ([structural] canonical representation is not required. leading zero accepted if no canonical form) - `num1 = "1", num2 = "1"` → `"0"` is wrong ([structural] specification permits product result one less than the true value. true product 1, returns 0) -/ namespace PMultiplyStrings abbrev Input := (String) × (String) abbrev Output := String /-! ### Specification helpers -/ /-- The natural number a character string denotes in decimal. -/ def stringValue (s : String) : Nat := Nat.ofDigits 10 (s.toList.map (fun c => c.toNat - '0'.toNat)).reverse /-- `s` is a non-empty string of decimal digits whose decimal value is `n`. -/ def StringDenotes (s : String) (n : Nat) : Prop := s ≠ "" ∧ (∀ c ∈ s.toList, '0' ≤ c ∧ c ≤ '9') ∧ stringValue s = n /-- `s` has no leading zero unless it is exactly `"0"`. -/ def isCanonical (s : String) : Prop := s.toList.head? = some '0' → s = "0" /-! ### Validity predicate (V) -/ /-- Valid input: two digit strings of length 1 to 200 with no leading zeros unless `"0"`. -/ def isValidInput (input : Input) : Bool := (1 ≤ input.1.length && input.1.length ≤ 200) && (1 ≤ input.2.length && input.2.length ≤ 200) && input.1.toList.all (fun c => '0' ≤ c && c ≤ '9') && input.2.toList.all (fun c => '0' ≤ c && c ≤ '9') && (input.1 == "0" || input.1.toList.head? != some '0') && (input.2 == "0" || input.2.toList.head? != some '0') /-! ### Ideal specification (P_spec) -/ /-- `result` is a decimal string denoting the product of the numbers denoted by the two inputs, spelled canonically with no leading zero unless it is `"0"`. -/ def multiplyStrings_spec (input : Input) (result : Output) : Prop := StringDenotes result (stringValue input.1 * stringValue input.2) ∧ isCanonical result /-! ### Decidable specification (P_check) -/ /-- `s` contains only decimal digit characters. -/ def digitsOnlyOk (s : String) : Bool := s.toList.all (fun c => '0' ≤ c && c ≤ '9') /-- `s` has no leading zero unless it is exactly `"0"`. -/ def canonicalOk (s : String) : Bool := (s.toList.head? != some '0') || (s == "0") /-- Executable checker for `multiplyStrings_spec`. -/ def multiplyStrings_check (input : Input) (result : Output) : Bool := (result != "") && digitsOnlyOk result && (stringValue result == stringValue input.1 * stringValue input.2) && canonicalOk result /-- On valid input the checker accepts exactly the specified outputs. -/ theorem multiplyStrings_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : multiplyStrings_check input result ↔ multiplyStrings_spec input result := by simp [multiplyStrings_check, multiplyStrings_spec, StringDenotes, digitsOnlyOk, canonicalOk, isCanonical] tauto /-! ### Implementation helpers -/ /-- The canonical decimal spelling of a natural number, `"0"` for zero. -/ def natToDecimalString (n : Nat) : String := if n = 0 then "0" else String.mk (Nat.toDigits 10 n) /-! ### Main algorithm (impl) -/ /-- Product of two decimal strings: parse each with `stringValue`, multiply the `Nat`s, render canonically. -/ def stringMultiply (input : Input) : Output := natToDecimalString (stringValue input.1 * stringValue input.2) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem stringMultiply_correct (input : Input) (h : isValidInput input) : multiplyStrings_spec input (stringMultiply input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("2", "3") #guard isValidInput ("123", "456") #guard isValidInput ("1", "1") /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("", "1")) #guard !(isValidInput ("1", "a")) #guard !(isValidInput ("01", "1")) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard multiplyStrings_check ("2", "3") "6" #guard multiplyStrings_check ("123", "456") "56088" #guard multiplyStrings_check ("1", "1") "1" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(multiplyStrings_check ("2", "3") "5") #guard !(multiplyStrings_check ("123", "456") "056088") #guard !(multiplyStrings_check ("1", "1") "0") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard stringMultiply ("2", "3") == "6" #guard stringMultiply ("123", "456") == "56088" #guard stringMultiply ("1", "1") == "1" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard multiplyStrings_check ("2", "3") (stringMultiply ("2", "3")) #guard multiplyStrings_check ("123", "456") (stringMultiply ("123", "456")) #guard multiplyStrings_check ("1", "1") (stringMultiply ("1", "1")) end PMultiplyStrings