import Mathlib /-! # Add Binary Given two binary strings a and b, return their sum as a binary string. ## Constraints - 1 <= a.length, b.length <= 10^4 - a and b consist only of '0' or '1' characters. - Each string does not contain leading zeros except for the zero itself. ## Provided examples - `a = "11", b = "1"` → `"100"` - `a = "1010", b = "1011"` → `"10101"` - `a = "0", b = "0"` → `"0"` ## Synthesized negative examples - invalid input: `a = "", b = "1"` ([structural] a predicate that admits 1 <= a.length, b.length <= 10^4. empty a below the length floor) - invalid input: `a = "2", b = "1"` ([structural] a predicate that admits a and b consist only of '0' or '1' characters.. a contains 2 outside the binary alphabet) - invalid input: `a = "01", b = "1"` ([structural] a predicate that admits Each string does not contain leading zeros except for the zero itself.. leading zero in a) - `a = "11", b = "1"` → `"101"` is wrong ([structural] result may be one greater than the true sum. binary 5 is one more than 4) - `a = "1010", b = "1011"` → `"010101"` is wrong ([structural] leading zeros on output are not forbidden. same numeric value with a leading zero) - `a = "0", b = "0"` → `"1"` is wrong ([structural] binary sum computed as sum plus one instead of the exact sum. value is one greater than the true sum but still a binary string) -/ namespace PAddBinary abbrev Input := (String) × (String) abbrev Output := String /-! ### Specification helpers -/ /-- The natural number denoted by the binary digit string `s`, read most-significant digit first. -/ def BinaryValue (s : String) : Nat := s.toList.foldl (fun n c => 2 * n + if c = '1' then 1 else 0) 0 /-- `s` is a canonical binary numeral: nonempty, only '0'/'1', and without a leading zero unless it is exactly "0". -/ def IsCanonicalBinary (s : String) : Prop := s ≠ "" ∧ (∀ c ∈ s.toList, c = '0' ∨ c = '1') ∧ (s = "0" ∨ s.toList.head? ≠ some '0') /-! ### Validity predicate (V) -/ /-- Valid input: both strings have length from 1 to 10^4, use only '0'/'1', and have no leading zero unless equal to "0". -/ 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 (fun c => c = '0' || c = '1') && input.2.toList.all (fun c => c = '0' || c = '1') && (input.1 = "0" || input.1.toList.head? ≠ some '0') && (input.2 = "0" || input.2.toList.head? ≠ some '0') /-! ### Ideal specification (P_spec) -/ /-- `result` denotes the sum of the values denoted by the two input strings and is a canonical binary numeral. -/ def addBinary_spec (input : Input) (result : Output) : Prop := BinaryValue result = BinaryValue input.1 + BinaryValue input.2 ∧ IsCanonicalBinary result /-! ### Decidable specification (P_check) -/ /-- Decides canonicality by unfolding it into decidable string emptiness, bounded list membership, and head-character checks. -/ instance decIsCanonicalBinary (s : String) : Decidable (IsCanonicalBinary s) := inferInstanceAs (Decidable (s ≠ "" ∧ (∀ c ∈ s.toList, c = '0' ∨ c = '1') ∧ (s = "0" ∨ s.toList.head? ≠ some '0'))) /-- Executable checker obtained mechanically from the specification. -/ def addBinary_check (input : Input) (result : Output) : Bool := @decide (addBinary_spec input result) (by unfold addBinary_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem addBinary_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : addBinary_check input result ↔ addBinary_spec input result := by simp [addBinary_check] /-! ### Implementation helpers -/ /-- The Nat bit value denoted by one digit character, reading anything but '1' as 0. -/ def digitToNat (c : Char) : Nat := if c = '1' then 1 else 0 /-- The digit character denoting a computed bit Nat, reading anything but 1 as '0'. -/ def natToBitChar (n : Nat) : Char := if n = 1 then '1' else '0' /-- Adds two reversed digit lists with an incoming carry, returning the reversed result digits. -/ def addRev (xs ys : List Char) (carry : Nat) : List Char := match xs, ys with | [], [] => if carry = 0 then [] else [natToBitChar carry] | x :: xs', [] => let s := digitToNat x + carry natToBitChar (s % 2) :: addRev xs' [] (s / 2) | [], y :: ys' => let s := digitToNat y + carry natToBitChar (s % 2) :: addRev [] ys' (s / 2) | x :: xs', y :: ys' => let s := digitToNat x + digitToNat y + carry natToBitChar (s % 2) :: addRev xs' ys' (s / 2) termination_by xs.length + ys.length /-! ### Main algorithm (impl) -/ /-- Binary addition by a single least-significant-digit-first carry pass over the reversed digit lists. -/ def sumBinaryStrings (input : Input) : Output := String.mk ((addRev input.1.toList.reverse input.2.toList.reverse 0).reverse) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem sumBinaryStrings_correct (input : Input) (h : isValidInput input) : addBinary_spec input (sumBinaryStrings input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("11", "1") #guard isValidInput ("1010", "1011") #guard isValidInput ("0", "0") /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("", "1")) #guard !(isValidInput ("2", "1")) #guard !(isValidInput ("01", "1")) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard addBinary_check ("11", "1") "100" #guard addBinary_check ("1010", "1011") "10101" #guard addBinary_check ("0", "0") "0" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(addBinary_check ("11", "1") "101") #guard !(addBinary_check ("1010", "1011") "010101") #guard !(addBinary_check ("0", "0") "1") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard sumBinaryStrings ("11", "1") == "100" #guard sumBinaryStrings ("1010", "1011") == "10101" #guard sumBinaryStrings ("0", "0") == "0" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard addBinary_check ("11", "1") (sumBinaryStrings ("11", "1")) #guard addBinary_check ("1010", "1011") (sumBinaryStrings ("1010", "1011")) #guard addBinary_check ("0", "0") (sumBinaryStrings ("0", "0")) end PAddBinary