Problem Analysis
The task is fundamentally a transcoding exercise: each input line is a valid but possibly wasteful Roman numeral, and I need to total how many characters I would save by rewriting every one of them in its shortest legal form. The crucial observation is that the rules of Roman notation define a unique canonical form for every positive integer in the range the file covers. A canonical form is simply the single "best" representation chosen by a fixed set of rules - here, the shortest valid numeral. Because that form is unique, I never have to weigh competing representations: I convert each numeral to a plain integer (a neutral, unambiguous intermediate) and re-encode that integer minimally. The difference in lengths is the saving for that line.
The re-encoding step is a greedy algorithm: at each step I consume the largest "denomination" that still fits the remaining value, where the denominations are the seven base symbols (I, V, X, L, C, D, M) plus the six subtractive pairs (IV, IX, XL, XC, CD, CM). Greedy is provably optimal here for the same reason it is optimal for making change with this particular denomination set - no combination of smaller pieces can express a value in fewer characters than taking the largest fitting piece first. Both the parse and the encode run in O(L) time per numeral, where L is the numeral's length (bounded by a small constant), so the whole program is O(N) in the number of lines - a thousand here, processed essentially instantly.
Solution Approach
Greedy Parse-then-Encode (Python and C)
Both files implement the same two-phase algorithm; I describe it once and note the language differences afterward.
Phase 1 - parse to integer. I scan the numeral from right to left, holding the
value of the previously seen (rightmost) symbol in a variable last. For each symbol I
look up its value n: if last > n the symbol is the smaller half of a
subtractive pair (the I in IX), so I subtract it; otherwise I add it. Reading right-to-left makes
this work with no look-ahead, because the larger neighbour of any subtractive pair is always already
in last by the time I reach the smaller symbol. The Python version iterates over
reversed(numeral) and indexes a dict; the C version uses a backward
for loop and a switch in char_value, which the compiler turns
into a fast jump table.
Phase 2 - encode minimally. I keep a table of (value, string) denominations ordered
from largest to smallest, including all six subtractive pairs. In a loop, while the remaining number
is positive, I pick the largest denomination that fits, subtract its value, and record its
contribution. Because the table includes the subtractive pairs, the
greedy
choice always yields the canonical minimal form. The Python encoder finds the fitting denomination
with max((value, numeral) for ... if value <= number) and builds the string by
appending to a list. The C encoder linearly scans descending parallel arrays
(numeral_values[] / numeral_strings[]), breaking on the first fit, and
accumulates only the length rather than the string, since the problem asks only for character
counts.
Measuring savings. For each line I add len(original) - len(minimal) to
a running total. Lines that are already minimal contribute zero. The Python solution reads the file
with splitlines; the C solution reads the whole file into one buffer and walks it with
pointer arithmetic, skipping \r and \n between lines.