Project Euler 53: Ruby
- by Ben Griswold
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"
