import Mathlib /-! # Integer To Roman Seven different symbols represent Roman numerals with the following values: Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules: If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral. If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for example, 4 is 1 (I) less than 5 (V): IV and 9 is 1 (I) less than 10 (X): IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM). Only powers of 10 (I, X, C, M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times use the subtractive form. Given an integer, convert it to a Roman numeral. ## Constraints - 1 <= num <= 3999 ## Provided examples - `num = 3749` → `"MMMDCCXLIX"` - `num = 58` → `"LVIII"` - `num = 1994` → `"MCMXCIV"` ## Synthesized negative examples - invalid input: `num = 0` ([structural] a predicate that admits 1 <= num <= 3999. one below the stated minimum) - invalid input: `num = 4000` ([structural] a predicate that admits 1 <= num <= 3999. one above the stated maximum) - invalid input: `num = 10000` ([structural] a predicate that admits 1 <= num <= 3999. order of magnitude past the ceiling) - `num = 3749` → `"MMMDCCIL"` is wrong ([structural] allowed subtractive forms are not restricted to the six listed. uses IL for 49; value is 3749 if allowed) - `num = 58` → `"LIX"` is wrong ([structural] conversion may be off by one from the input value. Roman numeral for 59, one greater than 58) - `num = 1994` → `"MCMXCV"` is wrong ([structural] conversion off by one at the units digit. MCMXCV is 1995, one more than the true value.) -/ namespace PIntegerToRoman abbrev Input := Nat abbrev Output := String /-! ### Specification helpers -/ /-- The value of a single Roman numeral symbol, `none` for any other character. -/ def symbolValue (c : Char) : Option Nat := match c with | 'I' => some 1 | 'V' => some 5 | 'X' => some 10 | 'L' => some 50 | 'C' => some 100 | 'D' => some 500 | 'M' => some 1000 | _ => none /-- The value of a list of symbol values under the left-to-right subtractive rule: a value immediately followed by a larger one is subtracted, otherwise added. -/ def romanListValue : List Nat → Int | [] => 0 | [v] => (v : Int) | v₁ :: v₂ :: rest => (if v₁ < v₂ then -(v₁ : Int) else (v₁ : Int)) + romanListValue (v₂ :: rest) /-- The number denoted by `s` read as a Roman numeral, `none` for the empty string or for strings containing characters other than the seven Roman symbols. -/ def RomanValue (s : String) : Option Nat := match s.toList.mapM symbolValue with | none => none | some [] => none | some vs => some (romanListValue vs).toNat /-- The canonical forms of the thousands place: zero to three `M`s. -/ def thousandsForms : List String := ["", "M", "MM", "MMM"] /-- The canonical forms of the hundreds place, in increasing order of value. -/ def hundredsForms : List String := ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"] /-- The canonical forms of the tens place, in increasing order of value. -/ def tensForms : List String := ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"] /-- The canonical forms of the units place, in increasing order of value. -/ def unitsForms : List String := ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"] /-- `s` is a canonical Roman numeral: a concatenation of one canonical form for each decimal place, from thousands down to units. -/ def IsCanonicalRoman (s : String) : Prop := ∃ th ∈ thousandsForms, ∃ hu ∈ hundredsForms, ∃ te ∈ tensForms, ∃ un ∈ unitsForms, s = th ++ hu ++ te ++ un /-! ### Validity predicate (V) -/ /-- Valid input: an integer between 1 and 3999 inclusive. -/ def isValidInput (input : Input) : Bool := 1 ≤ input && input ≤ 3999 /-! ### Ideal specification (P_spec) -/ /-- `result` is the canonical Roman numeral for `input`: it parses as a Roman numeral denoting `input`, and it lies in the canonical Roman numeral language. -/ def intToRoman_spec (input : Input) (result : Output) : Prop := RomanValue result = some input ∧ IsCanonicalRoman result /-! ### Decidable specification (P_check) -/ /-- Decidable canonicity check by enumerating the four frozen lists of place-value forms. -/ def isCanonicalRomanEnum (s : String) : Bool := thousandsForms.any fun th => hundredsForms.any fun hu => tensForms.any fun te => unitsForms.any fun un => decide (s = th ++ hu ++ te ++ un) /-- Executable checker for `intToRoman_spec`. -/ def intToRoman_check (input : Input) (result : Output) : Bool := decide (RomanValue result = some input) && isCanonicalRomanEnum result /-- The enumeration of place forms decides canonicity. -/ theorem integer_to_roman_enum_iff (s : String) : isCanonicalRomanEnum s = true ↔ IsCanonicalRoman s := by simp only [isCanonicalRomanEnum, IsCanonicalRoman, List.any_eq_true, decide_eq_true_eq] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem intToRoman_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : intToRoman_check input result ↔ intToRoman_spec input result := by unfold intToRoman_check intToRoman_spec rw [Bool.and_eq_true, decide_eq_true_iff] exact and_congr Iff.rfl (integer_to_roman_enum_iff result) /-! ### Implementation helpers -/ /-- The thousands, hundreds, tens, and units digits of `n`, in that order. -/ def decimalDigits (n : Nat) : Nat × Nat × Nat × Nat := (n / 1000, n / 100 % 10, n / 10 % 10, n % 10) /-- The canonical place form at index `d` of `forms`, `""` when `d` is out of range. -/ def lookupForm (forms : List String) (d : Nat) : String := forms.getD d "" /-! ### Main algorithm (impl) -/ /-- Canonical Roman numeral by extracting the four decimal digits and indexing the frozen canonical-form lists per place. -/ def convertToRoman (input : Input) : Output := let (th, hu, te, un) := decimalDigits input lookupForm thousandsForms th ++ lookupForm hundredsForms hu ++ lookupForm tensForms te ++ lookupForm unitsForms un /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem convertToRoman_correct (input : Input) (h : isValidInput input) : intToRoman_spec input (convertToRoman input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput 3749 #guard isValidInput 58 #guard isValidInput 1994 /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput 0) #guard !(isValidInput 4000) #guard !(isValidInput 10000) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard intToRoman_check 3749 "MMMDCCXLIX" #guard intToRoman_check 58 "LVIII" #guard intToRoman_check 1994 "MCMXCIV" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(intToRoman_check 3749 "MMMDCCIL") #guard !(intToRoman_check 58 "LIX") #guard !(intToRoman_check 1994 "MCMXCV") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard convertToRoman 3749 == "MMMDCCXLIX" #guard convertToRoman 58 == "LVIII" #guard convertToRoman 1994 == "MCMXCIV" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard intToRoman_check 3749 (convertToRoman 3749) #guard intToRoman_check 58 (convertToRoman 58) #guard intToRoman_check 1994 (convertToRoman 1994) end PIntegerToRoman