import Mathlib /-! # Strobogrammatic Number Iii Given two strings low and high that represent two integers low and high where low <= high, return the number of strobogrammatic numbers in the range [low, high]. A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). ## Constraints - 1 <= low.length, high.length <= 15 - low and high consist of only digits. - low <= high - low and high do not contain any leading zeros except for zero itself. ## Provided examples - `low = "50", high = "100"` → `3` - `low = "0", high = "0"` → `1` - `low = "6", high = "9"` → `1` ## Synthesized negative examples - invalid input: `low = "0", high = "1111111111111111"` ([structural] a predicate that admits 1 <= low.length, high.length <= 15. high is 16 digits; checking only low's length accepts it) - invalid input: `low = "-1", high = "0"` ([structural] a predicate that admits low and high consist of only digits.. minus sign is not a digit; int() parses low as -1) - invalid input: `low = "10", high = "9"` ([structural] a predicate that admits low <= high. lexicographic comparison accepts 10 <= 9) - `low = "50", high = "100"` → `4` is wrong ([structural] range check uses n <= high + 1 while stating inclusive high. includes 101 in addition to 69, 88, and 96) - `low = "0", high = "0"` → `2` is wrong ([structural] low and high are counted separately even when equal. equal endpoints counted twice; true count is one) - `low = "6", high = "9"` → `3` is wrong ([structural] treats any number composed of digits in {0,1,6,8,9} as strobogrammatic; 6 and 9 are not invariant alone. counts 6,8,9 but only 8 is strobogrammatic) -/ namespace PStrobogrammaticNumberIii abbrev Input := (String) × (String) abbrev Output := Nat /-! ### Specification helpers -/ /-- The digit `d` rotated 180 degrees, if it reads as a digit at all. -/ def rotDigit (d : ℕ) : Option ℕ := match d with | 0 => some 0 | 1 => some 1 | 6 => some 9 | 8 => some 8 | 9 => some 6 | _ => none /-- `n` reads the same upside down: rotating each decimal digit and reversing gives back its digits, with no digit outside {0, 1, 6, 8, 9}. -/ def IsStrobogrammatic (n : ℕ) : Prop := (Nat.digits 10 n).mapM rotDigit = some ((Nat.digits 10 n).reverse) /-- The natural number a digit string denotes. -/ def numVal (s : String) : ℕ := s.toNat! /-- `s` has no leading zero unless `s` is "0" itself. -/ def noLeadingZero (s : String) : Bool := s.length = 1 || s.front ≠ '0' /-! ### Validity predicate (V) -/ /-- Valid input: low and high are digit strings of length 1 to 15, free of leading zeros except "0" itself, with low numerically at most high. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 15 && 1 ≤ input.2.length && input.2.length ≤ 15 && input.1.toList.all Char.isDigit && input.2.toList.all Char.isDigit && noLeadingZero input.1 && noLeadingZero input.2 && numVal input.1 ≤ numVal input.2 /-! ### Ideal specification (P_spec) -/ /-- `result` is the size of a finite collection of natural numbers whose members are exactly the strobogrammatic numbers in the inclusive range from the integer represented by low to the integer represented by high. -/ def countStrobogrammatic_spec (input : Input) (result : Output) : Prop := ∃ s : Finset ℕ, s.card = result ∧ ∀ n : ℕ, n ∈ s ↔ IsStrobogrammatic n ∧ numVal input.1 ≤ n ∧ n ≤ numVal input.2 /-! ### Decidable specification (P_check) -/ /-- Decide `IsStrobogrammatic n`: it unfolds to an equality of `Option (List ℕ)`, which Lean decides on its own. -/ instance instDecIsStrobogrammatic (n : ℕ) : Decidable (IsStrobogrammatic n) := inferInstanceAs (Decidable ((Nat.digits 10 n).mapM rotDigit = some ((Nat.digits 10 n).reverse))) /-- Decide the unfolded specification: a finset satisfying the membership condition is uniquely the strobogrammatic numbers in the inclusive range `[numVal input.1, numVal input.2]`, so the existential is equivalent to the card of that filtered `Finset.Icc` being `result`, which computes. The two conjunction shapes differ only in order and association, which `tauto` closes after `simp` unfolds the filter membership. -/ instance instDecCountStrobogrammaticSpec (input : Input) (result : Output) : Decidable (∃ s : Finset ℕ, s.card = result ∧ ∀ n : ℕ, n ∈ s ↔ IsStrobogrammatic n ∧ numVal input.1 ≤ n ∧ n ≤ numVal input.2) := decidable_of_iff (((Finset.Icc (numVal input.1) (numVal input.2)).filter (fun n => IsStrobogrammatic n)).card = result) (by constructor · intro h refine ⟨_, h, fun n => ?_⟩ simp only [Finset.mem_filter, Finset.mem_Icc] tauto · rintro ⟨s, hcard, hs⟩ have : s = (Finset.Icc (numVal input.1) (numVal input.2)).filter (fun n => IsStrobogrammatic n) := by ext n simp only [Finset.mem_filter, Finset.mem_Icc, hs n] tauto subst this exact hcard) /-- Executable checker obtained mechanically from the specification. -/ def countStrobogrammatic_check (input : Input) (result : Output) : Bool := @decide (countStrobogrammatic_spec input result) (by unfold countStrobogrammatic_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem countStrobogrammatic_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : countStrobogrammatic_check input result ↔ countStrobogrammatic_spec input result := by simp [countStrobogrammatic_check] /-! ### Implementation helpers -/ /-- All strobogrammatic digit lists of length exactly `m`, most significant digit first; `outer` forbids a leading zero in the outermost digit pair. -/ def strobogrammaticNumbersOfLength : (m : ℕ) → (outer : Bool) → List (List ℕ) | 0, _ => [[]] | 1, _ => [[0], [1], [8]] | m + 2, outer => (strobogrammaticNumbersOfLength m false).flatMap fun inner => (if outer then [1, 6, 8, 9] else [0, 1, 6, 8, 9]).flatMap fun d => match rotDigit d with | some r => [d :: (inner ++ [r])] | none => [] termination_by m _ => m decreasing_by omega /-! ### Main algorithm (impl) -/ /-- Count the strobogrammatic numbers in `[low, high]` by generating every canonical strobogrammatic digit list of each length in range and counting those whose numeric value lies in the interval. -/ def countStrobogrammaticInRange (input : Input) : Output := let lo := numVal input.1 let hi := numVal input.2 let candidates := ((List.range (input.2.length + 1)).filter fun m => decide (input.1.length ≤ m)).flatMap fun m => (strobogrammaticNumbersOfLength m true).map fun ds => Nat.ofDigits 10 ds.reverse candidates.countP fun n => decide (lo ≤ n ∧ n ≤ hi) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem countStrobogrammaticInRange_correct (input : Input) (h : isValidInput input) : countStrobogrammatic_spec input (countStrobogrammaticInRange input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("50", "100") #guard isValidInput ("0", "0") #guard isValidInput ("6", "9") /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("0", "1111111111111111")) #guard !(isValidInput ("-1", "0")) #guard !(isValidInput ("10", "9")) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard countStrobogrammatic_check ("50", "100") 3 #guard countStrobogrammatic_check ("0", "0") 1 #guard countStrobogrammatic_check ("6", "9") 1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(countStrobogrammatic_check ("50", "100") 4) #guard !(countStrobogrammatic_check ("0", "0") 2) #guard !(countStrobogrammatic_check ("6", "9") 3) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard countStrobogrammaticInRange ("50", "100") == 3 #guard countStrobogrammaticInRange ("0", "0") == 1 #guard countStrobogrammaticInRange ("6", "9") == 1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard countStrobogrammatic_check ("50", "100") (countStrobogrammaticInRange ("50", "100")) #guard countStrobogrammatic_check ("0", "0") (countStrobogrammaticInRange ("0", "0")) #guard countStrobogrammatic_check ("6", "9") (countStrobogrammaticInRange ("6", "9")) end PStrobogrammaticNumberIii