Detailed mathematical approach

Problem Summary

Each word in the given list is converted into a word value by replacing every letter with its alphabetical position and adding the results. Thus \(A=1\), \(B=2\), ..., \(Z=26\), and a word \(w\) receives the value

$V(w)=\sum_{c \in w}\operatorname{pos}(c).$

A word is called a triangle word when its value is a triangular number, that is, one of the numbers

$T_n=\frac{n(n+1)}{2}\qquad(n \ge 1).$

The task is to count how many words in the supplied list satisfy \(V(w)=T_n\) for some \(n\).

Mathematical Approach

The implementations do not test each word value with a separate quadratic check. Instead, they build the finite set of all triangular numbers that could possibly occur, and then reduce the problem to repeated set membership.

Word values are additive

If a word is written as \(w=c_1c_2\cdots c_\ell\), then its value is simply

$V(w)=\operatorname{pos}(c_1)+\operatorname{pos}(c_2)+\cdots+\operatorname{pos}(c_\ell).$

This is the only numerical object attached to a word. Once \(V(w)\) is known, the original ordering of the letters no longer matters for the triangle-word test.

Only finitely many triangular numbers matter

Let

$M=\max_w V(w)$

be the largest word value appearing in the input. Any triangle word must have value in the set

$\mathcal{T}(M)=\left\{T_n=\frac{n(n+1)}{2}: T_n \le M\right\}.$

This works because the triangular numbers form a strictly increasing sequence. Once \(T_n\gt M\), every later triangular number is even larger, so it cannot match any word value from the file. The problem therefore collapses to a finite lookup problem.

The bound is small: the number of relevant triangular numbers is the largest \(n\) with \(n(n+1)/2 \le M\), which is \(O(\sqrt{M})\).

Worked example: why "SKY" qualifies

The standard example is the word "SKY". Its letters contribute

$S=19,\qquad K=11,\qquad Y=25,$

so

$V(\text{SKY})=19+11+25=55.$

Now compare this with the triangular sequence:

$1,3,6,10,15,21,28,36,45,55,\dots$

Since \(55=T_{10}\), "SKY" is a triangle word. The same logic applies to every other word in the list: compute its value once, then ask whether that value belongs to \(\mathcal{T}(M)\).

The final counting formula

If the input words are \(w_1,w_2,\dots,w_N\), then the answer is

$\sum_{i=1}^{N}\mathbf{1}_{\{V(w_i)\in \mathcal{T}(M)\}},$

where the indicator is 1 exactly when the word value is triangular. There is no deeper recurrence or search tree hidden here: the mathematical core is to replace repeated triangular-number tests by one precomputed finite set.

How the Code Works

Parsing the word list

The input is a single comma-separated line whose words are enclosed in double quotes. The implementations scan the text character by character, switch an "inside quotes" state on and off when they meet a quote, and collect characters only while that state is active. Every time a closing quote is reached, one complete word is stored.

Computing values and the global bound

After parsing, the implementation evaluates each word by summing the contributions of its uppercase letters from \(1\) through \(26\). During that same pass it records the maximum word value \(M\). This maximum is the key invariant for the rest of the algorithm: no triangular number above \(M\) can ever be useful.

Precomputing the triangle set and counting

Next, the implementation generates

$1,\ 3,\ 6,\ 10,\ \dots,\ \frac{n(n+1)}{2}$

until the values exceed \(M\), storing every valid triangular number in a hash-based set. A second pass over the parsed words recomputes each word value and checks whether it belongs to that set. The total number of successful lookups is the required answer.

The C++, Python, and Java implementations also include small sanity checks around this logic, such as verifying that "SKY" has value \(55\) and that \(55\) appears in the triangular set while \(54\) does not.

Complexity Analysis

Let \(N\) be the number of words, let \(C=\sum_{i=1}^{N}|w_i|\) be the total number of letters across all words, and let \(K=\max\{n:T_n\le M\}\). Parsing the input costs \(O(C)\). The first pass that computes word values and finds \(M\) also costs \(O(C)\). Building the triangular set costs \(O(K)=O(\sqrt{M})\). The second pass that counts triangle words is again \(O(C)\).

So the overall running time is

$O(C+\sqrt{M}),$

with the linear scans over the letters dominating in practice. The implementations store the parsed words explicitly, so the space usage is \(O(C+\sqrt{M})\): \(O(C)\) for the words themselves and \(O(\sqrt{M})\) for the set of triangular numbers up to the maximum word value.

Footnotes and References

1. Project Euler, Problem 42: Coded Triangle Numbers
2. Wikipedia: Triangular number
3. MathWorld: Triangular Number
4. Wikipedia: Comma-separated values