In my attempt to learn (Iron)Python out in the open, here’s my solution for Project Euler Problem 13.
As always, any feedback is welcome.
# Euler 13
# http://projecteuler.net/index.php?section=problems&id=13
# Work out the first ten digits of the sum of the
# following one-hundred 50-digit numbers.
import time
start = time.time()
number_string = '\
37107287533902102798797998220837590246510135740250\
46376937677490009712648124896970078050417018260538\
74324986199524741059474233309513058123726617309629\
91942213363574161572522430563301811072406154908250\
23067588207539346171171980310421047513778063246676\
89261670696623633820136378418383684178734361726757\
28112879812849979408065481931592621691275889832738\
44274228917432520321923589422876796487670272189318\
47451445736001306439091167216856844588711603153276\
70386486105843025439939619828917593665686757934951\
62176457141856560629502157223196586755079324193331\
64906352462741904929101432445813822663347944758178\
92575867718337217661963751590579239728245598838407\
58203565325359399008402633568948830189458628227828\
80181199384826282014278194139940567587151170094390\
35398664372827112653829987240784473053190104293586\
86515506006295864861532075273371959191420517255829\
71693888707715466499115593487603532921714970056938\
54370070576826684624621495650076471787294438377604\
53282654108756828443191190634694037855217779295145\
36123272525000296071075082563815656710885258350721\
45876576172410976447339110607218265236877223636045\
17423706905851860660448207621209813287860733969412\
81142660418086830619328460811191061556940512689692\
51934325451728388641918047049293215058642563049483\
62467221648435076201727918039944693004732956340691\
15732444386908125794514089057706229429197107928209\
55037687525678773091862540744969844508330393682126\
18336384825330154686196124348767681297534375946515\
80386287592878490201521685554828717201219257766954\
78182833757993103614740356856449095527097864797581\
16726320100436897842553539920931837441497806860984\
48403098129077791799088218795327364475675590848030\
87086987551392711854517078544161852424320693150332\
59959406895756536782107074926966537676326235447210\
69793950679652694742597709739166693763042633987085\
41052684708299085211399427365734116182760315001271\
65378607361501080857009149939512557028198746004375\
35829035317434717326932123578154982629742552737307\
94953759765105305946966067683156574377167401875275\
88902802571733229619176668713819931811048770190271\
25267680276078003013678680992525463401061632866526\
36270218540497705585629946580636237993140746255962\
24074486908231174977792365466257246923322810917141\
91430288197103288597806669760892938638285025333403\
34413065578016127815921815005561868836468420090470\
23053081172816430487623791969842487255036638784583\
11487696932154902810424020138335124462181441773470\
63783299490636259666498587618221225225512486764533\
67720186971698544312419572409913959008952310058822\
95548255300263520781532296796249481641953868218774\
76085327132285723110424803456124867697064507995236\
37774242535411291684276865538926205024910326572967\
23701913275725675285653248258265463092207058596522\
29798860272258331913126375147341994889534765745501\
18495701454879288984856827726077713721403798879715\
38298203783031473527721580348144513491373226651381\
34829543829199918180278916522431027392251122869539\
40957953066405232632538044100059654939159879593635\
29746152185502371307642255121183693803580388584903\
41698116222072977186158236678424689157993532961922\
62467957194401269043877107275048102390895523597457\
23189706772547915061505504953922979530901129967519\
86188088225875314529584099251203829009407770775672\
11306739708304724483816533873502340845647058077308\
82959174767140363198008187129011875491310547126581\
97623331044818386269515456334926366572897563400500\
42846280183517070527831839425882145521227251250327\
55121603546981200581762165212827652751691296897789\
32238195734329339946437501907836945765883352399886\
75506164965184775180738168837861091527357929701337\
62177842752192623401942399639168044983993173312731\
32924185707147349566916674687634660915035914677504\
99518671430235219628894890102423325116913619626622\
73267460800591547471830798392868535206946944540724\
76841822524674417161514036427982273348055556214818\
97142617910342598647204516893989422179826088076852\
87783646182799346313767754307809363333018982642090\
10848802521674670883215120185883543223812876952786\
71329612474782464538636993009049310363619763878039\
62184073572399794223406235393808339651327408011116\
66627891981488087797941876876144230030984490851411\
60661826293682836764744779239180335110989069790714\
85786944089552990653640447425576083659976645795096\
66024396409905389607120198219976047599490197230297\
64913982680032973156037120041377903785566085089252\
16730939319872750275468906903707539413042652315011\
94809377245048795150954100921645863754710598436791\
78639167021187492431995700641917969777599028300699\
15368713711936614952811305876380278410754449733078\
40789923115535562561142322423255033685442488917353\
44889911501440648020369068063960672322193204149535\
41503128880339536053299340368006977710650566631954\
81234880673210146739058568557934581403627822703280\
82616570773948327592232845941706525094512325230608\
22918802058777319719839450180888072429661980811197\
77158542502016545090413245809786882778948721859617\
72107838435069186155435662884062257473692284509516\
20849603980134001723930671666823555245252804609722\
53503534226472524250874054075591789781264330331690'
total = 0
for i in xrange(0, 100 * 50 - 1, 50):
total += int(number_string[i:i+49])
print str(total)[:10]
print "Elapsed Time:", (time.time() - start) * 1000, "millisecs"
a=raw_input('Press return to continue')
In my attempt to learn (Iron)Python out in the open, here’s my solution for Project Euler Problem 12.
As always, any feedback is welcome.
# Euler 12
# http://projecteuler.net/index.php?section=problems&id=12
# The sequence of triangle numbers is generated by adding
# the natural numbers. So the 7th triangle number would be
# 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms
# would be:
# 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
# Let us list the factors of the first seven triangle
# numbers:
# 1: 1
# 3: 1,3
# 6: 1,2,3,6
# 10: 1,2,5,10
# 15: 1,3,5,15
# 21: 1,3,7,21
# 28: 1,2,4,7,14,28
# We can see that 28 is the first triangle number to have
# over five divisors. What is the value of the first
# triangle number to have over five hundred divisors?
import time
start = time.time()
from math import sqrt
def divisor_count(x):
count = 2 # itself and 1
for i in xrange(2, int(sqrt(x)) + 1):
if ((x % i) == 0):
if (i != sqrt(x)): count += 2
else: count += 1
return count
def triangle_generator():
i = 1
while True:
yield int(0.5 * i * (i + 1))
i += 1
triangles = triangle_generator()
answer = 0
while True:
num = triangles.next()
if (divisor_count(num) >= 501):
answer = num
break;
print answer
print "Elapsed Time:", (time.time() - start) * 1000, "millisecs"
a=raw_input('Press return to continue')
In my attempt to learn (Iron)Python out in the open, here’s my solution for Project Euler Problem 11.
As always, any feedback is welcome.
# Euler 11
# http://projecteuler.net/index.php?section=problems&id=11
# What is the greatest product
# of four adjacent numbers in any direction (up, down, left,
# right, or diagonally) in the 20 x 20 grid?
import time
start = time.time()
grid = [\
[8,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,8],\
[49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00],\
[81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65],\
[52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91],\
[22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80],\
[24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50],\
[32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70],\
[67,26,20,68,02,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21],\
[24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72],\
[21,36,23,9,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95],\
[78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,9,53,56,92],\
[16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57],\
[86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58],\
[19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40],\
[04,52,8,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66],\
[88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69],\
[04,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36],\
[20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16],\
[20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54],\
[01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48]]
# left and right
max, product = 0, 0
for x in range(0,17):
for y in xrange(0,20):
product = grid[y][x] * grid[y][x+1] * \
grid[y][x+2] * grid[y][x+3]
if product > max : max = product
# up and down
for x in range(0,20):
for y in xrange(0,17):
product = grid[y][x] * grid[y+1][x] * \
grid[y+2][x] * grid[y+3][x]
if product > max : max = product
# diagonal right
for x in range(0,17):
for y in xrange(0,17):
product = grid[y][x] * grid[y+1][x+1] * \
grid[y+2][x+2] * grid[y+3][x+3]
if product > max: max = product
# diagonal left
for x in range(0,17):
for y in xrange(0,17):
product = grid[y][x+3] * grid[y+1][x+2] * \
grid[y+2][x+1] * grid[y+3][x]
if product > max : max = product
print max
print "Elapsed Time:", (time.time() - start) * 1000, "millisecs"
a=raw_input('Press return to continue')
In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 53.
I first attempted to solve this problem using the Ruby combinations libraries. That didn’t work out so well. With a second look at the problem, the provided formula ended up being just the thing to solve the problem effectively.
As always, any feedback is welcome.
# Euler 53
# http://projecteuler.net/index.php?section=problems&id=53
# There are exactly ten ways of selecting three from five,
# 12345: 123, 124, 125, 134, 135, 145, 234, 235, 245,
# and 345
# In combinatorics, we use the notation, 5C3 = 10.
# In general,
#
# nCr = n! / r!(n-r)!,where r <= n,
# n! = n(n1)...321, and 0! = 1.
#
# It is not until n = 23, that a value exceeds
# one-million: 23C10 = 1144066.
# In general: nCr
# How many, not necessarily distinct, values of nCr,
# for 1 <= n <= 100, are greater than one-million
timer_start = Time.now
# There's no factorial method in Ruby, I guess.
class Integer
# http://rosettacode.org/wiki/Factorial#Ruby
def factorial
(1..self).reduce(1, :*)
end
end
def combinations(n, r)
n.factorial / (r.factorial * (n-r).factorial)
end
answer = 0
100.downto(3) do |c|
(2).upto(c-1) { |r|
answer += 1 if combinations(c, r) > 1_000_000
}
end
puts answer
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"
In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 52.
Compared to Problem 51, this problem was a snap. Brute force and pretty quick…
As always, any feedback is welcome.
# Euler 52
# http://projecteuler.net/index.php?section=problems&id=52
# It can be seen that the number, 125874, and its double,
# 251748, contain exactly the same digits, but in a
# different order.
#
# Find the smallest positive integer, x, such that 2x, 3x,
# 4x, 5x, and 6x, contain the same digits.
timer_start = Time.now
def contains_same_digits?(n)
value = (n*2).to_s.split(//).uniq.sort.join
3.upto(6) do |i|
return false if (n*i).to_s.split(//).uniq.sort.join != value
end
true
end
i = 100_000
answer = 0
while answer == 0
answer = i if contains_same_digits?(i)
i+=1
end
puts answer
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"
In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 51.
I know I started back up with Python this week, but I have three more Ruby solutions in the hopper and I wanted to share. For the record, Project Euler 51 was the second hardest Euler problem for me thus far. Yeah.
As always, any feedback is welcome.
# Euler 51
# http://projecteuler.net/index.php?section=problems&id=51
# By replacing the 1st digit of *3, it turns out that six
# of the nine possible values: 13, 23, 43, 53, 73, and 83,
# are all prime.
#
# By replacing the 3rd and 4th digits of 56**3 with the
# same digit, this 5-digit number is the first example
# having seven primes among the ten generated numbers,
# yielding the family: 56003, 56113, 56333, 56443,
# 56663, 56773, and 56993. Consequently 56003, being the
# first member of this family, is the smallest prime with
# this property.
#
# Find the smallest prime which, by replacing part of the
# number (not necessarily adjacent digits) with the same
# digit, is part of an eight prime value family.
timer_start = Time.now
require 'mathn'
def eight_prime_family(prime)
0.upto(9) do |repeating_number|
# Assume mask of 3 or more repeating numbers
if prime.count(repeating_number.to_s) >= 3
ctr = 1
(repeating_number + 1).upto(9) do |replacement_number|
family_candidate = prime.gsub(repeating_number.to_s,
replacement_number.to_s)
ctr += 1 if (family_candidate.to_i).prime?
end
return true if ctr >= 8
end
end
false
end
# Wanted to loop through primes using Prime.each
# but it took too long to get to the starting value.
n = 9999
while n += 2
next if !n.prime?
break if eight_prime_family(n.to_s)
end
puts n
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"
In my attempt to learn (Iron)Python out in the open, here’s my solution for Project Euler Problem 10.
As always, any feedback is welcome.
# Euler 10
# http://projecteuler.net/index.php?section=problems&id=10
# The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
# Find the sum of all the primes below two million.
import time
start = time.time()
def primes_to_max(max):
primes, number = [2], 3
while number < max:
isPrime = True
for prime in primes:
if number % prime == 0:
isPrime = False
break
if (prime * prime > number):
break
if isPrime:
primes.append(number)
number += 2
return primes
primes = primes_to_max(2000000)
print sum(primes)
print "Elapsed Time:", (time.time() - start) * 1000, "millisecs"
a=raw_input('Press return to continue')
In my attempt to learn (Iron)Python out in the open, here’s my solution for Project Euler Problem 9.
As always, any feedback is welcome.
# Euler 9
# http://projecteuler.net/index.php?section=problems&id=9
# A Pythagorean triplet is a set of three natural numbers,
# a b c, for which, # a2 + b2 = c2
# For example, 32 + 42 = 9 + 16 = 25 = 52.
# There exists exactly one Pythagorean triplet for which
# a + b + c = 1000. Find the product abc.
import time
start = time.time()
product = 0
def pythagorean_triplet():
for a in range(1,501):
for b in xrange(a+1,501):
c = 1000 - a - b
if (a*a + b*b == c*c):
return a*b*c
print pythagorean_triplet()
print "Elapsed Time:", (time.time() - start) * 1000, "millisecs"
a=raw_input('Press return to continue')