import Mathlib /-! # Shifting Letters You are given a string s of lowercase English letters and an integer array shifts of the same length. Call the shift() of a letter, the next letter in the alphabet, (wrapping around so that 'z' becomes 'a'). For example, shift('a') = 'b', shift('t') = 'u', and shift('z') = 'a'. Now for each shifts[i] = x, we want to shift the first i + 1 letters of s, x times. Return the final string after all such shifts to s are applied. ## Constraints - 1 <= s.length <= 10^5 - s consists of lowercase English letters. - shifts.length == s.length - 0 <= shifts[i] <= 10^9 ## Provided examples - `s = "abc", shifts = [3, 5, 9]` → `"rpl"` - `s = "aaa", shifts = [1, 2, 3]` → `"gfd"` - `s = "z", shifts = [1]` → `"a"` ## Synthesized negative examples - invalid input: `s = "", shifts = []` ([structural] a predicate that admits 1 <= s.length <= 10^5. empty string below length floor) - invalid input: `s = "A", shifts = [0]` ([structural] a predicate that admits s consists of lowercase English letters.. uppercase letter; predicate allowing any letter accepts) - invalid input: `s = "a", shifts = [0, 0]` ([structural] a predicate that admits shifts.length == s.length. shifts one longer than s; predicates checking each side alone accept) - `s = "abc", shifts = [3, 5, 9]` → `"rst"` is wrong ([structural] prefix bound is dropped and every letter receives every shift. total shift 17 applied to each character) - `s = "aaa", shifts = [1, 2, 3]` → `"aaa"` is wrong ([structural] the output is not required to be the result of applying shifts. input echoed back; no shifts applied) - `s = "z", shifts = [1]` → `"b"` is wrong ([structural] applies x+1 shifts rather than x shifts. one extra shift maps z to b instead of a) -/ namespace PShiftingLetters abbrev Input := (String) × (List Nat) abbrev Output := String /-! ### Specification helpers -/ /-- The lowercase letter `c` shifted forward `n` positions in the alphabet, wrapping `'z'` around to `'a'`. -/ def shiftedChar (c : Char) (n : Nat) : Char := Char.ofNat ((c.toNat - 'a'.toNat + n) % 26 + 'a'.toNat) /-- The total shift applied to position `j`: the sum of `shifts[k]` over all indices `k` from `j` to the end. -/ def suffixShiftSum (shifts : List Nat) (j : Nat) : Nat := (shifts.drop j).sum /-! ### Validity predicate (V) -/ /-- Valid input: a string of 1 to 100000 lowercase letters, with a shifts list of the same length whose entries are all at most 1000000000. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 100000 && input.1.toList.all (fun c => 'a' ≤ c && c ≤ 'z') && input.2.length == input.1.length && input.2.all (fun x => x ≤ 1000000000) /-! ### Ideal specification (P_spec) -/ /-- `result` is the final string: it has the length of the input string, and at every position `j` its character is the input's character at `j` shifted by the sum of all shifts from index `j` onward. -/ def shiftingLetters_spec (input : Input) (result : Output) : Prop := result.length = input.1.length ∧ ∀ j : Nat, j < input.1.length → result.toList[j]? = (input.1.toList[j]?).map (fun c => shiftedChar c (suffixShiftSum input.2 j)) /-! ### Decidable specification (P_check) -/ /-- Executable checker obtained mechanically from the specification. -/ def shiftingLetters_check (input : Input) (result : Output) : Bool := @decide (shiftingLetters_spec input result) (by unfold shiftingLetters_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem shiftingLetters_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : shiftingLetters_check input result ↔ shiftingLetters_spec input result := by simp [shiftingLetters_check] /-! ### Implementation helpers -/ /-- The suffix sums of `shifts` in original order, built by one accumulating pass over the reversed list. -/ def suffixSums (shifts : List Nat) : List Nat := shifts.reverse.foldl (fun acc x => (x + acc.head?.getD 0) :: acc) [] /-! ### Main algorithm (impl) -/ /-- Shift each letter by its suffix sum: one reverse accumulation pass over `shifts`, then zip the characters of `s` with their sums through `shiftedChar`. -/ def applyShifts (input : Input) : Output := String.mk (List.zipWith shiftedChar input.1.toList (suffixSums input.2)) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem applyShifts_correct (input : Input) (h : isValidInput input) : shiftingLetters_spec input (applyShifts input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("abc", [3, 5, 9]) #guard isValidInput ("aaa", [1, 2, 3]) #guard isValidInput ("z", [1]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("", [])) #guard !(isValidInput ("A", [0])) #guard !(isValidInput ("a", [0, 0])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard shiftingLetters_check ("abc", [3, 5, 9]) "rpl" #guard shiftingLetters_check ("aaa", [1, 2, 3]) "gfd" #guard shiftingLetters_check ("z", [1]) "a" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(shiftingLetters_check ("abc", [3, 5, 9]) "rst") #guard !(shiftingLetters_check ("aaa", [1, 2, 3]) "aaa") #guard !(shiftingLetters_check ("z", [1]) "b") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard applyShifts ("abc", [3, 5, 9]) == "rpl" #guard applyShifts ("aaa", [1, 2, 3]) == "gfd" #guard applyShifts ("z", [1]) == "a" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard shiftingLetters_check ("abc", [3, 5, 9]) (applyShifts ("abc", [3, 5, 9])) #guard shiftingLetters_check ("aaa", [1, 2, 3]) (applyShifts ("aaa", [1, 2, 3])) #guard shiftingLetters_check ("z", [1]) (applyShifts ("z", [1])) end PShiftingLetters