import Mathlib /-! # Palindrome Number Given an integer x, return true if x is a palindrome, and false otherwise. ## Constraints - -2^31 <= x <= 2^31 - 1 ## Provided examples - `x = 121` → `true` - `x = -121` → `false` - `x = 10` → `false` ## Synthesized negative examples - invalid input: `x = -2147483649` ([structural] a predicate that admits -2^31 <= x <= 2^31 - 1. one below the stated minimum) - invalid input: `x = 2147483648` ([structural] a predicate that admits -2^31 <= x <= 2^31 - 1. one above the stated maximum) - invalid input: `x = 100000000000` ([structural] a predicate that admits -2^31 <= x <= 2^31 - 1. an order of magnitude past the ceiling) - `x = 121` → `false` is wrong ([structural] no requirement to return true for palindromes. constant false satisfies a one-way spec) - `x = -121` → `true` is wrong ([structural] ignores the negative sign when testing digit palindrome. abs(-121) is 121, a palindrome) - `x = 10` → `true` is wrong ([structural] the specification does not require 'false' for non-palindromes. true passes a spec with no false branch) -/ namespace PPalindromeNumber abbrev Input := Int abbrev Output := Bool /-! ### Specification helpers -/ /-- `x` is a palindrome integer: non-negative, and its decimal digits read the same backwards. -/ def IsPalindrome (x : Int) : Prop := 0 ≤ x ∧ (Nat.digits 10 x.toNat).Palindrome /-! ### Validity predicate (V) -/ /-- Valid input: a 32-bit signed integer, `-2^31 ≤ x ≤ 2^31 - 1`. -/ def isValidInput (input : Input) : Bool := -2^31 ≤ input && input ≤ 2^31 - 1 /-! ### Ideal specification (P_spec) -/ /-- `result` is true exactly when `input` is a palindrome integer. -/ def isPalindrome_spec (input : Input) (result : Output) : Prop := result ↔ IsPalindrome input /-! ### Decidable specification (P_check) -/ /-- Executable checker for `isPalindrome_spec`: `result` equals the Bool form of `IsPalindrome input`. -/ def isPalindrome_check (input : Input) (result : Output) : Bool := result == (decide (0 ≤ input) && ((Nat.digits 10 input.toNat).reverse == Nat.digits 10 input.toNat)) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem isPalindrome_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : isPalindrome_check input result ↔ isPalindrome_spec input result := by unfold isPalindrome_check isPalindrome_spec IsPalindrome simp only [beq_iff_eq] rw [Bool.eq_iff_iff] simp only [Bool.and_eq_true, decide_eq_true_eq, beq_iff_eq, List.Palindrome.iff_reverse_eq] /-! ### Main algorithm (impl) -/ /-- Palindrome test by digit reversal, extracted from the frozen checker by fixing its expected result to `true`. -/ def isPalindromeNumber (input : Input) : Output := isPalindrome_check input true /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem isPalindromeNumber_correct (input : Input) (h : isValidInput input) : isPalindrome_spec input (isPalindromeNumber input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput 121 #guard isValidInput (-121) #guard isValidInput 10 /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (-2147483649)) #guard !(isValidInput 2147483648) #guard !(isValidInput 100000000000) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard isPalindrome_check 121 true #guard isPalindrome_check (-121) false #guard isPalindrome_check 10 false /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(isPalindrome_check 121 false) #guard !(isPalindrome_check (-121) true) #guard !(isPalindrome_check 10 true) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard isPalindromeNumber 121 == true #guard isPalindromeNumber (-121) == false #guard isPalindromeNumber 10 == false /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard isPalindrome_check 121 (isPalindromeNumber 121) #guard isPalindrome_check (-121) (isPalindromeNumber (-121)) #guard isPalindrome_check 10 (isPalindromeNumber 10) end PPalindromeNumber