Problem 42: Coded Triangle Numbers

View on Project Euler

Project Euler Problem 42 Solution

EulerSolve provides an optimized solution for Project Euler Problem 42, Coded Triangle Numbers, with C++, Python, Java, and a step-by-step mathematical explanation.

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

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

Problem 42 source code

C++

#include <algorithm>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <unordered_set>
#include <vector>

namespace {

using i64 = std::int64_t;

struct Options {
    std::string words_file = "resources/documents/0042_words.txt";
    bool run_checkpoints = true;
};

bool parse_string_after_prefix(const std::string& arg,
                               const std::string& prefix,
                               std::string& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    value = tail;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_string_after_prefix(arg, "--words-file=", options.words_file)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return true;
}

std::vector<std::string> parse_csv_words(const std::string& payload) {
    std::vector<std::string> words;
    std::string current;
    bool inside_quotes = false;

    for (char c : payload) {
        if (c == '"') {
            inside_quotes = !inside_quotes;
            if (!inside_quotes) {
                words.push_back(current);
                current.clear();
            }
            continue;
        }
        if (inside_quotes) {
            current.push_back(c);
        }
    }

    return words;
}

int word_value(const std::string& word) {
    int value = 0;
    for (char c : word) {
        if (c >= 'A' && c <= 'Z') {
            value += c - 'A' + 1;
        }
    }
    return value;
}

std::unordered_set<int> triangle_set_up_to(const int limit) {
    std::unordered_set<int> triangles;
    for (int n = 1;; ++n) {
        const int t = n * (n + 1) / 2;
        if (t > limit) {
            break;
        }
        triangles.insert(t);
    }
    return triangles;
}

int solve(const std::string& words_file) {
    std::ifstream input(words_file);
    if (!input) {
        throw std::runtime_error("Could not open words file: " + words_file);
    }

    std::ostringstream buf;
    buf << input.rdbuf();
    const std::vector<std::string> words = parse_csv_words(buf.str());

    int max_word_value = 0;
    for (const std::string& w : words) {
        max_word_value = std::max(max_word_value, word_value(w));
    }

    const auto triangles = triangle_set_up_to(max_word_value);

    int count = 0;
    for (const std::string& w : words) {
        if (triangles.count(word_value(w)) > 0U) {
            ++count;
        }
    }

    return count;
}

bool run_checkpoints() {
    if (word_value("SKY") != 55) {
        std::cerr << "Checkpoint failed for SKY value" << '\n';
        return false;
    }
    const auto triangles = triangle_set_up_to(100);
    if (triangles.count(55) == 0U || triangles.count(54) != 0U) {
        std::cerr << "Checkpoint failed for triangle-number set" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    try {
        std::cout << solve(options.words_file) << '\n';
    } catch (const std::exception& ex) {
        std::cerr << ex.what() << '\n';
        return 3;
    }

    return 0;
}

Python

import sys
import os

def parse_string_after_prefix(arg, prefix):
    if not arg.startswith(prefix):
        return False, ""
    tail = arg[len(prefix):]
    if not tail:
        return False, ""
    return True, tail

def parse_arguments(args):
    options = {
        "words_file": "resources/documents/0042_words.txt",
        "run_checkpoints": True
    }
    
    i = 1
    while i < len(args):
        arg = args[i]
        if arg == "--skip-checkpoints":
            options["run_checkpoints"] = False
            i += 1
            continue
        
        found, value = parse_string_after_prefix(arg, "--words-file=")
        if found:
            options["words_file"] = value
            i += 1
            continue
        
        print(f"Unknown argument: {arg}", file=sys.stderr)
        return None, False
    
    return options, True

def parse_csv_words(payload):
    words = []
    current = ""
    inside_quotes = False
    
    for c in payload:
        if c == '"':
            inside_quotes = not inside_quotes
            if not inside_quotes:
                words.append(current)
                current = ""
            continue
        
        if inside_quotes:
            current += c
    
    return words

def word_value(word):
    value = 0
    for c in word:
        if 'A' <= c <= 'Z':
            value += ord(c) - ord('A') + 1
    return value

def triangle_set_up_to(limit):
    triangles = set()
    n = 1
    while True:
        t = n * (n + 1) // 2
        if t > limit:
            break
        triangles.add(t)
        n += 1
    return triangles

def solve(words_file):
    try:
        with open(words_file, 'r') as f:
            content = f.read()
    except Exception as e:
        raise RuntimeError(f"Could not open words file: {words_file}")
    
    words = parse_csv_words(content)
    
    max_word_value = 0
    for w in words:
        current_value = word_value(w)
        if current_value > max_word_value:
            max_word_value = current_value
    
    triangles = triangle_set_up_to(max_word_value)
    
    count = 0
    for w in words:
        if word_value(w) in triangles:
            count += 1
    
    return count

def run_checkpoints():
    if word_value("SKY") != 55:
        print("Checkpoint failed for SKY value", file=sys.stderr)
        return False
    
    triangles = triangle_set_up_to(100)
    if 55 not in triangles or 54 in triangles:
        print("Checkpoint failed for triangle-number set", file=sys.stderr)
        return False
    
    return True

def main():
    args = sys.argv
    options, success = parse_arguments(args)
    
    if not success:
        sys.exit(1)
    
    if options["run_checkpoints"] and not run_checkpoints():
        sys.exit(2)
    
    try:
        result = solve(options["words_file"])
        print(result)
    except Exception as ex:
        print(str(ex), file=sys.stderr)
        sys.exit(3)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Euler42 {

    private static class Options {
        String wordsFile = "resources/documents/0042_words.txt";
        boolean runCheckpoints = true;
    }

    private static boolean parseStringAfterPrefix(String arg, String prefix, StringBuilder value) {
        if (!arg.startsWith(prefix)) {
            return false;
        }
        String tail = arg.substring(prefix.length());
        if (tail.isEmpty()) {
            return false;
        }
        value.setLength(0);
        value.append(tail);
        return true;
    }

    private static boolean parseArguments(String[] args, Options options) {
        for (String arg : args) {
            if ("--skip-checkpoints".equals(arg)) {
                options.runCheckpoints = false;
                continue;
            }
            StringBuilder value = new StringBuilder();
            if (parseStringAfterPrefix(arg, "--words-file=", value)) {
                options.wordsFile = value.toString();
                continue;
            }
            System.err.println("Unknown argument: " + arg);
            return false;
        }
        return true;
    }

    private static List<String> parseCsvWords(String payload) {
        List<String> words = new ArrayList<>();
        StringBuilder current = new StringBuilder();
        boolean insideQuotes = false;

        for (char c : payload.toCharArray()) {
            if (c == '"') {
                insideQuotes = !insideQuotes;
                if (!insideQuotes) {
                    words.add(current.toString());
                    current.setLength(0);
                }
                continue;
            }
            if (insideQuotes) {
                current.append(c);
            }
        }

        return words;
    }

    private static int wordValue(String word) {
        int value = 0;
        for (char c : word.toCharArray()) {
            if (c >= 'A' && c <= 'Z') {
                value += c - 'A' + 1;
            }
        }
        return value;
    }

    private static Set<Integer> triangleSetUpTo(int limit) {
        Set<Integer> triangles = new HashSet<>();
        for (int n = 1; ; ++n) {
            int t = n * (n + 1) / 2;
            if (t > limit) {
                break;
            }
            triangles.add(t);
        }
        return triangles;
    }

    private static int solve(String wordsFile) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader(wordsFile));
        StringBuilder buf = new StringBuilder();
        String line;
        while ((line = reader.readLine()) != null) {
            buf.append(line);
        }
        reader.close();

        List<String> words = parseCsvWords(buf.toString());

        int maxWordValue = 0;
        for (String w : words) {
            maxWordValue = Math.max(maxWordValue, wordValue(w));
        }

        Set<Integer> triangles = triangleSetUpTo(maxWordValue);

        int count = 0;
        for (String w : words) {
            if (triangles.contains(wordValue(w))) {
                ++count;
            }
        }

        return count;
    }

    private static boolean runCheckpoints() {
        if (wordValue("SKY") != 55) {
            System.err.println("Checkpoint failed for SKY value");
            return false;
        }
        Set<Integer> triangles = triangleSetUpTo(100);
        if (!triangles.contains(55) || triangles.contains(54)) {
            System.err.println("Checkpoint failed for triangle-number set");
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Options options = new Options();
        if (!parseArguments(args, options)) {
            System.exit(1);
        }
        if (options.runCheckpoints && !runCheckpoints()) {
            System.exit(2);
        }

        try {
            System.out.println(solve(options.wordsFile));
        } catch (Exception ex) {
            System.err.println(ex.getMessage());
            System.exit(3);
        }
    }
}