Project Euler/42

Problem Statement

The nth term of the sequence of triangle numbers is given by:

$ t_n = \frac{1}{2} n (n + 1) $

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 (A=1, B=2, ..., Z=26) 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 the word is called a triangle word.

Using words.txt, a 16K text file containing nearly two-thousand common English words, find the number of triangle words.

Approach

Pre-compute Triangle Numbers

Generate all triangle numbers up to a sufficient bound. The longest word in the file yields a word value well under 5,000, so pre-computing triangle numbers for n = 1 to 100 (giving t_{100} = 5050) is more than adequate. Store these in a HashSet for O(1) lookup.

Parse the Word File

The file words.txt contains comma-separated, double-quoted words (e.g., "A","ABILITY","ABLE",...). Split on commas, strip the surrounding quotes, and trim whitespace.

Compute Word Values

For each word:

• Convert to uppercase
• Iterate over each character, computing its value as (c - 'A' + 1)
• Sum all character values to obtain the word value

Check Against Triangle Numbers

If the word value is contained in the pre-computed set of triangle numbers, increment the count.

Return the Count

After processing all words, return the total count of triangle words.

Solution

Link: https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem042.java