import Mathlib /-! # String To Integer Atoi Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer. The algorithm for myAtoi(string s) is as follows: Whitespace: Ignore any leading whitespace (" "). Signedness: Determine the sign by checking if the next character is '-' or '+', assuming positivity if neither present. Conversion: Read the integer by skipping leading zeros until a non-digit character is encountered or the end of the string is reached. If no digits were read, then the result is 0. Rounding: If the integer is out of the 32-bit signed integer range [-2^31, 2^31 - 1], then round the integer to remain in the range. Specifically, integers less than -2^31 should be rounded to -2^31, and integers greater than 2^31 - 1 should be rounded to 2^31 - 1. Return the integer as the final result. ## Constraints - 0 <= s.length <= 200 - s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'. ## Provided examples - `s = "42"` → `42` - `s = " -042"` → `-42` - `s = "1337c0d3"` → `1337` ## Synthesized negative examples - invalid input: `s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"` ([structural] a predicate that admits 0 <= s.length <= 200. one character past the maximum length; a predicate that forgot the ceiling accepts) - invalid input: `s = "\t42"` ([structural] a predicate that admits s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.. tab is whitespace but not the allowed space; whitespace-tolerant predicate accepts) - invalid input: `s = "٤"` ([structural] a predicate that admits s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.. Unicode digit is not one of 0-9; isdigit() predicate accepts) - `s = "42"` → `-42` is wrong ([structural] signedness default positivity is omitted, so an absent sign is read as negative. digits and range correct; only sign condition dropped) - `s = " -042"` → `42` is wrong ([structural] unattainable does not apply here; signedness is omitted, so the '-' is ignored. reads 42 but fails to apply the minus sign) - `s = "1337c0d3"` → `-1337` is wrong ([structural] signedness omits default positive, assumes negative. Same digits with negative sign; only default sign is wrong.) -/ namespace PStringToIntegerAtoi abbrev Input := String abbrev Output := Int /-! ### Specification helpers -/ /-- `c` is one of the ASCII decimal digits `0` through `9`. -/ def isDecimalDigit (c : Char) : Prop := '0' ≤ c ∧ c ≤ '9' /-- The numeric value of an ASCII decimal digit character. -/ def digitValue (c : Char) : Nat := c.toNat - '0'.toNat /-- The decimal value of a list of ASCII digit characters, most significant first. -/ def digitsValue (ds : List Char) : Nat := Nat.ofDigits (10 : Nat) (ds.map digitValue).reverse /-- `raw` is the integer read from `s`: leading spaces, then an optional sign, then the maximal run of decimal digits (empty run meaning zero), then the rest. -/ def AtoiValue (s : String) (raw : Int) : Prop := ∃ (ws sign ds rest : String), s = ws ++ sign ++ ds ++ rest ∧ (∀ c ∈ ws.toList, c = ' ') ∧ (∀ c ∈ (sign ++ ds ++ rest).toList.head?, c ≠ ' ') ∧ ((sign = "-" ∨ sign = "+") ∨ (sign = "" ∧ ∀ c ∈ (ds ++ rest).toList.head?, c ≠ '-' ∧ c ≠ '+')) ∧ (∀ c ∈ ds.toList, isDecimalDigit c) ∧ (∀ c ∈ rest.toList.head?, ¬ isDecimalDigit c) ∧ raw = (if sign = "-" then -1 else 1 : Int) * (digitsValue ds.toList : Int) /-- `result` is `raw` clamped to the 32-bit signed interval `[-2^31, 2^31 - 1]`. -/ def ClampedTo32 (raw result : Int) : Prop := (raw < -2147483648 ∧ result = -2147483648) ∨ (raw > 2147483647 ∧ result = 2147483647) ∨ (-2147483648 ≤ raw ∧ raw ≤ 2147483647 ∧ result = raw) /-! ### Validity predicate (V) -/ /-- Valid input: at most 200 characters, each an ASCII letter, digit, space, `+`, `-`, or `.`. -/ def isValidInput (input : Input) : Bool := input.length ≤ 200 && input.toList.all (fun c => ('a' ≤ c && c ≤ 'z') || ('A' ≤ c && c ≤ 'Z') || ('0' ≤ c && c ≤ '9') || c == ' ' || c == '+' || c == '-' || c == '.') /-! ### Ideal specification (P_spec) -/ /-- `result` is the clamped value of some reading of `input`, and every reading of `input` clamps to `result`, so the answer is the uniquely determined one. -/ def stringToInt32_spec (input : Input) (result : Output) : Prop := (∃ raw : Int, AtoiValue input raw ∧ ClampedTo32 raw result) ∧ (∀ raw' : Int, AtoiValue input raw' → ClampedTo32 raw' result) /-! ### Decidable specification (P_check) -/ /-- All reading codes for `s`: a leading-block length, one of the three sign strings, and a digit-block length. -/ def allCodes (s : String) : List (Nat × String × Nat) := (List.range (s.length + 1)).flatMap fun i => ["", "+", "-"].flatMap fun sign => (List.range (s.length + 1)).map fun j => (i, sign, j) /-- `(i, sign, j)` is a genuine reading of `s` when the blocks it cuts out of `s` satisfy every decomposition clause of `AtoiValue`; computed as a `Bool`. -/ def validReading (s : String) (code : Nat × String × Nat) : Bool := let i := code.1 let sign := code.2.1 let j := code.2.2 s.toList == s.toList.take i ++ sign.toList ++ (s.toList.drop (i + sign.length)).take j ++ s.toList.drop (i + sign.length + j) && (s.toList.take i).all (fun c => c == ' ') && ((s.toList.drop i).take 1).all (fun c => !(c == ' ')) && (sign == "-" || sign == "+" || (sign == "" && ((s.toList.drop (i + sign.length)).take 1).all (fun c => !(c == '-') && !(c == '+')))) && ((s.toList.drop (i + sign.length)).take j).all (fun c => '0' ≤ c && c ≤ '9') && ((s.toList.drop (i + sign.length + j)).take 1).all (fun c => !('0' ≤ c && c ≤ '9')) /-- The raw integer read by code `(i, sign, j)`: the spec's signed decimal value of the digit block the code selects. -/ def readingValue (s : String) (code : Nat × String × Nat) : Int := (if code.2.1 = "-" then -1 else 1 : Int) * (digitsValue ((s.toList.drop (code.1 + code.2.1.length)).take code.2.2) : Int) /-- Boolean counterpart of `ClampedTo32` for the executable checker. -/ def clampedTo32B (raw result : Int) : Bool := (raw < -2147483648 && result == -2147483648) || (raw > 2147483647 && result == 2147483647) || (-2147483648 ≤ raw && raw ≤ 2147483647 && result == raw) /-- Executable checker for `stringToInt32_spec` over the finite reading codes. -/ def stringToInt32_check (input : Input) (result : Output) : Bool := (allCodes input).any (fun code => validReading input code && clampedTo32B (readingValue input code) result) && (allCodes input).all (fun code => !validReading input code || clampedTo32B (readingValue input code) result) theorem atoi_root (bridge : ∀ s raw, AtoiValue s raw ↔ ∃ code ∈ allCodes s, validReading s code = true ∧ readingValue s code = raw) (input : Input) (result : Output) : stringToInt32_check input result ↔ stringToInt32_spec input result := by simp only [stringToInt32_check, Bool.and_eq_true, List.any_eq_true, List.all_eq_true, Bool.or_eq_true, Bool.not_eq_true', clampedTo32B, beq_iff_eq, decide_eq_true_eq, stringToInt32_spec, ClampedTo32, bridge, and_assoc, or_assoc] constructor · rintro ⟨⟨c, hc, hv, hr⟩, hall⟩ refine ⟨⟨readingValue input c, ⟨c, hc, hv, rfl⟩, hr⟩, ?_⟩ rintro raw ⟨c, hc, hv, rfl⟩ exact (hall c hc).resolve_left (by simp [hv]) · rintro ⟨⟨raw, ⟨c, hc, hv, he⟩, hr⟩, hall⟩ refine ⟨⟨c, hc, hv, he ▸ hr⟩, ?_⟩ intro c hc by_cases hv : validReading input c = true · exact Or.inr (hall _ ⟨c, hc, hv, rfl⟩) · exact Or.inl (by simpa using hv) theorem head_take_one (l : List Char) (p : Char → Prop) : (∀ c ∈ l.take 1, p c) ↔ (∀ c ∈ l.head?, p c) := by cases l <;> simp theorem validReading_prop (s : String) (i j : Nat) (sign : String) : validReading s (i, sign, j) = true ↔ s.toList = s.toList.take i ++ sign.toList ++ (s.toList.drop (i + sign.length)).take j ++ s.toList.drop (i + sign.length + j) ∧ (∀ c ∈ s.toList.take i, c = ' ') ∧ (∀ c ∈ (s.toList.drop i).head?, c ≠ ' ') ∧ ((sign = "-" ∨ sign = "+") ∨ (sign = "" ∧ ∀ c ∈ (s.toList.drop (i + sign.length)).head?, c ≠ '-' ∧ c ≠ '+')) ∧ (∀ c ∈ (s.toList.drop (i + sign.length)).take j, isDecimalDigit c) ∧ (∀ c ∈ (s.toList.drop (i + sign.length + j)).head?, ¬ isDecimalDigit c) := by simp [validReading, Bool.and_eq_true, Bool.or_eq_true, List.all_eq_true, head_take_one, isDecimalDigit, and_assoc, or_assoc] grind theorem codes_mem (s : String) (i j : Nat) (sign : String) : (i, sign, j) ∈ allCodes s ↔ i ≤ s.length ∧ (sign = "" ∨ sign = "+" ∨ sign = "-") ∧ j ≤ s.length := by simp [allCodes, List.mem_flatMap, List.mem_map, Nat.lt_succ_iff] grind only [] theorem atoi_sound (s : String) (i j : Nat) (sign : String) (hi : i ≤ s.length) (hv : validReading s (i, sign, j) = true) : AtoiValue s (readingValue s (i, sign, j)) := by rcases (validReading_prop s i j sign).mp hv with ⟨he, hw, hh, hs, hd, hr⟩ have hlen : (s.toList.take i).length = i := by simp only [List.length_take] exact Nat.min_eq_left hi have hdrop : s.toList.drop i = sign.toList ++ (s.toList.drop (i + sign.length)).take j ++ s.toList.drop (i + sign.length + j) := by have hh := congrArg (List.drop (s.toList.take i).length) he simp only [List.append_assoc, List.drop_append_length] at hh simpa only [hlen, List.append_assoc] using hh have hdrop2 : s.toList.drop (i + sign.length) = (s.toList.drop (i + sign.length)).take j ++ s.toList.drop (i + sign.length + j) := by simp [← List.drop_drop] refine ⟨String.ofList (s.toList.take i), sign, String.ofList ((s.toList.drop (i + sign.length)).take j), String.ofList (s.toList.drop (i + sign.length + j)), ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ · apply String.toList_injective simpa only [String.toList_append, String.toList_ofList] using he · simpa only [String.toList_ofList] using hw · simpa only [String.toList_append, String.toList_ofList, ← hdrop] using hh · simpa only [String.toList_append, String.toList_ofList, ← hdrop2] using hs · simpa only [String.toList_ofList] using hd · simpa only [String.toList_ofList] using hr · simp only [readingValue, String.toList_ofList] theorem atoi_complete (s : String) (raw : Int) (hv : AtoiValue s raw) : ∃ code ∈ allCodes s, validReading s code = true ∧ readingValue s code = raw := by rcases hv with ⟨ws, sign, ds, rest, he, hw, hh, hs, hd, hr, hraw⟩ have hel : s.toList = ws.toList ++ sign.toList ++ ds.toList ++ rest.toList := by simpa only [String.toList_append] using congrArg String.toList he have hlen : s.length = ws.length + sign.length + ds.length + rest.length := by simpa only [List.length_append, String.length_toList] using congrArg List.length hel have hws : s.toList.take ws.length = ws.toList := by rw [hel] simp only [List.append_assoc] exact List.take_append_length have htail : s.toList.drop ws.length = sign.toList ++ ds.toList ++ rest.toList := by rw [hel] simp only [List.append_assoc] exact List.drop_append_length have hds : s.toList.drop (ws.length + sign.length) = ds.toList ++ rest.toList := by rw [← List.drop_drop, htail] simp only [List.append_assoc] exact List.drop_append_length have hdigits : (s.toList.drop (ws.length + sign.length)).take ds.length = ds.toList := by rw [hds] exact List.take_append_length have hrest : s.toList.drop (ws.length + sign.length + ds.length) = rest.toList := by rw [← List.drop_drop, hds] exact List.drop_append_length refine ⟨(ws.length, sign, ds.length), ?_, ?_, ?_⟩ · apply (codes_mem s _ _ _).mpr refine ⟨by omega, ?_, by omega⟩ rcases hs with (hm | hp) | ⟨hz, _⟩ · exact Or.inr (Or.inr hm) · exact Or.inr (Or.inl hp) · exact Or.inl hz · apply (validReading_prop s _ _ _).mpr rw [hws, htail, hdigits, hrest, hds] simpa only [String.toList_append] using (show s.toList = ws.toList ++ sign.toList ++ ds.toList ++ rest.toList ∧ (∀ c ∈ ws.toList, c = ' ') ∧ (∀ c ∈ (sign ++ ds ++ rest).toList.head?, c ≠ ' ') ∧ ((sign = "-" ∨ sign = "+") ∨ (sign = "" ∧ ∀ c ∈ (ds ++ rest).toList.head?, c ≠ '-' ∧ c ≠ '+')) ∧ (∀ c ∈ ds.toList, isDecimalDigit c) ∧ (∀ c ∈ rest.toList.head?, ¬isDecimalDigit c) from ⟨hel, hw, hh, hs, hd, hr⟩) · simpa only [readingValue, hdigits] using hraw.symm theorem atoi_bridge (s : String) (raw : Int) : AtoiValue s raw ↔ ∃ code ∈ allCodes s, validReading s code = true ∧ readingValue s code = raw := by constructor · exact atoi_complete s raw · rintro ⟨⟨i, sign, j⟩, hc, hv, rfl⟩ exact atoi_sound s i j sign ((codes_mem s i j sign).mp hc).1 hv /-- On valid input the checker accepts exactly the specified outputs. -/ theorem stringToInt32_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : stringToInt32_check input result ↔ stringToInt32_spec input result := by exact atoi_root atoi_bridge input result /-! ### Implementation helpers -/ /-- Skips the leading ASCII space characters of `cs`. -/ def skipSpaces : List Char → List Char | [] => [] | c :: cs => if c == ' ' then skipSpaces cs else c :: cs /-- Collects the maximal prefix of decimal digit characters from `cs`. -/ def scanDigits : List Char → List Char | [] => [] | c :: cs => if '0' ≤ c && c ≤ '9' then c :: scanDigits cs else [] /-- Clamps `raw` to the 32-bit signed integer interval. -/ def clamp32 (raw : Int) : Int := if raw < -2147483648 then -2147483648 else if 2147483647 < raw then 2147483647 else raw /-! ### Main algorithm (impl) -/ /-- Reads the integer by a single left-to-right scan, then clamps it to 32 bits. -/ def myAtoi (input : Input) : Output := let cs := skipSpaces input.toList let (sign, ds) := match cs with | '-' :: rest => ((-1 : Int), scanDigits rest) | '+' :: rest => ((1 : Int), scanDigits rest) | _ => ((1 : Int), scanDigits cs) clamp32 (sign * (digitsValue ds : Int)) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem myAtoi_correct (input : Input) (h : isValidInput input) : stringToInt32_spec input (myAtoi input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "42" #guard isValidInput " -042" #guard isValidInput "1337c0d3" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") #guard !(isValidInput "\t42") #guard !(isValidInput "٤") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard stringToInt32_check "42" 42 #guard stringToInt32_check " -042" (-42) #guard stringToInt32_check "1337c0d3" 1337 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(stringToInt32_check "42" (-42)) #guard !(stringToInt32_check " -042" 42) #guard !(stringToInt32_check "1337c0d3" (-1337)) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard myAtoi "42" == 42 #guard myAtoi " -042" == (-42) #guard myAtoi "1337c0d3" == 1337 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard stringToInt32_check "42" (myAtoi "42") #guard stringToInt32_check " -042" (myAtoi " -042") #guard stringToInt32_check "1337c0d3" (myAtoi "1337c0d3") end PStringToIntegerAtoi