Python Implementation of Problem 89
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 89
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.
1"""
2Project Euler Problem 89
3
4For a number written in Roman numerals to be considered valid there are basic rules which must be followed. Even though
5the rules allow some numbers to be expressed in more than one way there is always a "best" way of writing a particular
6number.
7
8For example, it would appear that there are at least six ways of writing the number sixteen:
9
10IIIIIIIIIIIIIIII
11VIIIIIIIIIII
12VVIIIIII
13XIIIIII
14VVVI
15XVI
16
17However, according to the rules only XIIIIII and XVI are valid, and the last example is considered to be the most
18efficient, as it uses the least number of numerals.
19
20The 11K text file, roman.txt (right click and 'Save Link/Target As...'), contains one thousand numbers written in
21valid, but not necessarily minimal, Roman numerals; see About... Roman Numerals for the definitive rules for this
22problem.
23
24Find the number of characters saved by writing each of these in their minimal form.
25
26Note: You can assume that all the Roman numerals in the file contain no more than four consecutive identical units.
27"""
28from .lib.utils import get_data_file
29
30
31def parse_roman(roman: str) -> int:
32 values = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
33 corrections = {
34 "IV": 2, # initially parsed as 6, but should be 4, so subtract 2
35 "IX": 2, # initially parsed as 11, but should be 9, so subtract 2
36 "XL": 20, # initially parsed as 60, but should be 40, so subtract 20
37 "XC": 20, # initially parsed as 110, but should be 90, so subtract 20
38 "CD": 200, # initially parsed as 600, but should be 400, so subtract 200
39 "CM": 200 # initially parsed as 1100, but should be 900, so subtract 200
40 }
41 number = sum(values[ch] for ch in roman)
42 number -= sum(val for key, val in corrections.items() if key in roman)
43 return number
44
45
46def make_roman(i: int) -> str:
47 ret = ""
48 values = (
49 (1000, "M"), (900, "CM"),
50 (500, "D"), (400, "CD"),
51 (100, "C"), (90, "XC"),
52 (50, "L"), (40, "XL"),
53 (10, "X"), (9, "IX"),
54 (5, "V"), (4, "IV")
55 )
56 for threshhold, string in values:
57 while i >= threshhold:
58 ret += string
59 i -= threshhold
60 return ret + "I" * i
61
62
63def to_minimal(r: str) -> str:
64 return make_roman(parse_roman(r))
65
66
67def main() -> int:
68 saved = 0
69 for raw_line in get_data_file('p0089_roman.txt').splitlines():
70 line = raw_line.rstrip('\n')
71 saved += len(line) - len(to_minimal(line))
72 return saved