Project Euler problem 12 in Ruby

Question

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,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?

@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

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.