import Mathlib /-! # Add Two Numbers You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. ## Constraints - The number of nodes in each linked list is in the range [1, 100]. - 0 <= Node.val <= 9 - It is guaranteed that the list represents a number that does not have leading zeros. ## Provided examples - `l1 = [2, 4, 3], l2 = [5, 6, 4]` → `[7, 0, 8]` - `l1 = [0], l2 = [0]` → `[0]` - `l1 = [9, 9, 9, 9, 9, 9, 9], l2 = [9, 9, 9, 9]` → `[8, 9, 9, 9, 0, 0, 0, 1]` ## Synthesized negative examples - invalid input: `l1 = [], l2 = [0]` ([structural] a predicate that admits The number of nodes in each linked list is in the range [1, 100].. empty l1; below the one-node minimum) - invalid input: `l1 = [-1], l2 = [0]` ([structural] a predicate that admits 0 <= Node.val <= 9. negative digit; lower bound not checked) - invalid input: `l1 = [1, 0], l2 = [0]` ([structural] a predicate that admits It is guaranteed that the list represents a number that does not have leading zeros.. leading zero at tail; head-only check accepts) - `l1 = [2, 4, 3], l2 = [5, 6, 4]` → `[7, 10, 7]` is wrong ([structural] the output digit is not required to be a single digit. sum is correct but a node holds 10) - `l1 = [0], l2 = [0]` → `[0, 0]` is wrong ([structural] no-leading-zero rule not applied to result. Still sums to zero but adds a leading zero.) - `l1 = [9, 9, 9, 9, 9, 9, 9], l2 = [9, 9, 9, 9]` → `[18, 8, 9, 9, 0, 0, 0, 1]` is wrong ([structural] node values are not constrained to 0..9. the leading digit 18 is outside the digit range while the sum is correct) -/ namespace PAddTwoNumbers abbrev Input := (List Int) × (List Int) abbrev Output := List Nat /-! ### Specification helpers -/ /-- `l` is a least-significant-first decimal numeral: every entry is a digit 0-9, and the most significant digit is nonzero unless `l` is exactly `[0]`. -/ def IsDecimalNumeral (l : List Nat) : Prop := (∀ d ∈ l, d ≤ 9) ∧ (l = [0] ∨ ∃ h : l ≠ [], l.getLast h ≠ 0) /-- The natural number denoted by a least-significant-first list of decimal digits. -/ def NatDecimalValue (l : List Nat) : Nat := Nat.ofDigits 10 l /-- The natural number denoted by a least-significant-first input digit list, whose entries are digits by the validity predicate. -/ def IntDecimalValue (l : List Int) : Nat := Nat.ofDigits 10 (l.map Int.toNat) /-! ### Validity predicate (V) -/ /-- Valid input: both lists have between 1 and 100 entries, every entry is a digit 0-9, and neither list has a leading zero unless it is exactly `[0]`. -/ def isValidInput (input : Input) : Bool := decide (1 ≤ input.1.length ∧ input.1.length ≤ 100) && decide (1 ≤ input.2.length ∧ input.2.length ≤ 100) && input.1.all (fun d => decide (0 ≤ d ∧ d ≤ 9)) && input.2.all (fun d => decide (0 ≤ d ∧ d ≤ 9)) && ((input.1 == [0]) || (input.1.getLast? != some 0)) && ((input.2 == [0]) || (input.2.getLast? != some 0)) /-! ### Ideal specification (P_spec) -/ /-- `result` is a decimal numeral denoting the sum of the two numbers the input lists denote. -/ def addTwoNumbers_spec (input : Input) (result : Output) : Prop := IsDecimalNumeral result ∧ NatDecimalValue result = IntDecimalValue input.1 + IntDecimalValue input.2 /-! ### Decidable specification (P_check) -/ /-- Executable form of `IsDecimalNumeral`: every entry is at most 9, and the list is `[0]` or is nonempty with a nonzero last entry. -/ def isDecimalNumeral (l : List Nat) : Bool := l.all (fun d => decide (d ≤ 9)) && ((l == [0]) || (decide (l ≠ []) && l.getLast? != some 0)) /-- Executable checker for `addTwoNumbers_spec`: `result` is a decimal numeral denoting the sum of the two input numbers. -/ def addTwoNumbers_check (input : Input) (result : Output) : Bool := isDecimalNumeral result && NatDecimalValue result == IntDecimalValue input.1 + IntDecimalValue input.2 /-- On valid input the checker accepts exactly the specified outputs. -/ theorem addTwoNumbers_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : addTwoNumbers_check input result ↔ addTwoNumbers_spec input result := by by_cases hr : result = [] · subst result simp [addTwoNumbers_check, addTwoNumbers_spec, isDecimalNumeral, IsDecimalNumeral] · simp [addTwoNumbers_check, addTwoNumbers_spec, isDecimalNumeral, IsDecimalNumeral, hr, List.getLast?_eq_getLast_of_ne_nil hr] /-! ### Implementation helpers -/ /-- Adds two least-significant-first digit lists with an incoming carry, returning the sum's digits in the same order. -/ def addDigitLists (l1 l2 : List Int) (carry : Nat) : List Nat := match l1, l2 with | [], [] => if carry = 0 then [] else [carry] | d :: t, [] => let s := d.toNat + carry s % 10 :: addDigitLists t [] (s / 10) | [], d :: t => let s := d.toNat + carry s % 10 :: addDigitLists [] t (s / 10) | d1 :: t1, d2 :: t2 => let s := d1.toNat + d2.toNat + carry s % 10 :: addDigitLists t1 t2 (s / 10) termination_by l1.length + l2.length decreasing_by all_goals simp_wf all_goals omega /-! ### Main algorithm (impl) -/ /-- Adds the two input numbers by a simultaneous digit-by-digit pass with carry over both lists, least significant digit first. -/ def addTwoNumbersImpl (input : Input) : Output := addDigitLists input.1 input.2 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem addTwoNumbersImpl_correct (input : Input) (h : isValidInput input) : addTwoNumbers_spec input (addTwoNumbersImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([2, 4, 3], [5, 6, 4]) #guard isValidInput ([0], [0]) #guard isValidInput ([9, 9, 9, 9, 9, 9, 9], [9, 9, 9, 9]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], [0])) #guard !(isValidInput ([(-1)], [0])) #guard !(isValidInput ([1, 0], [0])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard addTwoNumbers_check ([2, 4, 3], [5, 6, 4]) [7, 0, 8] #guard addTwoNumbers_check ([0], [0]) [0] #guard addTwoNumbers_check ([9, 9, 9, 9, 9, 9, 9], [9, 9, 9, 9]) [8, 9, 9, 9, 0, 0, 0, 1] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(addTwoNumbers_check ([2, 4, 3], [5, 6, 4]) [7, 10, 7]) #guard !(addTwoNumbers_check ([0], [0]) [0, 0]) #guard !(addTwoNumbers_check ([9, 9, 9, 9, 9, 9, 9], [9, 9, 9, 9]) [18, 8, 9, 9, 0, 0, 0, 1]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard addTwoNumbersImpl ([2, 4, 3], [5, 6, 4]) == [7, 0, 8] #guard addTwoNumbersImpl ([0], [0]) == [0] #guard addTwoNumbersImpl ([9, 9, 9, 9, 9, 9, 9], [9, 9, 9, 9]) == [8, 9, 9, 9, 0, 0, 0, 1] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard addTwoNumbers_check ([2, 4, 3], [5, 6, 4]) (addTwoNumbersImpl ([2, 4, 3], [5, 6, 4])) #guard addTwoNumbers_check ([0], [0]) (addTwoNumbersImpl ([0], [0])) #guard addTwoNumbers_check ([9, 9, 9, 9, 9, 9, 9], [9, 9, 9, 9]) (addTwoNumbersImpl ([9, 9, 9, 9, 9, 9, 9], [9, 9, 9, 9])) end PAddTwoNumbers