import Mathlib /-! # Valid Number Given a string s, return whether s is a valid number. For example, all the following are valid numbers: "2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789", while the following are not valid numbers: "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53". Formally, a valid number is defined using one of the following definitions: An integer number followed by an optional exponent. A decimal number followed by an optional exponent. An integer number is defined with an optional sign '-' or '+' followed by digits. A decimal number is defined with an optional sign '-' or '+' followed by one of the following definitions: Digits followed by a dot '.'. Digits followed by a dot '.' followed by digits. A dot '.' followed by digits. An exponent is defined with an exponent notation 'e' or 'E' followed by an integer number. The digits are defined as one or more digits. ## Constraints - 1 <= s.length <= 20 - s consists of only English letters (both uppercase and lowercase), digits (0-9), plus '+', minus '-', or dot '.'. ## Provided examples - `s = "0"` → `true` - `s = "e"` → `false` - `s = "."` → `false` ## Synthesized negative examples - invalid input: `s = ""` ([structural] a predicate that admits 1 <= s.length <= 20. empty string; a predicate checking only the upper bound accepts it.) - invalid input: `s = " "` ([structural] a predicate that admits s consists of only English letters (both uppercase and lowercase), digits (0-9), plus '+', minus '-', or dot '.'.. space is outside the allowed characters; a predicate that trims before checking accepts it.) - invalid input: `s = "aaaaaaaaaaaaaaaaaaaaa"` ([structural] a predicate that admits 1 <= s.length <= 20. 21 characters, one past the maximum; a predicate checking only the lower bound accepts it.) - `s = "0"` → `false` is wrong ([structural] the valid-number definition omits the integer-number branch, so bare integers are rejected. spec accepts only decimal-with-dot; 0 has no dot) - `s = "e"` → `true` is wrong ([structural] exponent allowed without trailing integer. e is a lone exponent marker) - `s = "."` → `true` is wrong ([structural] digits defined as one or more, but bare dot accepted if digits allowed zero. digit count relaxed to zero and bare dot accepted) -/ namespace PValidNumber abbrev Input := String abbrev Output := Bool /-! ### Specification helpers -/ /-- The pattern matching one digit character. -/ def digitPattern : RegularExpression Char := .plus (.char '0') (.plus (.char '1') (.plus (.char '2') (.plus (.char '3') (.plus (.char '4') (.plus (.char '5') (.plus (.char '6') (.plus (.char '7') (.plus (.char '8') (.char '9'))))))))) /-- The pattern matching one or more digits. -/ def digitsPattern : RegularExpression Char := .comp digitPattern digitPattern.star /-- The pattern matching an optional `+` or `-` sign. -/ def signPattern : RegularExpression Char := .plus .epsilon (.plus (.char '+') (.char '-')) /-- The pattern matching an integer number: an optional sign then one or more digits. -/ def integerPattern : RegularExpression Char := .comp signPattern digitsPattern /-- The pattern matching a decimal number: an optional sign then digits-dot, digits-dot-digits, or dot-digits. -/ def decimalPattern : RegularExpression Char := .comp signPattern (.plus (.comp digitsPattern (.char '.')) (.plus (.comp digitsPattern (.comp (.char '.') digitsPattern)) (.comp (.char '.') digitsPattern))) /-- The pattern matching an exponent: `e` or `E` then an integer number. -/ def exponentPattern : RegularExpression Char := .comp (.plus (.char 'e') (.char 'E')) integerPattern /-- The pattern matching the problem's valid numbers: an integer or a decimal, optionally followed by an exponent. -/ def validNumberPattern : RegularExpression Char := .comp (.plus integerPattern decimalPattern) (.plus .epsilon exponentPattern) /-- `s` belongs to the language of valid numbers the problem defines. -/ def IsValidNumber (s : String) : Prop := s.toList ∈ validNumberPattern.matches' /-! ### Validity predicate (V) -/ /-- Valid input: a string of 1 to 20 characters, each an English letter, a digit, `+`, `-`, or `.`. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 20 && input.toList.all (fun c => ('a' ≤ c && c ≤ 'z') || ('A' ≤ c && c ≤ 'Z') || ('0' ≤ c && c ≤ '9') || c = '+' || c = '-' || c = '.') /-! ### Ideal specification (P_spec) -/ /-- `result` is true exactly when `input` matches the valid-number grammar. -/ def isValidNumber_spec (input : Input) (result : Output) : Prop := result ↔ IsValidNumber input /-! ### Decidable specification (P_check) -/ /-- Decides `IsValidNumber s` by unfolding it to membership of `s.toList` in `validNumberPattern.matches'`, which is decidable since `Char` has decidable equality and regular-expression language membership is decidable. -/ instance decidableIsValidNumber (s : String) : Decidable (IsValidNumber s) := inferInstanceAs (Decidable (s.toList ∈ validNumberPattern.matches')) /-- Executable checker obtained mechanically from the specification. -/ def isValidNumber_check (input : Input) (result : Output) : Bool := @decide (isValidNumber_spec input result) (by unfold isValidNumber_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem isValidNumber_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : isValidNumber_check input result ↔ isValidNumber_spec input result := by simp [isValidNumber_check] /-! ### Main algorithm (impl) -/ /-- Validity by delegating to the frozen checker with the result fixed to `true`, so the returned boolean is exactly the decided validity of the input. -/ def checkValidNumber (input : Input) : Output := isValidNumber_check input true /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem checkValidNumber_correct (input : Input) (h : isValidInput input) : isValidNumber_spec input (checkValidNumber input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "0" #guard isValidInput "e" #guard isValidInput "." /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "") #guard !(isValidInput " ") #guard !(isValidInput "aaaaaaaaaaaaaaaaaaaaa") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard isValidNumber_check "0" true #guard isValidNumber_check "e" false #guard isValidNumber_check "." false /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(isValidNumber_check "0" false) #guard !(isValidNumber_check "e" true) #guard !(isValidNumber_check "." true) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard checkValidNumber "0" == true #guard checkValidNumber "e" == false #guard checkValidNumber "." == false /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard isValidNumber_check "0" (checkValidNumber "0") #guard isValidNumber_check "e" (checkValidNumber "e") #guard isValidNumber_check "." (checkValidNumber ".") end PValidNumber