import Mathlib /-! # Decode Ways You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping: "1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z' However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25"). For example, "11106" can be decoded into: "AAJF" with the grouping (1, 1, 10, 6) "KJF" with the grouping (11, 10, 6) The grouping (1, 11, 06) is invalid because "06" is not a valid code (only "6" is valid). Note: there may be strings that are impossible to decode. Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0. The test cases are generated so that the answer fits in a 32-bit integer. ## Constraints - 1 <= s.length <= 100 - s contains only digits and may contain leading zero(s). ## Provided examples - `s = "12"` → `2` - `s = "226"` → `3` - `s = "06"` → `0` ## Synthesized negative examples - invalid input: `s = ""` ([structural] a predicate that admits 1 <= s.length <= 100. empty string is below the minimum length) - invalid input: `s = "a"` ([structural] a predicate that admits s contains only digits and may contain leading zero(s).. letter is not a digit) - invalid input: `s = "11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111"` ([structural] a predicate that admits 1 <= s.length <= 100. 101 digits exceed the maximum length) - `s = "12"` → `1` is wrong ([structural] two-character codes 10 through 26 are omitted from the decoding alphabet. only single-digit grouping is counted) - `s = "226"` → `0` is wrong ([structural] no condition requires a positive count when a decoding exists. returns 0 although valid decodings exist) - `s = "06"` → `1` is wrong ([structural] count is one off from the true number of decodings. true count is 0) -/ namespace PDecodeWays abbrev Input := String abbrev Output := Nat /-! ### Specification helpers -/ /-- `codes` decodes `s`: the codes concatenate to `s` and each is a valid code, of length one or two, with no leading zero and numeric value between 1 and 26. -/ def IsDecoding (s : String) (codes : List String) : Prop := String.join codes = s ∧ ∀ c ∈ codes, (c.length = 1 ∨ c.length = 2) ∧ c.front ≠ '0' ∧ 1 ≤ c.toNat! ∧ c.toNat! ≤ 26 /-! ### Validity predicate (V) -/ /-- Valid input: a string of between 1 and 100 characters, all of them digits. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 100 && input.toList.all Char.isDigit /-! ### Ideal specification (P_spec) -/ /-- `result` is the size of a finite collection of lists of strings that contains a list exactly when it is a decoding of `input`. -/ def numDecodings_spec (input : Input) (result : Output) : Prop := ∃ T : Set (List String), T.Finite ∧ T.ncard = result ∧ ∀ ds : List String, ds ∈ T ↔ IsDecoding input ds /-! ### Decidable specification (P_check) -/ /-- Bool mirror of the per-code condition in `IsDecoding`: length one or two, no leading zero, value in 1..26. -/ def isValidCode (c : String) : Bool := decide ((c.length = 1 ∨ c.length = 2) ∧ c.front ≠ '0' ∧ 1 ≤ c.toNat! ∧ c.toNat! ≤ 26) /-- Bool mirror of `IsDecoding`: the codes join to `s` and every code is valid. -/ def isDecodingOf (s : String) (codes : List String) : Bool := decide (String.join codes = s) && codes.all isValidCode /-- All partitions of a character list into contiguous blocks of length one or two. -/ def partitions : List Char → List (List String) | [] => [[]] | [c] => [[String.ofList [c]]] | c1 :: c2 :: rest => ((partitions (c2 :: rest)).map fun ps => String.ofList [c1] :: ps) ++ ((partitions rest).map fun ps => String.ofList [c1, c2] :: ps) /-- Executable checker for `numDecodings_spec`: `result` equals the number of valid decodings among the length-one-or-two block partitions of `input`. -/ def numDecodings_check (input : Input) (result : Output) : Bool := result == ((partitions input.toList).filter fun ds => isDecodingOf input ds).length theorem root_of_bridges (complete : ∀ s ds, IsDecoding s ds → ds ∈ partitions s.toList) (unique : ∀ cs, (partitions cs).Nodup) (input : Input) (result : Output) : numDecodings_check input result ↔ numDecodings_spec input result := by classical let L := (partitions input.toList).filter (isDecodingOf input) have reflect (ds : List String) : isDecodingOf input ds = true ↔ IsDecoding input ds := by simp [isDecodingOf, isValidCode, IsDecoding, List.all_eq_true] have mem (ds : List String) : ds ∈ L ↔ IsDecoding input ds := by simp only [L, List.mem_filter, reflect] exact ⟨And.right, fun h => ⟨complete input ds h, h⟩⟩ have nd : L.Nodup := (unique input.toList).filter _ have card : (L.toFinset : Set (List String)).ncard = L.length := by rw [Set.ncard_coe_finset, List.toFinset_card_of_nodup nd] change (result == L.length) = true ↔ _ rw [beq_iff_eq] constructor · intro h refine ⟨L.toFinset, Finset.finite_toSet _, ?_, ?_⟩ · exact card.trans h.symm · intro ds simpa using mem ds · rintro ⟨T, _, ht, hm⟩ have eq : T = (L.toFinset : Set (List String)) := by ext ds simpa using (hm ds).trans (mem ds).symm rw [eq, card] at ht exact ht.symm theorem partition_prepend_one (a : Char) (cs : List Char) (ds : List String) (hd : ds ∈ partitions cs) : String.ofList [a] :: ds ∈ partitions (a :: cs) := by cases cs with | nil => simpa [partitions] using hd | cons b rest => simp only [partitions, List.mem_append, List.mem_map] exact Or.inl ⟨ds, hd, rfl⟩ theorem partition_prepend_two (a b : Char) (cs : List Char) (ds : List String) (hd : ds ∈ partitions cs) : String.ofList [a, b] :: ds ∈ partitions (a :: b :: cs) := by simp only [partitions, List.mem_append, List.mem_map] exact Or.inr ⟨ds, hd, rfl⟩ theorem partitions_join (ds : List String) (hl : ∀ c ∈ ds, c.length = 1 ∨ c.length = 2) : ds ∈ partitions (String.join ds).toList := by induction ds with | nil => simp [partitions] | cons c ds ih => have ih' := ih (fun d hd => hl d (List.mem_cons_of_mem c hd)) have hc := hl c (by simp) rcases hc with hc | hc · have hn : c.toList.length = 1 := by rw [String.length_toList]; exact hc obtain ⟨a, ha⟩ := List.length_eq_one_iff.mp hn have he : c = String.ofList [a] := by apply String.toList_inj.mp simpa using ha subst c simpa using partition_prepend_one a (String.join ds).toList ds ih' · have hn : c.toList.length = 2 := by rw [String.length_toList]; exact hc obtain ⟨a, b, ha⟩ := List.length_eq_two.mp hn have he : c = String.ofList [a, b] := by apply String.toList_inj.mp simpa using ha subst c simpa using partition_prepend_two a b (String.join ds).toList ds ih' theorem partitions_complete (s : String) (ds : List String) (hd : IsDecoding s ds) : ds ∈ partitions s.toList := by rw [← hd.1] exact partitions_join ds (fun c hc => (hd.2 c hc).1) theorem root_with_complete (unique : ∀ cs : List Char, (partitions cs).Nodup) (input : Input) (result : Output) : numDecodings_check input result ↔ numDecodings_spec input result := root_of_bridges partitions_complete unique input result lemma partitions_unique : ∀ cs : List Char, (partitions cs).Nodup := by intro cs induction cs using List.twoStepInduction with | nil => simp [partitions] | singleton c => simp [partitions] | cons_cons c1 c2 rest ihrest ihtail => rw [partitions, List.nodup_append'] refine ⟨(ihtail c2).map ?_, ihrest.map ?_, ?_⟩ · intro xs ys hxy exact (List.cons.inj hxy).2 · intro xs ys hxy exact (List.cons.inj hxy).2 · rw [List.disjoint_iff_ne] intro xs hxs ys hys simp only [List.mem_map] at hxs hys rcases hxs with ⟨ps, hps, rfl⟩ rcases hys with ⟨qs, hqs, rfl⟩ intro heq have hstr : String.ofList [c1] = String.ofList [c1, c2] := (List.cons.inj heq).1 have hlist : [c1] = [c1, c2] := String.ofList_injective hstr simp at hlist /-- On valid input the checker accepts exactly the specified outputs. -/ theorem numDecodings_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : numDecodings_check input result ↔ numDecodings_spec input result := by exact root_with_complete partitions_unique input result /-! ### Implementation helpers -/ /-- DP table as a list: after processing positions n-1 down to i, the head is the number of decodings of the suffix starting at i; seeded with 1 for the empty suffix. -/ def suffixWays (cs : Array Char) : List Nat := let n := cs.size (List.range n).reverse.foldl (fun acc i => let one := if isValidCode (String.ofList [cs[i]!]) then acc.head! else 0 let two := if i + 1 < n && isValidCode (String.ofList [cs[i]!, cs[i + 1]!]) then acc.tail.head! else 0 (one + two) :: acc) [1] /-! ### Main algorithm (impl) -/ /-- Number of decodings by dynamic programming over suffix positions: each position sums the ways from the valid one-character and two-character codes starting there. -/ def countDecodings (input : Input) : Output := (suffixWays input.toList.toArray).head! /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem countDecodings_correct (input : Input) (h : isValidInput input) : numDecodings_spec input (countDecodings input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "12" #guard isValidInput "226" #guard isValidInput "06" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "") #guard !(isValidInput "a") #guard !(isValidInput "11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard numDecodings_check "12" 2 #guard numDecodings_check "226" 3 #guard numDecodings_check "06" 0 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(numDecodings_check "12" 1) #guard !(numDecodings_check "226" 0) #guard !(numDecodings_check "06" 1) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard countDecodings "12" == 2 #guard countDecodings "226" == 3 #guard countDecodings "06" == 0 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard numDecodings_check "12" (countDecodings "12") #guard numDecodings_check "226" (countDecodings "226") #guard numDecodings_check "06" (countDecodings "06") end PDecodeWays