Project Euler 53: Ruby

Posted by Ben Griswold on Johnny Coder See other posts from Johnny Coder or by Ben Griswold
Published on Tue, 14 Sep 2010 03:39:28 +0000 Indexed on 2010/12/06 16:59 UTC
Read the original article Hit count: 406

Filed under:
|
|

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"

© Johnny Coder or respective owner

Related posts about languages

Related posts about Project Euler