Problem 89: Roman Numerals

View on Project Euler

Project Euler Problem 89 Solution

EulerSolve provides an optimized solution for Project Euler Problem 89, Roman Numerals, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary The input file contains 1000 Roman numerals. Every numeral is valid, but some are not written in shortest form. The task is to rewrite each line in canonical minimal Roman notation and add up how many characters are saved. If \(s\) is one numeral, let \(\operatorname{val}(s)\) be its integer value and let \(R(n)\) be the minimal Roman representation of the integer \(n\). The required total is therefore $$\sum_s \bigl(|s|-|R(\operatorname{val}(s))|\bigr).$$ So the entire problem reduces to two precise operations on a single Roman string: evaluate it correctly, then reconstruct the same number in minimal form. Mathematical Approach The Roman alphabet is \(\{M,D,C,L,X,V,I\}\) with values \(1000,500,100,50,10,5,1\). Minimal Roman numerals also use the six subtractive pairs \(IV, IX, XL, XC, CD,\) and \(CM\). The implementations solve the problem entirely through these local value rules and the decimal block structure of Roman notation. Signed Contribution of Each Symbol Write a Roman string as \(s=s_1s_2\cdots s_m\), and let \(v(s_i)\) denote the value of the \(i\)-th symbol. In a valid numeral, a symbol contributes negatively exactly when it is the smaller member of a subtractive pair; otherwise it contributes positively....

Detailed mathematical approach

Problem Summary

The input file contains 1000 Roman numerals. Every numeral is valid, but some are not written in shortest form. The task is to rewrite each line in canonical minimal Roman notation and add up how many characters are saved.

If \(s\) is one numeral, let \(\operatorname{val}(s)\) be its integer value and let \(R(n)\) be the minimal Roman representation of the integer \(n\). The required total is therefore

$$\sum_s \bigl(|s|-|R(\operatorname{val}(s))|\bigr).$$

So the entire problem reduces to two precise operations on a single Roman string: evaluate it correctly, then reconstruct the same number in minimal form.

Mathematical Approach

The Roman alphabet is \(\{M,D,C,L,X,V,I\}\) with values \(1000,500,100,50,10,5,1\). Minimal Roman numerals also use the six subtractive pairs \(IV, IX, XL, XC, CD,\) and \(CM\). The implementations solve the problem entirely through these local value rules and the decimal block structure of Roman notation.

Signed Contribution of Each Symbol

Write a Roman string as \(s=s_1s_2\cdots s_m\), and let \(v(s_i)\) denote the value of the \(i\)-th symbol. In a valid numeral, a symbol contributes negatively exactly when it is the smaller member of a subtractive pair; otherwise it contributes positively. That gives the evaluation rule

$$\operatorname{val}(s)=\sum_{i=1}^{m}\sigma_i\,v(s_i),\qquad \sigma_i= \begin{cases} -1,& i<m \text{ and } v(s_i)<v(s_{i+1}),\\ 1,& \text{otherwise}. \end{cases}$$

This is why the parser only needs one-character lookahead. A rise in value means subtraction, while every non-rise means addition. For example,

$$MCMXCIX=1000-100+1000-10+100-1+10=1999.$$

The Minimal Token Table

To rebuild a number in shortest form, the implementations use the descending token list

$$\mathcal{T}=\bigl[(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)\bigr].$$

Starting from an integer \(n\), repeatedly take the largest token whose value does not exceed the current remainder, append its Roman symbol, and subtract its value. Because the table already contains the subtractive forms, the output is produced directly in canonical notation.

Why the Greedy Reconstruction Is Minimal

The key fact is that Roman numerals split naturally by decimal place. If

$$n=1000a+100b+10c+d,$$

then the minimal Roman numeral is obtained by concatenating a thousands block, a hundreds block, a tens block, and a ones block.

For a place whose symbols are \((u,f,t)\), meaning one, five, and ten times that place value, the minimal digit blocks satisfy

$$\bigl(\phi_{u,f,t}(0),\phi_{u,f,t}(1),\dots,\phi_{u,f,t}(9)\bigr)=\bigl(\varepsilon,u,uu,uuu,uf,f,fu,fuu,fuuu,ut\bigr).$$

Thus the ones place uses \((I,V,X)\), the tens place uses \((X,L,C)\), and the hundreds place uses \((C,D,M)\). The thousands block is simply \(a\) copies of \(M\).

No shorter valid block exists for any digit. The digit 4 is best written as \(IV\), not \(IIII\); the digit 9 is best written as \(IX\), not \(VIIII\); the digit 8 is best written as \(VIII\), not a longer additive alternative. Since the decimal places do not interfere with one another, minimizing each block separately minimizes the whole numeral.

The descending table \(\mathcal{T}\) is exactly a procedural version of this place-value decomposition. After all thousands are removed, the remainder is below 1000, so the next token choices determine the hundreds digit, then the tens digit, then the ones digit.

Worked Example

Consider the non-minimal numeral \(MDCCCCLXXXXVIIII\). Its value is

$$1000+(500+4\cdot100)+(50+4\cdot10)+(5+4\cdot1)=1999.$$

Now decompose \(1999\) by decimal place:

$$1999=1\cdot1000+9\cdot100+9\cdot10+9.$$

The minimal blocks are therefore

$$M,\qquad CM,\qquad XC,\qquad IX,$$

so the canonical numeral is \(MCMXCIX\). The original string has length \(16\), the minimal string has length \(7\), and this one line saves

$$16-7=9$$

characters. The checkpoint-style simplifications \(VIIII\to IX\) and \(LXXXX\to XC\) are smaller instances of the same rule.

The Quantity Being Summed

Once \(R(n)\) is defined by the minimal reconstruction rule, the final answer is just

$$\text{saved}=\sum_s \bigl(|s|-|R(\operatorname{val}(s))|\bigr).$$

Each line is independent of every other line. There is no hidden global combinatorics here; the entire mathematics lives inside correct Roman evaluation and minimal Roman re-encoding.

How the Code Works

Interpreting One Numeral

The C++, Python, and Java implementations first map each Roman character to its integer value. They scan the string from left to right and use one-step lookahead: if the next symbol is larger, the current value is subtracted; otherwise it is added. This computes \(\operatorname{val}(s)\) in a single pass.

Building the Canonical Numeral

After obtaining the integer value, the implementation walks through the fixed table \(\mathcal{T}\) from 1000 down to 1. For each entry, it appends the corresponding Roman token as many times as possible before moving to the next smaller token. Because \(CM, CD, XC, XL, IX,\) and \(IV\) already appear in the table, the produced string is the minimal Roman numeral itself, not merely an equivalent one.

Accumulating the Total Saving

For each input line, the implementation compares the length of the original numeral with the length of the reconstructed minimal numeral and adds the difference to a running total. The three language versions differ only in syntax; the algorithmic structure is the same.

Complexity Analysis

If the input contains numerals \(s_1,\dots,s_N\) with total length \(L_{\text{tot}}=\sum |s_i|\), then parsing costs \(O(L_{\text{tot}})\), because every input character is examined once. Reconstruction is also linear in the length of the produced minimal numerals, and the token table has fixed size 13.

For this problem the numerals are short, so the constants are tiny. Asymptotically the whole computation is linear in the total amount of input text, and the extra memory usage is \(O(1)\) beyond the current line and the minimal string being built.

Footnotes and References

  1. Problem page: Project Euler 89
  2. Roman numerals: Wikipedia - Roman numerals
  3. Numeral systems: Wikipedia - Numeral system
  4. Greedy algorithms: Wikipedia - Greedy algorithm

Problem 89 source code

C++

#include <fstream>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

namespace {

struct Options {
    std::string file = "resources/documents/0089_roman.txt";
    bool run_checkpoints = true;
};

bool parse_string_after_prefix(const std::string& arg,
                               const std::string& prefix,
                               std::string& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    value = tail;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_string_after_prefix(arg, "--file=", options.file)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return true;
}

int roman_value(const char c) {
    switch (c) {
        case 'I':
            return 1;
        case 'V':
            return 5;
        case 'X':
            return 10;
        case 'L':
            return 50;
        case 'C':
            return 100;
        case 'D':
            return 500;
        case 'M':
            return 1000;
        default:
            return 0;
    }
}

int roman_to_int(const std::string& s) {
    int total = 0;
    for (std::size_t i = 0; i < s.size(); ++i) {
        const int v = roman_value(s[i]);
        if (i + 1 < s.size() && roman_value(s[i + 1]) > v) {
            total -= v;
        } else {
            total += v;
        }
    }
    return total;
}

std::string int_to_minimal_roman(int value) {
    static const std::vector<std::pair<int, std::string>> table = {
        {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"},
    };

    std::string out;
    for (const auto& [v, tok] : table) {
        while (value >= v) {
            out += tok;
            value -= v;
        }
    }
    return out;
}

int solve(const std::string& file_path) {
    std::ifstream input(file_path);
    if (!input) {
        throw std::runtime_error("Could not open roman file: " + file_path);
    }

    int saved = 0;
    std::string line;
    while (std::getline(input, line)) {
        if (line.empty()) {
            continue;
        }

        const int value = roman_to_int(line);
        const std::string minimal = int_to_minimal_roman(value);
        saved += static_cast<int>(line.size() - minimal.size());
    }

    return saved;
}

bool run_checkpoints() {
    if (int_to_minimal_roman(roman_to_int("VIIII")) != "IX") {
        std::cerr << "Checkpoint failed for VIIII" << '\n';
        return false;
    }
    if (int_to_minimal_roman(roman_to_int("LXXXX")) != "XC") {
        std::cerr << "Checkpoint failed for LXXXX" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    try {
        std::cout << solve(options.file) << '\n';
    } catch (const std::exception& ex) {
        std::cerr << ex.what() << '\n';
        return 3;
    }

    return 0;
}

Python

# Problem 89: Roman numerals
# Find the number of characters saved by writing the Roman numerals in minimal form.

import os

def roman_to_int(s):
    vals = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
    total = 0
    for i in range(len(s)):
        if i + 1 < len(s) and vals[s[i]] < vals[s[i+1]]:
            total -= vals[s[i]]
        else:
            total += vals[s[i]]
    return total

def int_to_roman(n):
    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')]
    result = ''
    for val, sym in pairs:
        while n >= val:
            result += sym
            n -= val
    return result

def solve():
    script_dir = os.path.dirname(os.path.abspath(__file__))
    file_path = os.path.join(script_dir, '..', 'resources', 'documents', '0089_roman.txt')
    with open(file_path) as f:
        lines = [line.strip() for line in f if line.strip()]
    saved = 0
    for line in lines:
        val = roman_to_int(line)
        minimal = int_to_roman(val)
        saved += len(line) - len(minimal)
    print(saved)

solve()

Java

import java.nio.file.*;
import java.util.*;

public class Euler89 {
    static int romanToInt(String s) {
        Map<Character, Integer> v = Map.of('I', 1, 'V', 5, 'X', 10, 'L', 50, 'C', 100, 'D', 500, 'M', 1000);
        int total = 0;
        for (int i = 0; i < s.length(); i++)
            total += (i + 1 < s.length() && v.get(s.charAt(i)) < v.get(s.charAt(i + 1))) ? -v.get(s.charAt(i))
                    : v.get(s.charAt(i));
        return total;
    }

    static String intToRoman(int n) {
        int[] vals = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
        String[] syms = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < vals.length; i++)
            while (n >= vals[i]) {
                sb.append(syms[i]);
                n -= vals[i];
            }
        return sb.toString();
    }

    public static void main(String[] args) throws Exception {
        List<String> lines = Files.readAllLines(Path.of("resources/documents/0089_roman.txt"));
        int saved = 0;
        for (String line : lines) {
            line = line.trim();
            if (line.isEmpty())
                continue;
            saved += line.length() - intToRoman(romanToInt(line)).length();
        }
        System.out.println(saved);
    }
}