import Mathlib /-! # Strobogrammatic Number Given a string num which represents an integer, return true if num is a strobogrammatic number. A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). ## Constraints - 1 <= num.length <= 50 - num consists of only digits. - num does not contain any leading zeros except for zero itself. ## Provided examples - `num = "69"` → `true` - `num = "88"` → `true` - `num = "962"` → `false` ## Synthesized negative examples - invalid input: `num = ""` ([structural] a predicate that admits 1 <= num.length <= 50. empty string violates the minimum length) - invalid input: `num = "111111111111111111111111111111111111111111111111111"` ([structural] a predicate that admits 1 <= num.length <= 50. one more than the maximum length) - invalid input: `num = "-69"` ([structural] a predicate that admits num consists of only digits.. a minus sign is not a digit; a predicate parsing with int() accepts it) - `num = "69"` → `false` is wrong ([structural] spec's 180° mapping only includes 0,1,8, omitting 6↔9. false returned since 69 lacks self-rotating digits only.) - `num = "88"` → `false` is wrong ([structural] Specification accepts a constant false without verifying the rotation property.. False passes even though 88 is strobogrammatic.) - `num = "962"` → `true` is wrong ([structural] specification does not require the answer to depend on the input; constant true is accepted. true is trivially returned without checking strobogrammatic property) -/ namespace PStrobogrammaticNumber abbrev Input := String abbrev Output := Bool /-! ### Specification helpers -/ /-- The 180-degree rotation of a digit, when it has one. -/ def rotateDigit (c : Char) : Option Char := match c with | '0' => some '0' | '1' => some '1' | '6' => some '9' | '8' => some '8' | '9' => some '6' | _ => none /-- `s` reads the same rotated 180 degrees: at every complementary pair of positions `i, j` with `i + j + 1 = s.length`, the digit at `i` rotates to the digit at `j` under 0↔0, 1↔1, 6↔9, 8↔8, 9↔6. -/ def IsStrobogrammatic (s : String) : Prop := ∀ i j : Fin s.toList.length, i.val + j.val + 1 = s.length → rotateDigit (s.toList.get i) = some (s.toList.get j) /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 50 digit characters, with no leading zero unless the string is exactly "0". -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 50 && input.toList.all (fun c => '0' ≤ c && c ≤ '9') && !(2 ≤ input.length && input.toList.head? == some '0') /-! ### Ideal specification (P_spec) -/ /-- `result` is true exactly when `num` is strobogrammatic. -/ def isStrobogrammatic_spec (input : Input) (result : Output) : Prop := result ↔ IsStrobogrammatic input /-! ### Decidable specification (P_check) -/ /-- Decides `IsStrobogrammatic s`: unfolding exposes two bounded quantifiers over `Fin s.toList.length` whose body (a Nat equality implying an `Option Char` equality) is decided by Lean's own instances; `Fin`'s `Fintype` instance decides the quantifiers. -/ instance decIsStrobogrammatic (s : String) : Decidable (IsStrobogrammatic s) := inferInstanceAs (Decidable (∀ i j : Fin s.toList.length, i.val + j.val + 1 = s.length → rotateDigit (s.toList.get i) = some (s.toList.get j))) /-- Executable checker obtained mechanically from the specification. -/ def isStrobogrammatic_check (input : Input) (result : Output) : Bool := @decide (isStrobogrammatic_spec input result) (by unfold isStrobogrammatic_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem isStrobogrammatic_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : isStrobogrammatic_check input result ↔ isStrobogrammatic_spec input result := by simp [isStrobogrammatic_check] /-! ### Implementation helpers -/ /-- Compares the complementary digit pair at positions `lo` and `hi` of `cs` and recurses inward, returning false at the first pair failing the rotation map. -/ def checkSymmetric (cs : List Char) (lo hi : Nat) : Bool := if h : hi < lo then true else match cs[lo]?, cs[hi]? with | some a, some b => (rotateDigit a == some b) && checkSymmetric cs (lo + 1) (hi - 1) | _, _ => false termination_by hi + 1 - lo decreasing_by simp_wf omega /-! ### Main algorithm (impl) -/ /-- Linear two-pointer scan from the outside inward, checking each complementary digit pair against the 180-degree rotation map. -/ def isStrobogrammaticNumber (num : Input) : Bool := let cs := num.toList checkSymmetric cs 0 (cs.length - 1) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem isStrobogrammaticNumber_correct (input : Input) (h : isValidInput input) : isStrobogrammatic_spec input (isStrobogrammaticNumber input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "69" #guard isValidInput "88" #guard isValidInput "962" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "") #guard !(isValidInput "111111111111111111111111111111111111111111111111111") #guard !(isValidInput "-69") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard isStrobogrammatic_check "69" true #guard isStrobogrammatic_check "88" true #guard isStrobogrammatic_check "962" false /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(isStrobogrammatic_check "69" false) #guard !(isStrobogrammatic_check "88" false) #guard !(isStrobogrammatic_check "962" true) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard isStrobogrammaticNumber "69" == true #guard isStrobogrammaticNumber "88" == true #guard isStrobogrammaticNumber "962" == false /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard isStrobogrammatic_check "69" (isStrobogrammaticNumber "69") #guard isStrobogrammatic_check "88" (isStrobogrammaticNumber "88") #guard isStrobogrammatic_check "962" (isStrobogrammaticNumber "962") end PStrobogrammaticNumber