Roman Numeral to Integer Parser & Formatter
Interpreting historical dates and chapter sequences requires bidirectional Roman numeral translation. Decoding iterates right-to-left: if a numeral is smaller than the previous character (`IV`), subtract its value; otherwise add it. Encoding greedily greedily decrements subtractive pairs (`M`, `CM`, `D`, `CD`) 🏛️🔢⚡.
ROMAN = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
def parse_roman(s):
total, prev = 0, 0
for ch in reversed(s):
val = ROMAN[ch]
total += -val if val < prev else val
prev = val
return total
print("MCMXCIV =", parse_roman("MCMXCIV"))
# 11. Roman Numeral to Integer Parser & Formatter Roman numeral conversion is an interview classic and a practical necessity when parsing release version identifiers, legal statutes, and publication metadata 🛑. ```python # The Subtractive Invariant: # Numerals: I=1, V=5, X=10, L=50, C=100, D=500, M=1000 # Normally additive: VI = 5 + 1 = 6 # Subtractive pair: IV = 5 - 1 = 4 (smaller preceding larger) ``` ### The Reverse Traversal Insight If you parse left-to-right, you must look ahead by one character to check if the next numeral is larger (`s[i] < s[i+1]`), which introduces boundary checks at the end of the string. When traversing **right-to-left**: - Keep track of `prev_val`. - If `current_val < prev_val`: Subtract `current_val` (e.g. `I` before `V`). - If `current_val >= prev_val`: Add `current_val` and update `prev_val = current_val`. - Zero index-out-of-bounds risks, single pass in $O(N)$ time 🏛️🔢⚡. --- ### Interactive Pop-Quiz 🧠 #### Why does traversing a Roman numeral string in reverse (right-to-left) drastically simplify the subtractive decoding logic? - [ ] Because you only need to store a single `prev_value` scalar; if the current digit is smaller than `prev_value`, it is subtractive 🏛️ - [ ] Because Roman numerals were historically written from right to left - [ ] Because Python reverse iteration executes in GPU hardware - [ ] It prevents string memory allocation --- ### Practical Challenge 🎯 Implement `roman_to_int(s: str) -> int` and `int_to_roman(num: int) -> str`. Handle standard subtractive notations (`IV`, `IX`, `XL`, `XC`, `CD`, `CM`). Verify `'MCMXCIV'` converts to 1994 and back, and `'LVIII'` converts to 58 and back. Assert both roundtrips and print the result. <details> <summary>Solution</summary> ```python ROMAN_MAP = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000} INT_ROMAN_PAIRS = [ (1000, "M"), (900, "CM"), (500, "D"), (400, "CD"), (100, "C"), (90, "XC"), (50, "L"), (40, "XL"), (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I") ] def roman_to_int(s: str) -> int: total = 0 prev_val = 0 for ch in reversed(s.upper()): val = ROMAN_MAP[ch] if val < prev_val: total -= val else: total += val prev_val = val return total def int_to_roman(num: int) -> str: res = [] for val, sym in INT_ROMAN_PAIRS: while num >= val: res.append(sym) num -= val return "".join(res) assert roman_to_int("MCMXCIV") == 1994 assert int_to_roman(1994) == "MCMXCIV" assert roman_to_int("LVIII") == 58 assert int_to_roman(58) == "LVIII" print(f"Roman verified: MCMXCIV={roman_to_int('MCMXCIV')}, 58={int_to_roman(58)}") ``` </details>