Category Archives: Languages

Project Euler 12: (Iron)Python

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')

Project Euler 11: (Iron)Python

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')

Project Euler 53: Ruby

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"

Project Euler 52: Ruby

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"

Project Euler 51: Ruby

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"

Project Euler 10: (Iron)Python

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')

Project Euler 9: (Iron)Python

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')

Project Euler 8: (Iron)Python

In my attempt to learn (Iron)Python out in the open, here’s my solution for Project Euler Problem 8

As always, any feedback is welcome.

# Euler 8
# http://projecteuler.net/index.php?section=problems&id=8
# Find the greatest product of five consecutive digits
# in the following 1000-digit number
import time
start = time.time()

number = '\
73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450'

max = 0
for i in xrange(0, len(number) - 5):       
    nums = [int(x) for x in number[i:i+5]]         
    val = reduce(lambda agg, x: agg*x, nums)          
    if val > max: max = val
        
print max

print "Elapsed Time:", (time.time() - start) * 1000, "millisecs"
a=raw_input('Press return to continue')