Problem 89: Roman Numerals

Mathematical Analysis

Roman Numeral Rules

The seven Roman numeral symbols and their values:

Subtractive Notation (Minimal Form)

In minimal form, subtractive notation is used:

• IV = 4, IX = 9
• XL = 40, XC = 90
• CD = 400, CM = 900

Parsing Roman Numerals

To convert a Roman numeral string to an integer: scan left to right. If the current symbol’s value is less than the next symbol’s value, subtract it; otherwise, add it.

Generating Minimal Form

To convert an integer to minimal Roman numeral form, greedily subtract the largest possible value from the following ordered table:

Editorial

Each input numeral is already valid, so there is no need to reason about alternative parses. We simply convert it to its integer value and then rebuild the unique minimal Roman representation of that same value. The number of saved characters is just the difference in lengths.

Both transformations are straightforward. Parsing is determined by the subtractive rule: a symbol contributes negatively only when it stands immediately before a larger symbol. Rebuilding is greedy from the standard minimal token table, because the special subtractive forms are already included. So the candidates are the symbols or token pairs allowed by Roman notation, and the minimal-form table is what constrains the output to the shortest legal representation.

Pseudocode

Set the total number of saved characters to 0.

For each Roman numeral in the data file:
    Parse it from left to right into an integer value
    Rebuild that value as a minimal Roman numeral using the ordered token table
    Add the difference in string lengths to the running total

Return the running total.

Examples of Savings

• IIII (4 chars) becomes IV (2 chars): saves 2.
• VIIII (5 chars) becomes IX (2 chars): saves 3.
• DCCCC (5 chars) becomes CM (2 chars): saves 3.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

• Time: $O(N \cdot L)$ where $N = 1000$ numerals and $L$ is the average length. Essentially $O(1)$ since all values are bounded.
• Space: $O(N \cdot L)$.

Answer

#include <bits/stdc++.h>
using namespace std;

int romanToInt(const string& s) {
    map<char, int> val = {
        {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
        {'C', 100}, {'D', 500}, {'M', 1000}
    };
    int result = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (i + 1 < (int)s.size() && val[s[i]] < val[s[i + 1]])
            result -= val[s[i]];
        else
            result += val[s[i]];
    }
    return result;
}

string intToRoman(int n) {
    const int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    const string symbols[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    string result;
    for (int i = 0; i < 13; i++) {
        while (n >= values[i]) {
            result += symbols[i];
            n -= values[i];
        }
    }
    return result;
}

int main() {
    // The roman numerals from Project Euler problem 89
    // Since we cannot download the file, we embed the known answer logic.
    // The file contains 1000 Roman numerals, one per line.
    // We read from stdin or a file.

    // Try reading from file first, then stdin
    ifstream fin("p089_roman.txt");
    istream& in = fin.is_open() ? fin : cin;

    int totalSaved = 0;
    string line;
    while (getline(in, line)) {
        // Remove trailing whitespace
        while (!line.empty() && (line.back() == '\r' || line.back() == '\n' || line.back() == ' '))
            line.pop_back();
        if (line.empty()) continue;

        int val = romanToInt(line);
        string minimal = intToRoman(val);
        totalSaved += (int)line.size() - (int)minimal.size();
    }

    cout << totalSaved << endl;
    return 0;
}

import urllib.request
import os

def roman_to_int(s):
    """Parse a Roman numeral string to integer."""
    val = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    result = 0
    for i in range(len(s)):
        if i + 1 < len(s) and val[s[i]] < val[s[i + 1]]:
            result -= val[s[i]]
        else:
            result += val[s[i]]
    return result

def int_to_roman(n):
    """Convert integer to minimal Roman numeral form."""
    values =  [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    symbols = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I']
    result = []
    for v, sym in zip(values, symbols):
        while n >= v:
            result.append(sym)
            n -= v
    return ''.join(result)

def solve():
    """
    Read Roman numerals from Project Euler data file.
    For each, convert to integer and back to minimal form.
    Count total characters saved.
    """
    # Try to read from local file first
    script_dir = os.path.dirname(os.path.abspath(__file__))
    local_file = os.path.join(script_dir, "p089_roman.txt")

    if os.path.exists(local_file):
        with open(local_file) as f:
            lines = f.read().strip().split('\n')
    else:
        # Download from Project Euler
        url = "https://projecteuler.net/resources/documents/0089_roman.txt"
        try:
            response = urllib.request.urlopen(url)
            data = response.read().decode('utf-8')
            lines = data.strip().split('\n')
            # Save locally for future use
            with open(local_file, 'w') as f:
                f.write(data)
        except Exception:
            print("Error: Could not read roman numerals file.")
            print("Please download p089_roman.txt from Project Euler and place it in this directory.")
            return

    total_saved = 0
    for line in lines:
        line = line.strip()
        if not line:
            continue
        val = roman_to_int(line)
        minimal = int_to_roman(val)
        total_saved += len(line) - len(minimal)

    print(total_saved)

if __name__ == "__main__":
    solve()