I've been trying to optimize this while making it readable. Thoughts?
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,28We 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?
@triangle_number = 441
@factors = []
@right_of_tree = []
@left_of_tree = []
def find_triangle_number_with_500_factors
natural_number = 1000
while !over_500_factors?
@factors = []
@right_of_tree = []
@left_of_tree = []
triangle_number_generator(natural_number)
find_factors_with_a_factor_tree
natural_number += 1
end
p @triangle_number
end
def triangle_number_generator(natural_number)
@triangle_number = natural_number*(natural_number+1) / 2
end
def find_factors_with_a_factor_tree
create_prime_factor_tree(@triangle_number)
find_combinations_in_left_of_tree
end
def find_combinations_in_left_of_tree
last_prime_factor = @right_of_tree.last
@left_of_tree.push(last_prime_factor)
(1..@left_of_tree.length).each do |combination_size|
cxget_combinations(@left_of_tree, combination_size)
combinations.each do |arr|
@factors << arr.inject(:*)
end
end
end
def get_combinations(arr, combination_size)
arr.combination(combination_size).to_a.uniq
end
def create_prime_factor_tree(number)
until number <= 1
factor = get_initial_divisor(number)
if factor
@right_of_tree.push(number / factor)
@left_of_tree.push(factor)
number = number / factor
else
break
end
end
end
def get_initial_divisor(number)
2.upto(number / 2) do |possible_factor|
if number % possible_factor == 0
return possible_factor
break
end
end
return nil
end
def over_500_factors?
return true if @factors.size + @right_of_tree.size >= 498
end
Benchmark.bm do |bm|
bm.report { find_triangle_number_with_500_factors}
end
1 Answer 1
Main method
You want your code to tell the story of how you are solving the problem, starting with the general picture and then working down to the details.
Your main method is find_triangle_number_with_500_factors. I suggest you change the name slightly:
- drop "find" as being useless.
- don't hardwire "500".
Not hardwiring "500" makes the method more general, facilitates testing and helps explain what the method does. In general, hardwiring is bad and doesn't buy you anything.
Perhaps we might call the method smallest_triangle_number(nbr_factors).
Make the main method simple, showing how the calculation is made is the simplest of terms:
def smallest_triangle_number(nbr_factors)
n = 0
nfacs = 0
while nfacs < nbr_factors
n += 1
tnbr = triangle_number(n)
nfacs = nbr_factors(tnbr)
end
tnbr
end
To my way of thinking, the shorter the method, the shorter the variable names can be. If a method is short, and you understand what value a variable holds, you don't have to remember its name very long, so it can be short. Here I used n (and nbr) for "number" because I always use that convention. triangle_number(n) obviously is a method that calculates n's triangle number. I can use something short like tnbr because the expression says what it is. Same with nbr_factors and nfacs.
If you want to get fancy you don't have to begin with the number 1. Instead, you could calculate a lower bound on numbers that have triangle numbers with the given number of factors.
Calculate triangle numbers
Next, in order, the method triangle_number(n). Your method is fine, except "generator" doesn't add anything to the name and there is no need for an instance variable. Just return the triangle number, which also helps with the self-documentation of the method:
def triangle_number(nbr)
nbr * (nbr + 1) / 2
end
I suggest that you only introduce instance variables when you really need them. For this problem, I don't think you need any.
This problem concerns natural numbers, so I think nbr is enough. (Nobody will ask, "What if nbr is negative, a float, a complex number or a Roman numeral"?) You could instead calculate each triangle number from the previous one, but this is a quick calculation relative to the other work that must be done, and stands alone, so I think that's fine.
Calculate factors
Next up, nbr_factors. You are doing that calculation in two steps, so again, keep the method short to give the reader the big picture:
def nbr_factors(nbr)
pfacs = prime_factors(nbr)
prime_factors_to_nbr_factors(pfacs)
end
Again, this is pretty much self-documenting. Notice that I've written the argument as nbr, rather than some variation of triangle_number. That's because the method applies to natural numbers generally, even though we will only use it for triangle numbers. You could of course also write this as:
def nbr_factors(nbr)
prime_factors_to_nbr_factors(prime_factors(nbr))
end
That's up to you, but you probably want to use the first form at least while you are debugging and testing.
Calculate number of factors from prime factors
Now let's go out of order and look at the method prime_factors_to_nbr_factors. This one is actually quite easy, as we can employ a version of the Tau function.
Suppose we have constructed prime_factors(n) to return the array:
pfacs = [[f1,n1], [f2,n2],..., [fm, nm]],
where:
fi is the ith prime factor
ni is the number of times fi is a factor
and:
n = f1**n1 * f2**n2 *...* fm**nm
The Tau function tells us the number of factors is:
(n1+1)*(n2+1)*...*(nm+1)
which in Ruby-speak is:
def prime_factors_to_nbr_factors(prime_factors)
prime_factors.reduce(1) { |tot,(_,n)| tot *= (n+1) }
end
It makes sense that the number of factors should not depend on what the particular prime factors are, just how many there are and the number of times each occurs.
(Note that if you don't care about displaying the prime factors, you could have prime_factors--probably renamed--return only [n1, n2,..., nm].)
Suppose, for example:
tnbr = triangle_number(7)
#=> 28
Then
pfacs = prime_factors(28)
#=> [[2,2], [7,1]]
so
prime_factors_to_nbr_factors([[2,2], [7,1]])
#=> (2+1)*(1+1) => 6
It remains to construct the method prime_factors to return an array similar to pfacs above. As I've rambled on awhile, I'll leave it to others to cover that.