notes.html

problem 89 · 62 lines

<article>
<h3>Problem Analysis</h3>
<p>
The task is fundamentally a transcoding exercise: each input line is a valid but possibly wasteful
<a class="reference-source" href="https://en.wikipedia.org/wiki/Roman_numerals" rel="noopener noreferrer" target="_blank">Roman numeral</a>,
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
<em>canonical form</em> 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.
</p>
<p>
The re-encoding step is a
<a class="reference-source" href="https://en.wikipedia.org/wiki/Greedy_algorithm" rel="noopener noreferrer" target="_blank">greedy algorithm</a>:
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.
</p>
<h3>Solution Approach</h3>
<h4>Greedy Parse-then-Encode (Python and C)</h4>
<p>
Both files implement the same two-phase algorithm; I describe it once and note the language
differences afterward.
</p>
<p>
<strong>Phase 1 - parse to integer.</strong> I scan the numeral from right to left, holding the
value of the previously seen (rightmost) symbol in a variable <code>last</code>. For each symbol I
look up its value <code>n</code>: if <code>last &gt; n</code> 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 <code>last</code> by the time I reach the smaller symbol. The Python version iterates over
<code>reversed(numeral)</code> and indexes a <code>dict</code>; the C version uses a backward
<code>for</code> loop and a <code>switch</code> in <code>char_value</code>, which the compiler turns
into a fast jump table.
</p>
<p>
<strong>Phase 2 - encode minimally.</strong> 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
<a class="reference-source" href="https://en.wikipedia.org/wiki/Greedy_algorithm" rel="noopener noreferrer" target="_blank">greedy</a>
choice always yields the canonical minimal form. The Python encoder finds the fitting denomination
with <code>max((value, numeral) for ... if value &lt;= number)</code> and builds the string by
appending to a list. The C encoder linearly scans descending parallel arrays
(<code>numeral_values[]</code> / <code>numeral_strings[]</code>), breaking on the first fit, and
accumulates only the <em>length</em> rather than the string, since the problem asks only for character
counts.
</p>
<p>
<strong>Measuring savings.</strong> For each line I add <code>len(original) - len(minimal)</code> to
a running total. Lines that are already minimal contribute zero. The Python solution reads the file
with <code>splitlines</code>; the C solution reads the whole file into one buffer and walks it with
pointer arithmetic, skipping <code>\r</code> and <code>\n</code> between lines.
</p>
</article>