Tim Varley Logo
Tim Varley Systems Engineer
Problem #42 hard

Coded Triangle Numbers

View on Project Euler

The nnth term of the sequence of triangle numbers is given by, tn=12n(n+1)t_n = \frac12n(n+1); so the first ten triangle numbers are: 1,3,6,10,15,21,28,36,45,55,…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=t1019 + 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?

Implementations

cpp
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>


bool is_triangle(long long n) {
    double k = (-1 + sqrt(1 + 8 * n)) / 2;
    return k == floor(k);
}


long long word_value(const std::string& word) {
    long long sum = 0;
    for (char c : word) {
        sum += c - 'A' + 1;
    }
    return sum;
}


long long triangle_words() {
    std::ifstream file("src/0042_words.txt");
    if (!file) return 0;
    std::string line;
    std::getline(file, line);
    std::vector<std::string> words;
    std::string word;
    for (char c : line) {
        if (c == '"') {
            if (!word.empty()) {
                words.push_back(word);
                word.clear();
            }
        } else if (c != ',') {
            word += c;
        }
    }
    if (!word.empty()) words.push_back(word);
    long long count = 0;
    for (const auto& w : words) {
        long long val = word_value(w);
        if (is_triangle(val)) count++;
    }
    return count;
}


#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[]) {
    std::cout << triangle_words() << std::endl;
}
#endif // UNITTEST_MODE

Solution Notes

Mathematical Background

Triangle numbers are generated by the formula tn=n(n+1)2t_n = \frac{n(n+1)}{2}.

The first ten triangle numbers are 1, 3, 6, 10, 15, 21, 28, 36, 45, 55.

A word value is calculated by summing the alphabetical positions of its letters (A=1, B=2, …, Z=26).

For example, SKY = 19 + 11 + 25 = 55.

A triangle word is a word whose value is a triangle number.

Algorithm Analysis

The solution reads a list of words, computes each word’s value, and counts how many values are triangle numbers.

Triangle numbers are checked using the inverse formula: for a number x, solve k(k+1)2=x\frac{k(k+1)}{2} = x for integer k.

This gives the quadratic equation k2+k−2x=0k^2 + k - 2x = 0, solved as k=−1+1+8x2k = \frac{-1 + \sqrt{1 + 8x}}{2}.

If k is an integer, x is triangular.

Performance Analysis

  • Time Complexity: O(n × m) where n is the number of words (≈2000) and m is the average word length (≈8), resulting in ~16,000 operations.

  • Space Complexity: O(n) for storing the word list.

  • Execution Time: Very fast (<1 millisecond), suitable for real-time processing.

  • Scalability: Linear growth with input size, efficient for large word lists.

Key Insights

  • The triangle number check is O(1) per word using the quadratic formula solution

  • File I/O is a significant part of the implementation complexity

  • The problem demonstrates the connection between number theory and text processing

  • No optimization is needed for the given constraints (2000 words)

Educational Value

This problem teaches:

  • String processing and character encoding (ASCII/Unicode)

  • Mathematical formula manipulation and inverse calculations

  • File input/output operations in programming

  • The intersection of number theory and computational text analysis

  • Efficient checking of number properties using closed-form solutions