## Project Euler & HackerRank Problem 42 Solution

##### Coded triangle numbers

by {BetaProjects} | MAY 17, 2009 | Project Euler & HackerRank### Project Euler Problem 42 Statement

The *n*^{th} term of the sequence of triangle numbers is given by, ; 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, 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:

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

Using the quadratic formula to solve for *n* with coefficients: **a** = 1, **b** = 1, and **c** = −2t_{n}

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.

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:

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

*t*≤ 10

_{n}^{18}, 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 icon in the top left corner.