import Mathlib /-! # Roman To Integer Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II. Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used: I can be placed before V (5) and X (10) to make 4 and 9. X can be placed before L (50) and C (100) to make 40 and 90. C can be placed before D (500) and M (1000) to make 400 and 900. Given a roman numeral, convert it to an integer. ## Constraints - 1 <= s.length <= 15 - s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M'). - It is guaranteed that s is a valid roman numeral in the range [1, 3999]. ## Provided examples - `s = "III"` → `3` - `s = "LVIII"` → `58` - `s = "MCMXCIV"` → `1994` ## Synthesized negative examples - invalid input: `s = "IIII"` ([structural] a predicate that admits It is guaranteed that s is a valid roman numeral in the range [1, 3999].. four I's invalid; a parser that sums repeated I's accepts it) - invalid input: `s = "MMMM"` ([structural] a predicate that admits It is guaranteed that s is a valid roman numeral in the range [1, 3999].. one step past the 3999 maximum) - invalid input: `s = "VX"` ([structural] a predicate that admits It is guaranteed that s is a valid roman numeral in the range [1, 3999].. V may not precede X; left-to-right parser accepts it) - `s = "III"` → `2` is wrong ([structural] summation stops one symbol early. III read as II) - `s = "LVIII"` → `57` is wrong ([structural] the specification omits the final I. reads LVIII as LVII) - `s = "MCMXCIV"` → `2216` is wrong ([structural] not an optimization; omits the subtractive-notation rule. adds every symbol value, ignores all subtractions) -/ namespace PRomanToInteger abbrev Input := String abbrev Output := Nat /-! ### Specification helpers -/ /-- The face value of a roman numeral symbol, zero for any other character. -/ def symbolValue (c : Char) : Nat := if c == 'I' then 1 else if c == 'V' then 5 else if c == 'X' then 10 else if c == 'L' then 50 else if c == 'C' then 100 else if c == 'D' then 500 else if c == 'M' then 1000 else 0 /-- `c₁`, `c₂` is one of the six permitted subtractive pairs. -/ def isSubtractivePair (c₁ c₂ : Char) : Bool := (c₁ == 'I' && (c₂ == 'V' || c₂ == 'X')) || (c₁ == 'X' && (c₂ == 'L' || c₂ == 'C')) || (c₁ == 'C' && (c₂ == 'D' || c₂ == 'M')) /-- `n` is the integer denoted by the numeral `cs`: each symbol contributes its face value, negatively when it opens a subtractive pair. -/ def romanValue : List Char → Nat → Prop | [], n => n = 0 | [c], n => n = symbolValue c | c₁ :: c₂ :: rest, n => ∃ m, romanValue (c₂ :: rest) m ∧ n = (if isSubtractivePair c₁ c₂ then m - symbolValue c₁ else m + symbolValue c₁) /-- `n` is the integer denoted by the roman numeral `s`. -/ def RomanValue (s : String) (n : Nat) : Prop := romanValue s.toList n /-- Drop up to `k` leading copies of `c` from `cs`. -/ def dropUpTo (c : Char) : Nat → List Char → List Char | 0, cs => cs | _ + 1, [] => [] | k + 1, x :: rest => if x == c then dropUpTo c k rest else x :: rest /-- Consume one numeral group built from symbols `one`, `five`, `ten` (shapes `one-ten`, `one-five`, `five one{0,3}`, `one{1,3}` or empty), returning the remainder. -/ def matchGroup (one five ten : Char) : List Char → List Char | [] => [] | [c] => if c == one || c == five then [] else [c] | c₁ :: c₂ :: rest => if c₁ == one && (c₂ == five || c₂ == ten) then rest else if c₁ == five then dropUpTo one 3 (c₂ :: rest) else if c₁ == one then dropUpTo one 2 (c₂ :: rest) else c₁ :: c₂ :: rest /-- `cs` is a nonempty well-formed roman numeral, hence denotes a value in [1, 3999]. -/ def isValidRoman (cs : List Char) : Bool := let rest₁ := dropUpTo 'M' 3 cs let rest₂ := matchGroup 'C' 'D' 'M' rest₁ let rest₃ := matchGroup 'X' 'L' 'C' rest₂ let rest₄ := matchGroup 'I' 'V' 'X' rest₃ !cs.isEmpty && rest₄.isEmpty /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 15 characters from the roman alphabet forming a well-formed roman numeral in [1, 3999]. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 15 && input.toList.all (fun c => "IVXLCDM".toList.contains c) && isValidRoman input.toList /-! ### Ideal specification (P_spec) -/ /-- `result` is the value of `input` read as a roman numeral: `result` is a value of `input`, and every value of `input` equals `result`. -/ def romanToInt_spec (input : Input) (result : Output) : Prop := RomanValue input result ∧ ∀ n : Nat, RomanValue input n → n = result /-! ### Decidable specification (P_check) -/ /-- The list of integers denoted by the numeral `cs`: the image of the evaluation relation, computed by the same recursion as `romanValue`. -/ def romanValues : List Char → List Nat | [] => [0] | [c] => [symbolValue c] | c₁ :: c₂ :: rest => (romanValues (c₂ :: rest)).map fun m => if isSubtractivePair c₁ c₂ then m - symbolValue c₁ else m + symbolValue c₁ /-- Executable checker for `romanToInt_spec`: `result` is a value of `input` and every value of `input` equals `result`. -/ def romanToInt_check (input : Input) (result : Output) : Bool := let vals := romanValues input.toList decide (result ∈ vals ∧ ∀ n ∈ vals, n = result) theorem mem_romanValues_iff : ∀ cs n, n ∈ romanValues cs ↔ romanValue cs n := by intro cs induction cs with | nil => intro n simp [romanValues, romanValue] | cons c cs ih => cases cs with | nil => intro n simp [romanValues, romanValue] | cons c₂ rest => intro n simp only [romanValues, romanValue, List.mem_map] grind only [] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem romanToInt_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : romanToInt_check input result ↔ romanToInt_spec input result := by simpa only [romanToInt_check, romanToInt_spec, RomanValue, decide_eq_true_eq, mem_romanValues_iff] /-! ### Main algorithm (impl) -/ /-- Value of a roman numeral by one linear evaluation pass: take the head of the computed value list, with 0 as the unreachable default for valid input. -/ def convertRomanToInt (input : Input) : Output := (romanValues input.toList).headD 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem convertRomanToInt_correct (input : Input) (h : isValidInput input) : romanToInt_spec input (convertRomanToInt input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "III" #guard isValidInput "LVIII" #guard isValidInput "MCMXCIV" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "IIII") #guard !(isValidInput "MMMM") #guard !(isValidInput "VX") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard romanToInt_check "III" 3 #guard romanToInt_check "LVIII" 58 #guard romanToInt_check "MCMXCIV" 1994 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(romanToInt_check "III" 2) #guard !(romanToInt_check "LVIII" 57) #guard !(romanToInt_check "MCMXCIV" 2216) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard convertRomanToInt "III" == 3 #guard convertRomanToInt "LVIII" == 58 #guard convertRomanToInt "MCMXCIV" == 1994 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard romanToInt_check "III" (convertRomanToInt "III") #guard romanToInt_check "LVIII" (convertRomanToInt "LVIII") #guard romanToInt_check "MCMXCIV" (convertRomanToInt "MCMXCIV") end PRomanToInteger