notes.html

problem 42 · 13 lines

<article>
<h3>Problem Analysis</h3>
<p>This problem fuses a simple string-processing task with a number-theoretic membership test. For each word I compute a "word value" by mapping each letter to its 1-based alphabetical position (A=1, ..., Z=26) and summing those positions. I then ask whether that sum is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Triangular_number" rel="noopener noreferrer" target="_blank">triangular number</a> - a number of the form t(n) = n(n+1)/2 for some positive integer n, which counts the dots in an equilateral triangular arrangement.</p>
<p>The observation that makes the test cheap is that I never need to build a table of <a class="reference-source" href="https://en.wikipedia.org/wiki/Triangular_number" rel="noopener noreferrer" target="_blank">triangular numbers</a>. Because t(n) is a closed-form quadratic, I can invert it: setting n(n+1)/2 = k and solving the <a class="reference-source" href="https://en.wikipedia.org/wiki/Quadratic_equation" rel="noopener noreferrer" target="_blank">quadratic</a> n^2 + n - 2k = 0 with the <a class="reference-source" href="https://en.wikipedia.org/wiki/Quadratic_formula" rel="noopener noreferrer" target="_blank">quadratic formula</a> gives the positive root n = (-1 + sqrt(1 + 8k)) / 2. That n is a whole number exactly when 1 + 8k is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Square_number" rel="noopener noreferrer" target="_blank">perfect square</a>. So "is k triangular?" reduces to "is 8k+1 a perfect square?" - a constant-time test requiring no precomputation and no chosen upper bound. With roughly two thousand words and each word value bounded well under a few hundred, the work is O(W * L) where W is the word count and L the average word length: linear, and dominated entirely by file I/O and parsing. Both implementations finish in well under a millisecond.</p>
<h3>Solution Approach</h3>
<h4>Direct Triangle Test via Perfect-Square Check (Python and C)</h4>
<p>Both files implement the same three-step algorithm; only the language mechanics differ.</p>
<p><strong>Step 1 - load and split.</strong> I read the whole file into memory as one string, then split it on commas to recover each quoted word. I chose in-memory splitting over line-by-line reading because the file uses commas, not newlines, as its sole delimiter. In Python this is <code>str.split(",")</code>. In C I use <a class="reference-source" href="https://man7.org/linux/man-pages/man3/strtok_r.3.html" rel="noopener noreferrer" target="_blank">strtok_r</a>, the re-entrant variant of <code>strtok</code>, which walks the buffer and writes null terminators in place - cheap because no per-token allocation is needed.</p>
<p><strong>Step 2 - score each word.</strong> I strip quote characters and whitespace, then map each remaining letter to its position by subtracting the code point just below 'A'. In Python this is <code>ord(c) - 64</code> (since <code>ord('A')</code> is 65), wrapped in a generator expression fed to <code>sum</code>. In C it is <code>*c - 'A' + 1</code> inside an explicit loop; the C version also handles lowercase defensively with a parallel <code>*c - 'a' + 1</code> branch. The Python scoring function carries an <a class="reference-source" href="https://docs.python.org/3/library/functools.html#functools.lru_cache" rel="noopener noreferrer" target="_blank">lru_cache</a> decorator, which memoises results - harmless here and a sensible default for a pure function called in a loop.</p>
<p><strong>Step 3 - triangle test.</strong> I check whether <code>8*n + 1</code> is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Square_number" rel="noopener noreferrer" target="_blank">perfect square</a>. In Python I compute <code>(8*n + 1) ** 0.5</code> and call <code>float.is_integer()</code> on it; this is safe because all word values are small enough for the double-precision square root to be exact. In C I take <code>sqrt</code>, round to the nearest integer with <code>round</code>, then square that integer back and compare against <code>8*n + 1</code> using 64-bit integer arithmetic. That round-trip guards against any <a class="reference-source" href="https://en.wikipedia.org/wiki/Floating-point_arithmetic" rel="noopener noreferrer" target="_blank">floating-point</a> rounding error.</p>
<p>The final answer is the count of words passing the test - tallied via <code>sum</code> over a boolean generator in Python, and via an explicit counter in C.</p>
</article>