Project Euler 42: Count how many 'triangle words' a list of common English words contain

Project Euler 42 Problem Description

Project Euler 42: The n^th term of the sequence of triangle numbers is given by, t_n = ½n(n+1); 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 (right click and ‘Save Link/Target As…’), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

Analysis

We can use some of our understanding from Project Euler 22 to parse and process this list of words (included in the Trinket tab as words.txt next to the main.py tab). But first, we will need a way to determine if a number is a trianglular number.

If we solve the triangle formula, introduced above in the problem statement, for n then we can test numbers for being a trianglular number when n evaluates as an integer. Since this is a quadratic equation, we will need to use the quadratic formula to solve for n.

Quadratic formula:

Let’s calculate the coefficients a, b, and c first.

Let’s use the quadratic equation to solve for n as coefficients: a = 1, b = 1, and c = -2t_n

This codes in Python as:

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

Where t is some number we want to test for being a trianglular number. When our expression evaluates to an integer, i.e. evaluates to zero after being modded by 1, then the number is a trianglular number. Only integers mod 1 will evaluate to 0.

Next, the quotation marks (“) are removed by ignoring the first and last characters of each word as they are split from the input string. A word score is calculated and then tested for being a trianglular number. If it is then the is_tn() function returns True (numerically interpreted as 1) otherwise it returns False (numerically interpreted as 0) and added to the sum.

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

This solution easily solves HackerRank Project Euler 42 which requires us to test 100,000 numbers up to 10¹⁸ for being a triangular number. If it is then we print it’s index and if it is not then we print -1. So, 2 would print -1 and 55 would print 10.

This program and method
solves all test cases for
Project Euler 42 on HackerRank

Project Euler 42 Solution

Afterthoughts

• See also, Project Euler 22 Solution:
  
• Backup copy of words.txt file from Project Euler site.