linkProblem 42 - Coded Triangle Numbers

linkQuestion

The nth term of the sequence of triangle numbers is given by, tn = ½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 = t10. 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?

linkSolution

euler_042.py
1linkimport string

2link

3linkdef is_triangular(x):

4link    if (((8*x) + 1)**0.5) % 1 == 0:

5link        return True

6link    else:

7link        return False

8link

9linkdef word_to_number(word):

10link    alphabet = list(string.ascii_lowercase)

11link

12link    sum_of_positions = 0

13link    for w in word:

14link        position = alphabet.index(w.lower()) + 1

15link        sum_of_positions += position

16link

17link    return sum_of_positions

18link

19linkwith open("p042_words.txt", 'r') as f:

20link    words = f.read().replace('"', '')

21link

22linktriangle_count = 0

23linkfor w in words.split(","):

24link    value = word_to_number(w)

25link    if is_triangular(value):

26link        triangle_count += 1

linkDiscussion

• To identify if a number is triangular or not, we make use of this function. This formula was derived from Triangular Roots and Tests. It states that an integer x is triangular if and only if 8x+1 is a square.
• We can get a number's square root by using ** 0.5 and to check if it is a whole number or not, we compare it to % 1 == 0.
  Sample usage:chevron_right

  1linkx = 3
  
  2link(((8*3) + 1) ** 0.5) % 1 == 0
  
  3link((24 + 1) ** 0.5) % 1 == 0
  
  4link(25 ** 0.5) % 1 == 0
  
  5link5 % 1 == 0
  
  6link0 == 0
  
  7link# 3 is a triangle number
  
  8link
  
  9linkx = 4
  
  10link((32 + 1) ** 0.5) % 1 == 0
  
  11link(33 ** 0.5) % 1 == 0
  
  12link5.75 % 1 == 0
  
  13link0.75 == 0
  
  14link# 4 is not a triangle number
  
  

• To convert each letter to a number corresponding to its alphabetical position, we use this function.
  • alphabet is a list of characters that will help us identify a letter's position (['a', 'b', 'c', ...])
  • We iterate through each of the letters of the word and identify its position by getting its index in the list and adding 1 (since indices start from zero). .lower() was used because alphabet is a list of characters in lower case.
  • The positions are then added together to get the sum.
• We open the file that contains the words that needs to be processed. It is stored in words, and the enclosing " are removed to make string parsing easier.
• To go through each word, we split words into a list.
• We then get the value of each word, and finally check if it is a triangle number or not.

linkAnswer