Problem #89 concerns the number of characters in Roman numerals. The question reads:
Project Euler Problem 89: Roman numerals For a number written in Roman numerals to be considered valid there are basic rules which must be followed. Even though the rules allow some numbers to be expressed in more than one way there is always a "best" way of writing a particular number. For example, it would appear that there are at least six ways of writing the number sixteen: IIIIIIIIIIIIIIII VIIIIIIIIIII VVIIIIII XIIIIII VVVI XVI However, according to the rules only XIIIIII and XVI are valid, and the last example is considered to be the most efficient, as it uses the least number of numerals. The 11K text file, roman.txt (right click and 'Save Link/Target As...'), contains one thousand numbers written in valid, but not necessarily minimal, Roman numerals; see About... Roman Numerals for the definitive rules for this problem. 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.
As it turns out, this was the last problem in the first hundred problems that I solved. I thought I would have to use an obscure Python library to solve it, but luckily I noticed the following trick:
Solution #1: Inefficient Pattern Approach
We can observe that there are only so many patterns of characters for a particular digit in Roman numerals which can be legal when written with an inefficient number of digits. Specifically, when dealing with a 9 in the hundreds place, “DCCCC” is legal, but “CM” is more efficient. When dealing with a 4 in the hundreds place, “CCCC” is legal, but “CD” is more efficient. When dealing with a 9 in the tens place, “LXXXX” is legal but “XC” is more efficient. When dealing with a 4 in the tens place, “XXXX” is legal but “XL” is more efficient. When dealing with a 9 in the ones place, “VIIII” is legal but “IX” is more efficient. Finally, when dealing with a 4 in the ones place, “IIII” is legal but “IV” is more efficient. Thus, to convert a Roman numeral to its most efficient form, it suffices to convert these patterns to their most efficient forms. The only thing we need to look out for is the order in which we do it: “DCCCC” must be replaced for “CCCC”, etc. Once we have done that, we can count the number of unnecessary characters. Here is an implementation in Python 2.7:
'''
Author: Walker Kroubalkian
String Parsing Approach to Project Euler Problem #89
'''
import time
from re import sub
f = open("PE89RomanNumerals.txt","r")
if f.mode=="r":
contents = f.readlines()
realContents = []
for x in contents:
realContents.append(str(x))
else:
raise ValueError("Cannot read from file")
finalContents = []
for x in realContents:
if x[len(x)-1]=="\n":
finalContents.append(x[0:len(x)-1])
else:
finalContents.append(x)
def replace(big,small,rep):
s = len(small)
while(True):
try:
x = big.index(small)
big = big[0:x]+rep+big[x+s:]
except:
break
return big
def projectEulerProblemEightyNine(myList):
total = 0
for x in myList:
v = len(x)
go = True
while(go):
temp = x
x = replace(x,"DCCCC","CM")
x = replace(x,"LXXXX","XC")
x = replace(x,"VIIII","IX")
x = replace(x,"CCCC","CD")
x = replace(x,"XXXX","XL")
x = replace(x,"IIII","IV")
if(x==temp):
go = False
total+=(v-len(x))
return total
start = time.time()
print projectEulerProblemEightyNine(finalContents)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
743
--- 0.00833415985107 seconds ---
for input of given list of Roman Numerals
'''
And with that, we’re done. That ran in only 8 milliseconds. I would like to find a Python library that can convert between decimal and Roman numerals, but that can wait for another day.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 