Project Euler Problem 42 Solution

Project Euler & HackerRank Problem 42 Solution

Coded triangle numbers
by {BetaProjects} | MAY 17, 2009 | Project Euler & HackerRank

Project Euler Problem 42 Statement

The nth 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 = t10. 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:

Quadratic formula

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 = −2tn

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 tn in the sequence of triangle numbers, which is useful for the Hackerrank version. For example, solving for tn = 55:

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

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

HackerRank reduces this exercise to simply determining if a number, 1 ≤ tn ≤ 1018, is a triangle number and, if it is, determine its index in the series. Up to ten thousand test cases could be queried.

Python Source Code

Last Word

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