Problem #42 is yet another simple question that involves analyzing a file with tons of data. The question reads:
Project Euler Problem 42: Coded triangle numbers 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?
This problem is genuinely uninteresting. We have already seen plenty of questions involving analyzing text files and triangle numbers. With that being said, here’s my solution:
Solution #1: Brute Force Approach
This time, I stored the text in a file called “PE42Words.txt”. We simply iterate through all of the words in the file. We calculate the total for each word and store the maximum total. Then we generate a list of all triangular numbers up to that maximum total, and we count the number of totals that are in that list. Here’s an implementation of this method in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #42
'''
import time
f = open("PE42Words.txt", "r")
if(f.mode == "r"):
contents = f.readlines()
realContents = []
for x in contents:
realContents.append(x.split(","))
else:
raise ValueError("Cannot read from file")
finalList = realContents[0]
def getValueString(myString):
total = 0
for x in myString:
if("A"<=x<="Z"):
total+=(ord(x)-ord("A")+1)
return total
def projectEulerProblemFortyTwo(myList):
totalsList = []
maxTotal = 0
for x in myList:
a = getValueString(x)
totalsList.append(a)
if(a>maxTotal):
maxTotal = a
triangles = []
c = 1
while(c*(c+1)/2<=maxTotal):
triangles.append(c*(c+1)/2)
c+=1
finalCount = 0
for x in totalsList:
if x in triangles:
finalCount+=1
return finalCount
start = time.time()
print projectEulerProblemFortyTwo(finalList)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
162
--- 0.00270199775696 seconds ---
for input of n = given list of words
'''
As shown above, iteration is a very powerful tool that can be used to solve many interesting problems. Unfortunately, this was not one of them.
Thanks for reading!
The Inner Machinations of Walker 