[C/C++] Project Euler #42 - Coded Triangle Numbers

Project Euler #42 - Coded Triangle Numbers

This problem does not require a complex algorithm.

As a result, its difficulty level is only 5%.

---

The alphabetical value of a word is defined as follows:
Each letter is assigned a value (A=1, B=2, C=3, …, Z=26), and the word’s alphabetical value is the sum of these values.
For example, the word “SKY” has values S=19, K=11, Y=25, so its alphabetical value is 19 + 11 + 25 = 55.

A triangle number is calculated using the following formula:


\[T_n = \frac{n(n+1)}{2}\]

 

where n is a natural number. The first few triangle numbers are 1, 3, 6, 10, 15, 21, ….

If the alphabetical value of a word matches a triangle number, it is called a “Coded Triangle Number”.

The goal of the problem is to determine how many words in a given list are Coded Triangle Numbers.

---

This problem is relatively simple, and the number of words to check is not very large.

If we convert each English letter into its corresponding number (A→1, B→2, etc.), each word becomes a series of numbers.
Then, we only need to check whether the sum of these numbers is a triangle number.

Since a triangle number is simply the sum of integers from 1 to n, the sequence of triangle numbers is 1, 3, 6, 10, 15, 21, ….

Because the length of each word is not very long, the simplest approach is to precompute a table of triangle numbers and check whether a given sum is in that table.
Even if a word has up to 40 letters, and each letter can have a maximum value of 26, the maximum sum will be around 1200.
So, generating all triangle numbers up to 1200 and checking membership in that set is a straightforward solution.

However, instead of using a lookup table, I implemented a mathematical approach.

Given that each letter in a word has a numerical value cᵢ, we need to determine if there exists an integer n satisfying:

 

\[\frac{n(n+1)}{2} = \sum c_i\]

 

To determine whether an integer n exists, we check if the discriminant is a perfect square.

If the discriminant is a perfect square, n will always be an integer, ensuring that the sum is a triangle number.
The discriminant is always odd, and if it is a perfect square, its square root must also be odd, guaranteeing that n is an integer.

---

Triangle Numbers

---

The resulting implementation is as follows.

//------------------------------------------------
//    Project Euler #42 - Coded Triangle Numbers
//        - by Aubrey Choi
//        - created at 2015-03-29
//------------------------------------------------
#include <stdio.h>
#include <math.h>

int main()
{
    const char *words[] = 
    {
        #include "p042_words.txt"
    };

    int count = 0;

    for( int i = 0 ; i < sizeof(words)/sizeof(char *); i++ )
    {
        int v = 0;
        for( int j = 0 ; words[i][j] ; j++ ) v += words[i][j] - 'A'+1;
        v = 1+8*v;
        int t = sqrt(v);
        if( t*t == v ) count++;
    }
    printf("Ans = %d\n", count);
}