notes.html

problem 22 · 59 lines

<article>
<h3>Problem Analysis</h3>
<p>
This problem contains no number theory, recursion, or combinatorics. It is a pure data-processing
exercise: the answer is a weighted sum where the weight of each name is its rank after sorting.
The "alphabetical value" of a name is the sum of the 1-based positions of its letters in the
alphabet (A=1, B=2, ..., Z=26), and the "name score" multiplies that value by the name's 1-based
position in the sorted list. The final answer sums every name's score. The single insight that
makes the problem tractable is recognising its shape: it is a classic
<a class="reference-source" href="https://en.wikipedia.org/wiki/MapReduce" rel="noopener noreferrer" target="_blank">map-reduce</a>
pipeline - parse the input, sort it, map each element to a score, and reduce the scores to a sum.
</p>
<p>
The complexity is dominated by the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Sorting_algorithm" rel="noopener noreferrer" target="_blank">sort</a>,
which runs in O(n log n) time for n names (here n is roughly 5,000). The scoring pass is O(n * L)
where L is the average name length, which is small and constant in practice. With n this small the
entire computation finishes in well under a millisecond in C and a few milliseconds in Python, so
no clever optimisation is warranted - the goal is simply a clean, correct implementation.
</p>
<h3>Solution Approach</h3>
<h4>Algorithm 0 - Parse, Sort, Score, Sum (Python and C)</h4>
<p>
Both solutions implement the same four-step pipeline and differ only in language mechanics.
</p>
<p>
<strong>Step 1 - Parse.</strong> The file is a single line of comma-separated, double-quoted
tokens such as <code>"AARON","ABBEY",...</code>. In Python I read the whole file and call
<code>.split(",")</code> to obtain a list of raw tokens (quotes still attached). In C I read the
file into one buffer and use <code>strtok</code> with <code>","</code> as the delimiter to split
in place. Before tokenising in C, I make a single linear pass counting commas so I can allocate the
<code>char **names</code> pointer array exactly once - one cheap scan avoids any dynamic regrowth.
</p>
<p>
<strong>Step 2 - Sort.</strong> Python's <code>sorted()</code> uses
<a class="reference-source" href="https://en.wikipedia.org/wiki/Timsort" rel="noopener noreferrer" target="_blank">Timsort</a>,
a stable O(n log n) sort. In C I call
<a class="reference-source" href="https://en.wikipedia.org/wiki/Qsort" rel="noopener noreferrer" target="_blank">qsort</a>
with a comparator that dereferences the <code>char **</code> arguments and calls
<a class="reference-source" href="https://en.wikipedia.org/wiki/C_string_handling#strcmp" rel="noopener noreferrer" target="_blank">strcmp</a>.
A subtle but important point: every token still carries its surrounding double-quotes at this
stage. Because all tokens begin with the same quote character, the quotes contribute equally to
every comparison and cancel out - the sort order is identical to sorting the bare names, so no
preprocessing is required before the sort.
</p>
<p>
<strong>Step 3 - Score.</strong> I iterate over the sorted list with a 1-based index. The helper
<code>word_to_num</code> sums each letter's alphabet position using <code>ord(c) - 64</code>
(Python) or <code>*c - 64</code> (C), skipping the quote and space characters. Since ASCII 'A' is
65, subtracting 64 maps 'A' to 1 directly - no lookup table needed.
</p>
<p>
<strong>Step 4 - Sum.</strong> Each name's value is multiplied by its rank and accumulated. The C
version uses a <code>long long</code> accumulator: the total is around 8.7 x 10^8, which fits in a
32-bit signed integer, but I use 64-bit to remove any doubt about overflow. Python integers are
arbitrary precision, so the concern does not arise.
</p>
</article>