Project Euler Problem 42 Solution: Coded triangle numbers

Project Euler Problem 42 Statement

The n^th term of the sequence of triangle numbers is given by, Triangle number formula ; 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₁₀. If the word value is a triangle number then we shall call the word a triangle word.

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

Solution

We can use some of our understanding from Project Euler 22 to parse and process the list of words (included in the REPL.IT files tab as words.txt). But first, we need to find a way to determine if a number is a triangle number.

If we solve the triangle formula for $n$, then we can test numbers for being a triangle number. Since this is a quadratic equation, we will use the quadratic formula to solve for $n$.

The quadratic formula:

$$ x = \frac{-b\pm\sqrt{b^2 - 4ac}}{2a} $$

Let's put the triangle equation into a recognizable quadratic form using algebra.

$$ \begin{align*}t_n &= \frac{n(n+1)}{2} \\[1ex]2t_n &= n^2 + n \\[1ex]0 &= n^2 + n - 2t_n\end{align*} $$

Using the quadratic formula to solve for $n$ with coefficients: $a = 1$, $b=1$, and $c= -2t_n$

$$ n = \frac{-1\pm\sqrt{1 + 8t_n}}{2} $$

The quadratic formula has two solutions as indicated by the plus–minus symbol "±" in the numerator. We only care about the plus solution as it produces a positive result. We can rearrange the equation to make it more readable.

$$ n = \frac{\sqrt{1 + 8t_n} - 1}{2} $$

The result, $n$, is the index for t_$n$ in the sequence of triangle numbers, which is useful for the Hackerrank version. For example, solving for $t_n = 55$:

$$ \begin{align*}n &=\frac{\sqrt{1 + 8\cdot55} - 1}{2}\\[5pt]10 &= \frac{\sqrt{441} - 1}{2}\end{align*} $$

This codes in Python as a lambda function:

is_tn = lambda t: (sqrt(1 + 8*t) - 1) / 2 % 1 == 0

Given t, if our expression evaluates to an integer, then the number is a triangle number. Only integers mod 1 will evaluate to 0. The == comparison will return a true or false logical condition which is equivalent to a numerical integer 1 or 0, respectively, when used in a calculation.

Next, the quotation marks (") are removed by ignoring the first and last characters of each word as they are split from the input string. One is added every time a word score is tested successfully as a triangle number.

sum(is_tn(score(x[1:-1])) for x in open('words.txt').read().split(','))

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 42

HackerRank Project Euler 42 reduces this exercise to simply identifying a number, 1 ≤ t_n ≤ 10¹⁸, as a triangle number and, if it is, determines its index in the series. Up to ten thousand test cases could be queried.

Python Source Code

from math import sqrt
score = lambda word: sum(ord(c)-ord('A')+1 for c in word)
is_tn = lambda t: (sqrt(1 + 8*t) - 1) / 2 % 1 == 0
print "Number of triangle words =",
print sum(1 for x in open('words.txt').read().split(',') 
    if is_tn(score(x[1:-1])))

Run Project Euler Problem 42 using Python on replit.com.

Last Word

The data file, words.txt, is available on REPL.IT page by clicking the files icon in the top left corner.