def number_to_numeral(n):
"""
returns minimal numeral
"""
remainder = n
values = [1000, 500, 100, 50, 10, 5, 1]
substractive_cases = [None, 100, 100, 10, 10, 1, 1]
symbols = dict(zip(values, ['M', 'D', 'C', 'L', 'X', 'V', 'I']))
numeral = ''
for i in range(len(values)):
if remainder >= values[i]:
# first substractive test
if substractive_cases[i] != None and i > 0:
if (remainder + substractive_cases[i]) >= values[i-1]:
remainder -= (values[i-1] - substractive_cases[i])
numeral += symbols[substractive_cases[i]] + symbols[values[i-1]]
# then normal test
while remainder >= values[i]:
remainder -= values[i]
numeral += symbols[values[i]]
return numeral
The problem with this problem is the "minimal" form as described here. It is important to pay attention to the potential errors arising from substractive combinations:
In addition to the three rules given above, if subtractive combinations are used then the following four rules must be followed.
Only one I, X, and C can be used as the leading numeral in part of a subtractive pair.
I can only be placed before V and X.
X can only be placed before L and C.
C can only be placed before D and M.
The substractive cases to take into account are thus:
First test case:
for i in range(1, 21):
print(number_to_numeral(i))
I II III IV V VI VII VIII IX X XI XII XIII XIV XV XVI XVII XVIII XIX XX
Second test case batch:
number_to_numeral(9)
'IX'
number_to_numeral(19)
'XIX'
number_to_numeral(400)
'CD'
number_to_numeral(405)
'CDV'
number_to_numeral(900)
'CM'
number_to_numeral(1900)
'MCM'
Now, on to the problem. First, we need to be able to read numerals, then we convert them to minimal form, storing the in-between result.
def numeral_to_number(numeral):
number = 0
values = [1000, 500, 100, 50, 10, 5, 1]
symbols = dict(zip(['M', 'D', 'C', 'L', 'X', 'V', 'I'], values))
for ind, num in enumerate(numeral):
if not ind == len(numeral) - 1:
if symbols[numeral[ind+1]] > symbols[num]:
number -= symbols[num]
else:
number += symbols[num]
else:
number += symbols[num]
return number
numeral_to_number('MMMDLXVIIII')
3569
number_to_numeral(3569)
'MMMDLXIX'
The final loop:
import urllib2 # the lib that handles the url stuff
data = urllib2.urlopen("https://projecteuler.net/project/resources/p089_roman.txt").readlines() # it's a file like object and works just like a file
initial_lengths = []
shortest_lengths = []
for line in data: # files are iterable
initial_lengths.append(len(line.strip()))
n = numeral_to_number(line.strip())
shortest_lengths.append(len(number_to_numeral(n)))
sum(initial_lengths)
8850
sum(shortest_lengths)
8107
And the answer is:
sum(initial_lengths) - sum(shortest_lengths)
743