In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 12.
This is another problem which I previously solved in F#. The F# solution is arguably more elegant but I find this Ruby solution far more readable. Maybe it’s just me?
I’ve talked about feature envy and extending existing class in prior Ruby posts, but I think this is the first time I’m actually doing it. It feels a bit like C# extension methods. In any case, the ability to extend classes in Ruby is probably a great reason why Ruby and TDD go hand in hand.
I originally tried to brute force the result in F# and it took forever. Actually the result never surfaced. I then discovered the clever way to calculate the number of divisors using prime factors. We bet we all learned this rule in elementary school, but I decided to document it along with my implementation. That’s the reason for the wall of comments below. As long as my blog is running, I’ll never forget again. And for the record, I didn’t try brute forcing the solution in Ruby as it seemed futile.
This script takes 1936.111 milliseconds to complete. There’s likely a more efficent implementation this is the best I can offer at the moment. Thoughts?
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?
require 'mathn'
timer_start = Time.now
# http://mathschallenge.net/index.php?section=faq
# &ref=number/number_of_divisors
# If n=48, then prime factors are 3^1 2^4, and divisor
# count is calculated by adding 1 to each power and then
# multiplying the results together.
# For 48, we have (1+1)(4+1) = 10
class Integer
def divisor_count
sum = 1
# prime_division return two dimensional array.
# for 48, [3,1], [2,4] is the result
self.prime_division.each do |x|
sum *= (x[1] + 1)
end
sum
end
end
# Define the counter and first triangle number
i, triangle_number = 1, 1
while(triangle_number.divisor_count <= 500)
i += 1
triangle_number += i
end
puts triangle_number
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"
Lol, either I’ll ask, how many hours did it take you, or, what awesome specs does your computer have?
I have to express appreciation to the writer for bailing me out of this particular crisis. Because of checking throughout the world-wide-web and getting methods which were not powerful, I thought my entire life was well over. Being alive minus the solutions to the problems you’ve resolved by way of this website is a critical case, and the ones which may have in a negative way damaged my entire career if I hadn’t discovered your blog post. Your personal knowledge and kindness in playing with the whole lot was vital. I am not sure what I would have done if I hadn’t discovered such a subject like this. I am able to at this time relish my future. Thanks for your time very much for this specialized and result oriented help. I won’t hesitate to propose your web site to anyone who should have direction about this subject.
How to add article to Joomla using a blackberry or other mobile device?
Thanks for your marvelous posting! I truly enjoyed reading it, you may be a great author.I will always bookmark your blog and will eventually come back very soon. I want to encourage you continue your great work, have a nice weekend!
Simply a smiling visitant here to share the love (:, btw outstanding style. “Everything should be made as simple as possible, but not one bit simpler.” by Albert Einstein.
It’s my belief that mesothelioma is usually the most dangerous cancer. It contains unusual features. The more I really look at it a lot more I am sure it does not act like a true solid tissue cancer. In case mesothelioma is a rogue virus-like infection, so there is the chance of developing a vaccine as well as offering vaccination for asbestos subjected people who are open to high risk connected with developing foreseeable future asbestos associated malignancies. Thanks for discussing your ideas about this important ailment.
An interesting discussion is worth comment. I think that you should write more on this topic, it might not be a taboo subject but generally people are not enough to speak on such topic.
I think this is one of the best things I have read. I’m happy that I saw your article. Would like to point out a few things, The web site style is brilliant, the posts are wicked!
. Nice one, thanks!