Project Euler 35: Ruby

In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 35. 

For this solution, I played with pushing and popping on and off of a stack, err, Ruby array. And rotating the digits is brought to you by our good friend, shift. Execution time is slow (35 seconds) but it didn’t take me long to code so, once again, I’m happy with the result.

As always, any feedback is welcome.

# Euler 35
# http://projecteuler.net/index.php?section=problems&id=35
# The number, 197, is called a circular prime because all
# rotations of the digits: 197, 971, and 719, are
# themselves prime.
#
# There are thirteen such primes below 100:
# 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
#
# How many circular primes are there below one million?
timer_start = Time.now

require 'mathn'

def circular_prime?(i)
  nums = i.to_s.chars.to_a

  nums.length.times do
    return false if (!nums.join().to_i.prime?)
    # "pop" digit off the front and rotate to the end
    nums.push nums[0]
    nums.shift
  end

  return true
end

answer = 0
Prime.each { |x|
  break if x >= 1_000_000
  answer += 1 if circular_prime?(x)
}

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 34. 

Having just solved Project Euler 30 in Ruby a few days ago, the solution to this problem was still on the tips of my fingers. The solution is almost identical. I could have nerded out and come up with an intelligent upper bound, but doesn’t 99999 just feel right?

As always, any feedback is welcome.

# Euler 34
# http://projecteuler.net/index.php?section=problems&id=34
# 145 is a curious number, as
# 1! + 4! + 5! = 1 + 24 + 120 = 145.
#
# Find the sum of all numbers which are equal to the sum
# of the factorial of their digits.
#
# Note: as 1! = 1 and 2! = 2 are not sums they are not
# included.
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

# Note the completely random upper bound
max, answer = 99999, 0

(3..max).each do |i|
  sum_factorials = i.to_s.chars \
    .inject(0){|sum, char| sum + (char.to_i.factorial)}

  answer += i if (i == sum_factorials)
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 33. 

I had to read this problem again and again before it started to make sense to me. Actually, I moved forward having to make a few assumptions. It appeared that trivial cases were cases where the numerator and denominator were both mod 10. Also, I assumed the number to be cancelled out could be in either the first or second position of the numerator. Maybe it’s just me, but I think this problem could have been written a little clearer.

After getting a decent grasp of the problem, it became a matter of working through how Ruby handles precision which is quite logical really. The only thing I learned about Ruby in this exercise was that next will move you to the next iteration point in ones loop. I guessed the keyword for this action would be continue but it didn’t take long to correct my mistake.

As always, any feedback is welcome.

# Euler 33
# http://projecteuler.net/index.php?section=problems&id=33
# The fraction 49/98 is a curious fraction, as an
# inexperienced mathematician in attempting to simplify it
# may incorrectly believe that 49/98 = 4/8, which is correct,
# is obtained by cancelling the 9s.
#
# We shall consider fractions like, 30/50 = 3/5, to be
# trivial examples.
#
# There are exactly four non-trivial examples of this type
# of fraction, less than one in value, and containing two
# digits in the numerator and denominator.
#
# If the product of these four fractions is given in its
# lowest common terms, find the value of the denominator.
timer_start = Time.now

numerator_product, denominator_product = 1, 1

(10..98).each do |n|
  (n+1..99).each do |d|
    # Non-trivial check
    next if n % 10 == 0 && d & 10 == 0

    # See if opposite digits in numerator and denominator match
    if (n.to_s[0] == d.to_s[1] && n.to_s[1] < d.to_s[0])
      # Second digit of numerator over first digit of denominator
      fraction_as_float = Float(n.to_s[1]) / Float(d.to_s[0])
    elsif (n.to_s[1] == d.to_s[0] && n.to_s[0] < d.to_s[1])
      # First digit of numerator over second digit of denominator
      fraction_as_float = Float(n.to_s[0]) / Float(d.to_s[1])
    else
      next
    end

    # Do we get the same value if we cancel out like digits?
    if (Float(n) / Float(d) == fraction_as_float)
      numerator_product*=n
      denominator_product*=d
    end
  end
end

puts denominator_product / numerator_product

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 32. 

I should take some time and consider why iterating from 1 to 9999 is enough looping to obtain the correct result. I should but I won’t. It’s a beautiful Sunday afternoon and the grill is calling. I’ll also bet there are dozens of more optimized solutions to this problem (likely tied to the iteration count) but I’m happy with what I’ve provided below — and now those burgers and Anaheim peppers won’t have to cook themselves.

As always, any feedback is welcome.

# Euler 32
# http://projecteuler.net/index.php?section=problems&id=32
# We shall say that an n-digit number is pandigital if it
# makes use of all the digits 1 to n exactly once;
# for example, the 5-digit number, 15234, is 1 through 5
# pandigital.
#
# The product 7254 is unusual, as the identity,
# 39 x 186 = 7254, containing multiplicand, multiplier,
# and product is 1 through 9 pandigital.
#
# Find the sum of all products whose multiplicand/
# multiplier/product identity can be written as a 1 through
# 9 pandigital.
#
# HINT: Some products can be obtained in more than one way
# so be sure to only include it once in your sum.
timer_start = Time.now

require 'set'
distinct_products = Set.new

def ordered_value(a, b)
  # Build and sort the
  # multiplicand/multiplier/product
  num = a.to_s + b.to_s + (a*b).to_s
  num.split(//).sort.join
end

(1..9999).each do |a|
  (a+1..9999).each do |b|
    value = ordered_value(a, b)
    if value.length == 9  && value == "123456789"
      distinct_products << a*b
    elsif value.length > 9
      # Safely break out of the inner loop because the
      # Product isn't going to get any smaller
      break
    end
  end
end

puts distinct_products.inject {|agg, n| agg + n }

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 31. 

I like this question as it puts an interesting twist on the “how many ways can you make change for a dollar” question of which I was already familiar and I solved years ago. I haven’t turned to recursion in many (if any) of the Ruby solutions thus far. After spending a good amount of time with F# and Scala this year, this is welcome change because I regret to say that I still have troubles working with recursive functions at times. But enough about my shortcomings…

Below I have offered two solutions to the problem. The first isn’t scalable though it nicely demonstrates the overall approach and it does include multiple recursive methods. The latter solution is a refactoring of the former and though it might not be as easy to interpret I believe it is a more appropriate implementation.

As always, any feedback is welcome.

# Euler 31
# http://projecteuler.net/index.php?section=problems&id=31
# In England the currency is made up of pound, £, and pence,
# p, and there are eight coins in general circulation:
#
# 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
#
# It is possible to make £2 in the following way:
# 1x£1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p
#
# How many different ways can £2 be made using any number of coins?
timer_start = Time.now

def pence(i)
  1
end

def two_pence(i)
  i >= 0 ? two_pence(i-2) + pence(i) : 0
end

def five_pence(i)
  i >= 0 ? five_pence(i-5) + two_pence(i) : 0
end

def ten_pence(i)
  i >= 0 ? ten_pence(i-10) + five_pence(i) : 0
end

def twenty_pence(i)
  i >= 0 ? twenty_pence(i-20) + ten_pence(i) : 0
end

def fifty_pence(i)
  i >= 0 ? fifty_pence(i-50) + twenty_pence(i) : 0
end

def pound(i)
  i >= 0 ? pound(i-100) + fifty_pence(i) : 0
end

def two_pound(i)
  i >= 0 ? two_pound(i-200) + pound(i) : 0
end

puts two_pound(200)

puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"

# Refactored solution
timer_start = Time.now

$coin_values = [1, 2, 5, 10, 20, 50, 100, 200]

def change_count(change, coin_values_index)
  return 1 if coin_values_index == 0
  return 0 if change <  0
  change_count(change - $coin_values[coin_values_index], \
    coin_values_index) + change_count(change, coin_values_index - 1)
end

puts change_count(200, 7)

puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"

For the record, the latter implementation takes roughly 50% longer to execute. It’s a difference of 10 and 15 milliseconds.

In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 30. 

There’s not much new happening here. Again, the solution is pretty straight-forward. One minor hold up came with the way the problem statement was written. You’ll notice the max number to test wasn’t called out. I didn’t worry about this fact too much, but as you’ll see in the comments below, I solved the problem up to 9^4*5, 9^5*5 and then 9^6*5 and the last two tries provided the same result. I did try 9^7*5 as well but I didn’t wait for that result to come back. In the end, you’ll see I ended up using 9^5*5 as my max test value.

As always, any feedback is welcome.

# Euler 30
# http://projecteuler.net/index.php?section=problems&id=30
# Surprisingly there are only three numbers that can be
# written as the sum of fourth powers of their digits:
#
# 1634 = 1^4 + 6^4 + 3^4 + 4^4
# 8208 = 8^4 + 2^4 + 0^4 + 8^4
# 9474 = 9^4 + 4^4 + 7^4 + 4^4
#
# As 1 = 1^4 is not a sum it is not included.
#
# The sum of these numbers is 1634 + 8208 + 9474 = 19316.
#
# Find the sum of all the numbers that can be written as
# the sum of fifth powers of their digits.
timer_start = Time.now

# The result of 5, 6, and (I'm guessing) 7 nines was the same.
# Therefore only iterating upto 9**5 * 5
max, sum_all_sums = 9**5 * 5, 0

(2..max).each do |i|
  sum = i.to_s.chars.inject(0){|sum, char| sum + (char.to_i ** 5)}
  sum_all_sums += i if (i == sum)
end

puts sum_all_sums
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 29. 

I have provided a straight-forward, brute force solution to the problem below. Though the question talks about ordering the terms numerically, there’s no reason to do so. The only thing you need be concerned with is the number of distinct terms. If I were solving this problem in C#, I might leverage the C# HashSet to gather the terms. But I’m still focused on Ruby and it didn’t take long to hunt down the Ruby Set class.

As always, any feedback is welcome.

# Euler 29
# http://projecteuler.net/index.php?section=problems&id=29
# Consider all integer combinations of ab for 2 <= a <= 5
# and 2 <= b <= 5:
#
# 2^2=4, 2^3=8, 2^4=16, 2^5=32
# 3^2=9, 3^3=27, 3^4=81, 3^5=243
# 4^2=16, 4^3=64, 4^4=256, 4^5=1024
# 5^2=25, 5^3=125, 5^4=625, 5^5=3125
#
# If they are then placed in numerical order, with any
# repeats removed, we get the following sequence of 15
# distinct terms:
#
# 4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
#
# How many distinct terms are in the sequence generated by ab
# for 2 <= a <= 100 and 2 <= b <= 100?
timer_start = Time.now

require 'set'
distinct_terms = Set.new

(2..100).each do |a|
  (2..100).each do |b|
    distinct_terms << a**b
  end
end

puts distinct_terms.length
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"