Project Euler Solution 42: Coded triangle numbers

Today we have another I/O problem with a bit of triangle numbers, Problem 42: Coded triangle numbers from the Project Euler series.

The nth term of the sequence of triangle numbers is given by, $t_n = n(n+1)/2$; so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

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 = t_{10}$. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (linked file), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

For reading the words I again use JSON, this makes it so much easier to code.

def read_words() -> list[str]:
    with open("data/p042_words.txt") as f:
        content = f.read()
    return json.loads(f"[{content}]")

Converting the words to numbers is straightforward. One takes the letters and then subtracts the ASCII value for A from that.

def word_to_number(word: str) -> int:
    return sum(ord(c) - ord("A") + 1 for c in word)

We need an efficient check whether a number is a triangle number. We could just generate a handful and check. But there is a bit more elegant way. We have the prescription for triangle numbers as such: $$ t_n = \frac{n(n+1)}{2} \,. $$

We can solve this for $n$ using the abc formula and obtain this: $$ n = \frac{-1 \pm \sqrt{1 + 8 t_n}}{2} \,. $$

The negative branch is not applicable because then $n < 0$. We therefore need to have $1 + 8 t_n$ to be a perfect square and also $-1 - \sqrt{1 + 8 t_n}$ cleanly divisible by 2. Then it is a triangle number.

def is_triangle_number(number: int) -> bool:
    s = int(round(math.sqrt(1 + 8 * number)))
    return s**2 == 1 + 8 * number and (-1 + s) % 2 == 0

With those parts we can just read the words, map them to numbers, filter the triangle numbers into a list and return that length.

def solution() -> int:
    return len(list(filter(is_triangle_number, map(word_to_number, read_words()))))

This runs in 2.0 ms, so it should be fine.