Succinctness
As rubyists, we love being succinct, and we love playing with enumerations.
You will see very few literal false
and true
in ruby code, as well as very few explicit return
calls.
For example:
Instead of writing return false if self < 1
we will prefer to compound the condition to self >= 1 && ...
which will do the same thing, but we "save" return false
.
The power of Enumeration
Ruby has a very powerful Enumerable
, and is used widely, often more than once in a line (using method chaining).
For example:
2.upto(Math.sqrt(self)) do |i|
return false if self % i == 0
end
Here you check if any of the numbers in the range are a divisor for self
, and break if there is any. A more ruby way of doing it will be:
return false if 2.upto(Math.sqrt(self)).any? { |i| self % i == 0 }
We'll also prefer to more succinct range syntax (2..Math.sqrt(self))
, which is simply shorter...
So now, our def prime?
method could be reduced to a one-liner:
class Integer
def prime?
self > 1 && !(2..Math.sqrt(self)).any? { |i| self % i == 0 }
end
end
Mapping
Anywhere in the code I see the following pattern:
result = []
some_loop do
result << something
end
A red flag is raised, and I look for a way to use map
to do the same thing:
result = some_loop.map { something }
Your code goes over all the non-negative integers, and takes counts how many of them result in a prime, until the first non-prime.
"All the non-negative integers" can be expressed in ruby as (0..Float::INFINITY)
, so we can write:
(0..Float::INFINITY).map { |n| n**2 + a*n + b }.take_while { |result| result.prime? }.count
This code takes each integer, maps it into the result of n**2 + a*n + b
, takes all the results until they are no longer prime, and counts how many are there.
Cool! Right? The only problem with the code above, is that it will take infinity to complete it, as it takes all the numbers and maps them, and then checks for how many to take.
To solve this problem ruby now has...
Lazy Enumerables
As of ruby 2.0, lazy enumerables allows you to calculate values in an infinite stream only as needed.
To solve the problem above, all we need to do now is to add the lazy
operator on the range:
(0..Float::INFINITY).lazy.map { |n| n**2 + a*n + b }.take_while(&:prime?).count
And we have another one-liner!
Everything is an enumerable
So you want to save on your "upto-loops"? Let's do it!
You want to enumerate over each pair of numbers from -999
to 1000
, so what you actually want is to have a long matrix of those pairs:
[[-999, -999], [-999, -998],...,[1000, 1000]].do_something_smart
To do that, you can use product
:
(-999..1000).to_a.product((-999..1000).to_a)
But since both a
and b
have the same range, we can even DRY this up, and use repeated_permutation
:
(-999..1000).to_a.repeated_permutation(2)
Both of these solutions will give you the needed matrix, so we can move on the see what we should do with it...
We want to get the coeffiecients that produce the number of primes, so let's do just that:
a, b = (-999..1000).to_a.repeated_permutation(2).max_by { |a, b| get_amount_of_primes_from_quadratic_formula(a,b) }
Now all we need to do is multiply them with each other!
Method naming
Your names are very verbose, which is a good thing, but ruby idiom frowns upon get_
prefixes. Also, prefer using verbs already in the language (count
) over those which are not in the language (amount_of
)
So now the code will look like:
class Integer
def prime?
self > 1 && !(2..Math.sqrt(self)).any? { |i| self % i == 0 }
end
end
def count_quadratic_formula_primes(a,b)
(0..Float::INFINITY).lazy.map { |n| n**2 + a*n + b }.take_while(&:prime?).count
end
def product_of_coefficients_that_produce_maximum_number_of_primes_for_consecutive_values()
a, b = (-999..1000).to_a.repeated_permutation(2).max_by { |a, b| count_quadratic_formula_primes(a,b) }
a * b
end
start = Time.now
answer = product_of_coefficients_that_produce_maximum_number_of_primes_for_consecutive_values
puts "The answer is #{answer} and it took #{Time.now-start} seconds."
15 lines of hard-core ruby-style code!
Enjoy!
Update
It seems that lazy
adds considerable overhead to the performance of the code. So it is not advisable to use it.
Fortunately this works:
(0..Float::INFINITY).take_while { |n| (n**2 + a*n + b).prime? }.count
My code still runs ~2 times slower than the original (ends in 18 seconds), but it is more reasonable than with lazy
...