Problem 42 — Coded Triangle Numbers

solved Thu, 5 Dec 2019, 10:28 · level 0 · difficulty 2% projecteuler.net github

The $n$th term of the sequence of triangle numbers is given by, $t_n = \frac12n(n+1)$; so the first ten triangle numbers are: $$1, 3, 6, 10, 15, 21, 28, 36, 45, 55, \dots$$

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is $19 + 11 + 25 = 55 = t_{10}$. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?


Problem Analysis

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 triangular number - 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.

The observation that makes the test cheap is that I never need to build a table of triangular numbers. Because t(n) is a closed-form quadratic, I can invert it: setting n(n+1)/2 = k and solving the quadratic n^2 + n - 2k = 0 with the quadratic formula gives the positive root n = (-1 + sqrt(1 + 8k)) / 2. That n is a whole number exactly when 1 + 8k is a perfect square. 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.

Solution Approach

Direct Triangle Test via Perfect-Square Check (Python and C)

Both files implement the same three-step algorithm; only the language mechanics differ.

Step 1 - load and split. 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 str.split(","). In C I use strtok_r, the re-entrant variant of strtok, which walks the buffer and writes null terminators in place - cheap because no per-token allocation is needed.

Step 2 - score each word. 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 ord(c) - 64 (since ord('A') is 65), wrapped in a generator expression fed to sum. In C it is *c - 'A' + 1 inside an explicit loop; the C version also handles lowercase defensively with a parallel *c - 'a' + 1 branch. The Python scoring function carries an lru_cache decorator, which memoises results - harmless here and a sensible default for a pure function called in a loop.

Step 3 - triangle test. I check whether 8*n + 1 is a perfect square. In Python I compute (8*n + 1) ** 0.5 and call float.is_integer() 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 sqrt, round to the nearest integer with round, then square that integer back and compare against 8*n + 1 using 64-bit integer arithmetic. That round-trip guards against any floating-point rounding error.

The final answer is the count of words passing the test - tallied via sum over a boolean generator in Python, and via an explicit counter in C.

workbench

Test cases

categoryinputanswer
main file_url = https://projecteuler.net/resources/documents/0042_words.txt 162

Results

solutioncategoryanswerverdict avg seconds cavg seconds py
p0042_s0 main 162 correct 0.000072 (63) 0.000493 (63)

Files

Tags & blogs