import Mathlib /-! # Reverse Integer Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0. Assume the environment does not allow you to store 64-bit integers (signed or unsigned). ## Constraints - -2^31 <= x <= 2^31 - 1 ## Provided examples - `x = 123` → `321` - `x = -123` → `-321` - `x = 120` → `21` ## Synthesized negative examples - invalid input: `x = 2147483648` ([structural] a predicate that admits -2^31 <= x <= 2^31 - 1. one past the stated maximum) - invalid input: `x = -2147483649` ([structural] a predicate that admits -2^31 <= x <= 2^31 - 1. one below the stated minimum) - invalid input: `x = 1000000000000` ([structural] a predicate that admits -2^31 <= x <= 2^31 - 1. an order of magnitude past the ceiling) - `x = 123` → `123` is wrong ([structural] does not require the output to be the reversal of the input. echoes the input unchanged, accepted if the reversal clause is omitted) - `x = -123` → `-320` is wrong ([structural] off-by-one in reversal result. one greater than true reversed value) - `x = 120` → `120` is wrong ([structural] no requirement that the output be x's reversed digits; any in-range integer accepted. x itself is returned, performing no reversal) -/ namespace PReverseInteger abbrev Input := Int abbrev Output := Int /-! ### Specification helpers -/ /-- The sign-preserving reversal of the decimal digits of `x`, as an integer. -/ def digitReversal (x : Int) : Int := let r : Int := Nat.ofDigits 10 (Nat.digits 10 x.natAbs).reverse if x < 0 then -r else r /-- `result` is the decimal digit-reversal of `x` when it fits in signed 32 bits, else 0. -/ def IsCorrectReverseInteger (x result : Int) : Prop := (digitReversal x ∈ Set.Icc (-2^31) (2^31 - 1) → result = digitReversal x) ∧ (digitReversal x ∉ Set.Icc (-2^31) (2^31 - 1) → result = 0) /-! ### Validity predicate (V) -/ /-- Valid input: `x` lies in the signed 32-bit integer range. -/ def isValidInput (input : Input) : Bool := -2^31 ≤ input && input ≤ 2^31 - 1 /-! ### Ideal specification (P_spec) -/ /-- `result` is the sign-preserving decimal reversal of `input` if that reversal is within the signed 32-bit range, and 0 otherwise. -/ def reverseInteger_spec (input : Input) (result : Output) : Prop := IsCorrectReverseInteger input result /-! ### Decidable specification (P_check) -/ /-- Decidable membership of an integer in the signed 32-bit closed interval. -/ instance decMemSigned32 (x : Int) : Decidable (x ∈ Set.Icc (-2^31 : Int) (2^31 - 1)) := inferInstanceAs (Decidable ((-2^31 : Int) ≤ x ∧ x ≤ 2^31 - 1)) /-- Decidability of the full specification relation, unfolding the conjunction of implications. -/ instance decReverseIntegerSpec (input : Input) (result : Output) : Decidable (reverseInteger_spec input result) := inferInstanceAs (Decidable ( (digitReversal input ∈ Set.Icc (-2^31 : Int) (2^31 - 1) → result = digitReversal input) ∧ (digitReversal input ∉ Set.Icc (-2^31 : Int) (2^31 - 1) → result = 0))) /-- Executable checker for `reverseInteger_spec`. -/ def reverseInteger_check (input : Input) (result : Output) : Bool := decide (reverseInteger_spec input result) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem reverseInteger_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : reverseInteger_check input result ↔ reverseInteger_spec input result := by simp [reverseInteger_check] /-! ### Main algorithm (impl) -/ /-- Sign-preserving decimal digit reversal via `digitReversal`, returning 0 when the reversal falls outside the signed 32-bit range. -/ def reverseIntegerWithinRange (input : Input) : Output := let r := digitReversal input if r ∈ Set.Icc (-2^31) (2^31 - 1) then r else 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem reverseIntegerWithinRange_correct (input : Input) (h : isValidInput input) : reverseInteger_spec input (reverseIntegerWithinRange input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput 123 #guard isValidInput (-123) #guard isValidInput 120 /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput 2147483648) #guard !(isValidInput (-2147483649)) #guard !(isValidInput 1000000000000) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard reverseInteger_check 123 321 #guard reverseInteger_check (-123) (-321) #guard reverseInteger_check 120 21 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(reverseInteger_check 123 123) #guard !(reverseInteger_check (-123) (-320)) #guard !(reverseInteger_check 120 120) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard reverseIntegerWithinRange 123 == 321 #guard reverseIntegerWithinRange (-123) == (-321) #guard reverseIntegerWithinRange 120 == 21 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard reverseInteger_check 123 (reverseIntegerWithinRange 123) #guard reverseInteger_check (-123) (reverseIntegerWithinRange (-123)) #guard reverseInteger_check 120 (reverseIntegerWithinRange 120) end PReverseInteger