Problem 42 Project Euler Solution with Python

Coded triangle numbers

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?

This question is pretty simple. You will only have to know that a triangle number n will satisfy the condition of (8n+1) being a perfect square for numbers less than (2⁵³-1 = 9007199254740991. I got to know this from Matlab forum: Best way to determine if given number is triangular.

All the other operations are related to coding stuff which I have explained in program section.

Program

File: pep42.py ------------------------- # http://radiusofcircle.blogpspot.com # time module import time # sqrt for calculating square root from math import sqrt # time at the start of program execution start = time.time() # open the file words.txt f = open('words.txt') # read the whole file words = f.read() # close the file f.close() # split the words into a list words = words.strip().split(',') def convert(character): """function to convert the words to alphabetical position""" return ord(character)-64 # counter to count the number of instances counter = 0 # for loop to loop through the words for word in words: # convert the words to numbers and find the sum x = sum(map(convert, word[1:-1])) # check if the given number is triangle if sqrt(8*x+1) == int(sqrt(8*x+1)): counter += 1 # printing the result print counter # time at the end of program execution end = time.time() # total time taken print end-start

I have used open to do file operations. I am assuming that you know all the file operations.

Function converter will convert the given letter to a alphabetical position of the number. For example converter('A') will return 1, converter('S') will return 19 and so on.

We will loop through the words and map each and every word to converter function. This will return a list with the word converted to their alphabetical positions. Finally sum function will find the sum of the numbers in the list. i.e. we are simply finding the word value in this statement at line 36. For example map(converter,'SKY') will return 55 and so on.

After we have converted the word to word value, we are checking if sqrt(8x+1) is a perfect square or not. i.e. we are checking if the number is triangle number or not.

If the number is a triangle number then you can increase the value of counter.

You can download the source code from Github Gist pep42.py

The source code follows PEP8 standard.

Output

Summary

I don't have any comments on the problem. I am satisfied with the execution time. It has a good performance. I think one can still optimize the code to make it is still faster.

As always you can comment in the comment box below if you have any doubt or didn't understand anything. I will be glad to help you.

Please do comment if you have found any typo or have a different program/better program or have any suggestion. I will be glad to view each of them.

You can also contact me.

Thank you. Have a nice day😃.

RADIUS OF CIRCLE

Search This Blog