import Mathlib /-! # Strobogrammatic Number Ii Given an integer n, return all the strobogrammatic numbers that are of length n. You may return the answer in any order. A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). ## Constraints - 1 <= n <= 14 ## Provided examples - `n = 2` → `["11", "69", "88", "96"]` - `n = 1` → `["0", "1", "8"]` - `n = 3` → `["101", "808", "609", "906", "111", "818", "619", "916", "181", "888", "689", "986"]` ## Synthesized negative examples - invalid input: `n = 0` ([structural] a predicate that admits 1 <= n <= 14. zero is below the stated minimum length) - invalid input: `n = 15` ([structural] a predicate that admits 1 <= n <= 14. one past the stated maximum) - invalid input: `n = 100` ([structural] a predicate that admits 1 <= n <= 14. far past the ceiling; a shape case rather than an edge) - `n = 2` → `["00", "11", "69", "88", "96"]` is wrong ([structural] leading zero is not forbidden. only misses the no-leading-zero condition) - `n = 1` → `["0", "1", "8", "11"]` is wrong ([structural] entries are not required to have length n. 11 is valid strobogrammatic but length 2) - `n = 3` → `["11", "69", "88", "96"]` is wrong ([structural] n is read as n-1, so length-two numbers are accepted. lists length 2 instead of 3) -/ namespace PStrobogrammaticNumberIi abbrev Input := Nat abbrev Output := List String /-! ### Specification helpers -/ /-- The 180-degree rotation image of a digit character, or `none` if it has none. -/ def rotateChar (c : Char) : Option Char := match c with | '0' => some '0' | '1' => some '1' | '6' => some '9' | '8' => some '8' | '9' => some '6' | _ => none /-- `s` is a strobogrammatic number of length `n`: `n` characters, no leading zero unless `n = 1`, and equal to its own 180-degree rotation. -/ def IsStrobogrammaticNumber (s : String) (n : Nat) : Prop := s.toList.length = n ∧ (n ≠ 1 → s.toList.head? ≠ some '0') ∧ (List.mapM rotateChar s.toList.reverse : Option (List Char)) = some s.toList /-! ### Validity predicate (V) -/ /-- Valid input: a length between 1 and 14 inclusive. -/ def isValidInput (input : Input) : Bool := 1 ≤ input && input ≤ 14 /-! ### Ideal specification (P_spec) -/ /-- `result` has no repeated entries, contains only strobogrammatic numbers of length `input`, and contains every such number. -/ def strobogrammaticNumbers_spec (input : Input) (result : Output) : Prop := (result.Nodup ∧ ∀ s ∈ result, IsStrobogrammaticNumber s input) ∧ ∀ s : String, IsStrobogrammaticNumber s input → s ∈ result /-! ### Decidable specification (P_check) -/ /-- The five digit characters that have a 180-degree rotation image. -/ def stroboDigits : List Char := ['0', '1', '6', '8', '9'] /-- The length-`n` string over `stroboDigits` whose little-endian base-5 code is `k`. -/ def decodeCandidate (n k : Nat) : String := String.ofList ((List.range n).map fun i => stroboDigits.getD ((k / 5 ^ i) % 5) '0') /-- `IsStrobogrammaticNumber s n` is decidable: its clauses are decidable equalities and implications. -/ instance decIsStrobogrammaticNumber (s : String) (n : Nat) : Decidable (IsStrobogrammaticNumber s n) := inferInstanceAs (Decidable (s.toList.length = n ∧ (n ≠ 1 → s.toList.head? ≠ some '0') ∧ (List.mapM rotateChar s.toList.reverse : Option (List Char)) = some s.toList)) /-- Executable form of `strobogrammaticNumbers_spec`, truncating `∀ s : String` to the `5 ^ input` codes. -/ def strobogrammaticNumbers_check (input : Input) (result : Output) : Bool := decide ((result.Nodup ∧ ∀ s ∈ result, IsStrobogrammaticNumber s input) ∧ ∀ k : Fin (5 ^ input), IsStrobogrammaticNumber (decodeCandidate input k.val) input → decodeCandidate input k.val ∈ result) theorem wx_root (complete : ∀ n s, IsStrobogrammaticNumber s n → ∃ k : Fin (5 ^ n), decodeCandidate n k.val = s) (input : Input) (result : Output) : strobogrammaticNumbers_check input result ↔ strobogrammaticNumbers_spec input result := by simp only [strobogrammaticNumbers_check, decide_eq_true_eq, strobogrammaticNumbers_spec] constructor · rintro ⟨hs, hc⟩ refine ⟨hs, ?_⟩ intro s h obtain ⟨k, hk⟩ := complete input s h simpa only [hk] using hc k (by simpa only [hk] using h) · rintro ⟨hs, hc⟩ exact ⟨hs, fun k hk => hc _ hk⟩ theorem wx_rotate_mem (c d : Char) (h : rotateChar c = some d) : d ∈ stroboDigits := by unfold rotateChar at h split at h <;> simp_all [stroboDigits] <;> grind only [] theorem wx_mapM_digits (xs ys : List Char) (h : List.mapM rotateChar xs = some ys) : ∀ c ∈ ys, c ∈ stroboDigits := by induction xs generalizing ys with | nil => simp at h; subst ys; simp | cons a xs ih => cases ha : rotateChar a with | none => simp [List.mapM_cons, ha] at h | some b => cases ht : List.mapM rotateChar xs with | none => simp [List.mapM_cons, ha, ht] at h | some bs => have he : b :: bs = ys := by simpa [List.mapM_cons, ha, ht] using h subst ys intro c hc simp only [List.mem_cons] at hc rcases hc with rfl | hc · exact wx_rotate_mem a c ha · exact ih bs ht c hc theorem wx_encode (xs : List Char) (h : ∀ c ∈ xs, c ∈ stroboDigits) : ∃ k : Nat, k < 5 ^ xs.length ∧ ((List.range xs.length).map fun i => stroboDigits.getD ((k / 5 ^ i) % 5) '0') = xs := by induction xs with | nil => exact ⟨0, by simp, by simp⟩ | cons c xs ih => obtain ⟨k, hk, he⟩ := ih (fun a ha => h a (by simp [ha])) have hc := h c (by simp) have hd : ∃ d : Nat, d < 5 ∧ stroboDigits.getD d '0' = c := by simp [stroboDigits] at hc rcases hc with rfl | rfl | rfl | rfl | rfl · exact ⟨0, by decide, rfl⟩ · exact ⟨1, by decide, rfl⟩ · exact ⟨2, by decide, rfl⟩ · exact ⟨3, by decide, rfl⟩ · exact ⟨4, by decide, rfl⟩ obtain ⟨d, hd, hdc⟩ := hd refine ⟨d + 5 * k, ?_, ?_⟩ · simp only [List.length_cons, pow_succ] omega · have hdiv : (d + 5 * k) / 5 = k := by omega have hmod : (d + 5 * k) % 5 = d := by omega simp only [List.length_cons, List.range_succ_eq_map, List.map_cons, List.map_map, pow_zero, Nat.div_one, hmod, hdc] congr 1 apply Eq.trans _ he apply List.map_congr_left intro i hi simp only [Function.comp_apply, Nat.pow_succ, Nat.mul_comm (5 ^ i) 5, ← Nat.div_div_eq_div_mul, hdiv] theorem wx_complete (n : Nat) (s : String) (h : IsStrobogrammaticNumber s n) : ∃ k : Fin (5 ^ n), decodeCandidate n k.val = s := by obtain ⟨k, hk, he⟩ := wx_encode s.toList (wx_mapM_digits _ _ h.2.2) refine ⟨⟨k, by simpa only [h.1] using hk⟩, ?_⟩ unfold decodeCandidate simp only [← h.1, he, String.ofList_toList] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem strobogrammaticNumbers_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : strobogrammaticNumbers_check input result ↔ strobogrammaticNumbers_spec input result := by exact wx_root wx_complete input result /-! ### Implementation helpers -/ /-- The five mirrored digit pairs: self-symmetric pairs first, then the cross pairs. -/ def stroboPairs : List (Char × Char) := (stroboDigits.filter fun d => decide (rotateChar d = some d)).map (fun d => (d, d)) ++ (stroboDigits.filter fun d => decide (rotateChar d ≠ some d)).map (fun d => (d, (rotateChar d).getD d)) /-- The digit pairs allowed on the outermost layer, excluding the leading-zero pair. -/ def outerPairs : List (Char × Char) := stroboPairs.filter fun p => decide (p.1 ≠ '0') /-- All completions of `s` after `k` more mirrored layers, forbidding the zero pair on the last one. -/ def addLayer : Nat → String → List String | 0, s => [s] | k + 1, s => let ps := if k = 0 then outerPairs else stroboPairs ps.flatMap fun p => addLayer k (String.singleton p.1 ++ s ++ String.singleton p.2) /-- Lexicographic less-than-or-equal on character lists. -/ def charListLe : List Char → List Char → Bool | [], _ => true | _ :: _, [] => false | a :: as, b :: bs => if a = b then charListLe as bs else decide (a.val < b.val) /-- Inserts `s` into an ordered list of strings. -/ def insertString (s : String) : List String → List String | [] => [s] | t :: ts => if charListLe s.toList t.toList then s :: t :: ts else t :: insertString s ts /-- Sorts strings lexicographically by insertion sort. -/ def sortStrings : List String → List String | [] => [] | s :: ss => insertString s (sortStrings ss) /-! ### Main algorithm (impl) -/ /-- The mirrored digit pairs ordered by first digit, so that wrapping layers in this order emits strings in lexicographic order. -/ def sortedStroboPairs : List (Char × Char) := [('0', '0'), ('1', '1'), ('6', '9'), ('8', '8'), ('9', '6')] /-- The pairs allowed on the outermost layer, in first-digit order. -/ def sortedOuterStroboPairs : List (Char × Char) := [('1', '1'), ('6', '9'), ('8', '8'), ('9', '6')] /-- Wraps `k` mirrored layers around each center string, outermost pair major, yielding lexicographic order. -/ def wrapAllSortedLayers : Nat → List String → List String | 0, centers => centers | k + 1, centers => let inner := wrapAllSortedLayers k centers sortedStroboPairs.flatMap fun p => inner.map fun s => String.singleton p.1 ++ s ++ String.singleton p.2 /-- The even-length strobogrammatic numbers with the given number of mirrored layers, generated directly in lexicographic order. -/ def sortedEvenStrobos : Nat → List String | 0 => [""] | k + 1 => let inner := wrapAllSortedLayers k [""] sortedOuterStroboPairs.flatMap fun p => inner.map fun s => String.singleton p.1 ++ s ++ String.singleton p.2 /-- Strobogrammatic numbers of length `input`, built from the center outward by wrapping mirrored digit pairs. -/ def findStrobogrammaticNumbers (input : Input) : Output := let centers : List String := if input % 2 = 1 then (stroboDigits.filter fun d => decide (rotateChar d = some d)).map String.singleton else [""] let built := centers.flatMap fun c => addLayer (input / 2) c if input % 2 = 0 then sortedEvenStrobos (input / 2) else built /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findStrobogrammaticNumbers_correct (input : Input) (h : isValidInput input) : strobogrammaticNumbers_spec input (findStrobogrammaticNumbers input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput 2 #guard isValidInput 1 #guard isValidInput 3 /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput 0) #guard !(isValidInput 15) #guard !(isValidInput 100) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard strobogrammaticNumbers_check 2 ["11", "69", "88", "96"] #guard strobogrammaticNumbers_check 1 ["0", "1", "8"] #guard strobogrammaticNumbers_check 3 ["101", "808", "609", "906", "111", "818", "619", "916", "181", "888", "689", "986"] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(strobogrammaticNumbers_check 2 ["00", "11", "69", "88", "96"]) #guard !(strobogrammaticNumbers_check 1 ["0", "1", "8", "11"]) #guard !(strobogrammaticNumbers_check 3 ["11", "69", "88", "96"]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findStrobogrammaticNumbers 2 == ["11", "69", "88", "96"] #guard findStrobogrammaticNumbers 1 == ["0", "1", "8"] #guard findStrobogrammaticNumbers 3 == ["101", "808", "609", "906", "111", "818", "619", "916", "181", "888", "689", "986"] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard strobogrammaticNumbers_check 2 (findStrobogrammaticNumbers 2) #guard strobogrammaticNumbers_check 1 (findStrobogrammaticNumbers 1) #guard strobogrammaticNumbers_check 3 (findStrobogrammaticNumbers 3) end PStrobogrammaticNumberIi