# Efficiency in Roman expression

Published on 2012-04-21It's been a while since I tried my hand at Project Euler, and in the meantime, I seem to have forgotten a good deal about C# syntax. I wrote the solution to problem 89 in python, as it seemed easier to get my sea legs back in that language.

This problem asks for a list of Roman numerals to be optimized, that is, to be rewritten in as few characters as possible:

The rules for writing Roman numerals allow for many ways of writing each number. However, there is always a "best" way of writing a particular number.

For example, the following represent all of the legitimate ways of writing the number sixteen:

IIIIIIIIIIIIIIII

VIIIIIIIIIII

VVIIIIII

XIIIIII

VVVI

XVI

The last example being considered the most efficient, as it uses the least number of numerals.

The 11K text file, roman.txt, contains one thousand numbers written in valid, but not necessarily minimal, Roman numerals; that is, they are arranged in descending units and obey the subtractive pair rule (see About Roman Numerals...)

Find the number of characters saved by writing each of these in their minimal form.

Note: You can assume that all the Roman numerals in the file contain no more than four consecutive identical units.

Python made this easy by building a "replace" function into the string class. I read the text file into a list, each member of which was optimized individually. Rather than saving the efficient expressions in a separate array, I just kept a running count of the number of characters saved, as that's all Project Euler wanted.

original = open("roman.txt").readlines() originalLength = 0 revisedLength = 0 for numeral in original: originalLength += len(numeral) temporary = numeral.replace("DD","M") temporary = temporary.replace("LL","C") temporary = temporary.replace("CCCC","CD") temporary = temporary.replace("DCD","CM") temporary = temporary.replace("XXXX","XL") temporary = temporary.replace("LXL","XC") temporary = temporary.replace("IIII","IV") temporary = temporary.replace("VIV","IX") revisedLength += len(temporary) print(originalLength - revisedLength)