def value(x): if x == 'I': return 1 elif x == 'V': return 5 elif x == 'X': return 10 elif x == 'L': return 50 elif x == 'C': return 100 elif x == 'D': return 500 elif x == 'M': return 1000 else: print "Decoding error: " + x return None def decode_roman(n): result = 0 for i in xrange(len(n)-1): # search for subtractive pairs cur = value(n[i]) nxt = value(n[i+1]) if cur < nxt: result -= cur else: result += cur result += value(n[-1]) return result def minimal_roman(n): result = "" while n > 0: if n - 1000 >= 0: n -= 1000 result += "M" elif n - 900 >= 0: n -= 900 result += "CM" elif n - 500 >= 0: n -= 500 result += "D" elif n - 400 >= 0: n -= 400 result += "CD" elif n - 100 >= 0: n -= 100 result += "C" elif n - 90 >= 0: n -= 90 result += "XC" elif n - 50 >= 0: n -= 50 result += "L" elif n - 40 >= 0: n -= 40 result += "XL" elif n - 10 >= 0: n -= 10 result += "X" elif n - 9 >= 0: n -= 9 result += "IX" elif n - 5 >= 0: n -= 5 result += "V" elif n - 4 >= 0: n -= 4 result += "IV" elif n - 1 >= 0: n -= 1 result += "I" return result numbers = [] f = open('089.txt', 'r') for line in f: line = line.rstrip('\r\n') numbers.append(line) f.close() saved = 0 for number in numbers: n = decode_roman(number) m = minimal_roman(n) saved += len(number) - len(m) print saved