I solved a couple of sums from the Project Euler archives and feel quite stupid since this is the first time in the last few weeks that a post has some code in it. I really ought to improve my efficiency. Well, the first sum I did was no. 42 and extremely special since it is the ultimate answer to the ultimate question. Well, the question was:
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?
So, I whipped up a solution in no time. I was only hindered when it came to figuring out whether a number was a perfect square or not and I was trying to explore better algorithms that mine which involved squaring the integral part of the square root of type float obtained by using math.sqrt(num) and squaring this integral part to see if we return to the original number again. I couldn’t really find a decent solution so I just implemented my own answer:
#Author: Shriphani Palakodety
#Example 42, Project Euler Archives.
import string
import math
def makeAlphaDict():
alpha_dict = {}
for i in range(len(string.uppercase)):
alpha_dict[string.uppercase[i]] = i + 1
return alpha_dict
alpha_dict = makeAlphaDict()
def checkTriangular(word):
word_sum = 0
for char in word:
if char == ‘"’:
continue
else:
word_sum += alpha_dict[char]
discrmnt = 8 * word_sum + 1
if checkOdd(int(math.sqrt(discrmnt))) == True and checkPerfSquare(discrmnt) == True:
return True
else:
return False
def checkPerfSquare(num):
probable = int(math.sqrt(num))
if probable * probable == num:
return True
else:
return False
def checkOdd(num):
if num % 2 == 0:
return False
else:
return True
input = open("words.txt", "r")
words_list = input.readlines()[0].split(",")
input.close()
word_count = 0
for word in words_list:
print word
if checkTriangular(word) == True:
word_count += 1
else:
continue
print word_count
Thats the first question. The next problem I solved was #53;
How many values of nCr, for 1 ? n ? 100, are greater than one-million?
Since is a symmetric function about the middle term while r increases from 0 to n, I figured out that once we hit upon one (n, r) pair, without computing the rest, we could obtain the other values of r for a fixed value of n that crossed the million mark. Remember, if n is even, the number of terms is odd and if n is odd, number of terms is even. In case the number of terms is even, the middle terms are
and
. In case, the number of terms is odd, the middle term is
. Using just these three I could get to the solution in no time. Here is the code:
#Author: Shriphani Palakodety
#Project Euler Problem 53
def factorial(number):
if number == 0 or number == 1:
return 1
else:
return number * factorial(number - 1)
def combination(n, r):
n_fact = factorial(n)
r_fact = factorial(r)
n_r_fact = factorial(n - r)
return n_fact / (r_fact * n_r_fact)
def midTerm(n):
if n % 2 == 0:
mid_term_1 = n / 2
return mid_term_1
else:
mid_term = (n + 1) / 2
return mid_term
comb_num = 0
def countComb(n, r):
”‘If a particular value is found to be greater than 0,
it adds a certain number to comb_sum using properties of
combinatorics.’”
if n % 2 != 0:
num_to_add = 2 * (n / 2 - r + 1)
return num_to_add
else:
num_to_add = 2 * ((n+1)/2 - r) + 1
return num_to_add
for n in range(101):
for r in range(midTerm(n) + 1):
if combination(n, r) > 1000000:
comb_num += countComb(n, r)
break
else:
continue
print comb_num
Thats the solution. And of course, who’ll forget the time taken to get to the solution.
shriphani@psp-laptop:~/project_euler$ time python ex53.py 4075 real 0m1.116s user 0m0.140s sys 0m0.024s shriphani@psp-laptop:~/project_euler$
Till the next time I put up a post, HAPPY CODING !
0 comments ↓
There are no comments yet...Kick things off by filling out the form below.
Leave a Comment