require 'spec_helper'
require 'prime'
=begin
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?

help:
* http://www.wikihow.com/Determine-the-Number-of-Divisors-of-an-Integer
* https://www.khanacademy.org/math/pre-algebra/factors-multiples/prime_factorization/v/prime-factorization
=end

class TriangleNumbers
  include Enumerable

  def each(&block)
    n = 1
    loop do
      block.call(sum_of(n))
      n += 1
    end
  end

  private

  def sum_of(n)
    n.downto(0).inject(0) { |total, m| total += m }
  end

end

describe 'problem 12' do
  describe TriangleNumbers do
    it 'produces the first 7 triangle numbers' do
      expect(subject.take(7)).to eql([1, 3, 6, 10, 15, 21, 28])
    end

    it 'produces the first 10 triangle numbers' do
      expect(subject.take(10)).to eql([1, 3, 6, 10, 15, 21, 28, 36, 45, 55])
    end
  end

  class Divisors
    def divisors_for(n)
      1.upto(n).find_all do |x|
        (n % x).zero?
      end
    end

    def number_of_divisors_for(n)
      prime_factors = n.prime_division
      powers_plus_one = prime_factors.map do |(prime, exponent)|
        exponent + 1
      end
      powers_plus_one.inject(1) { |total, power| total *= power }
    end
  end

  describe Divisors do
    it 'returns each factor for a number' do
      {
        1 => [1],
        2 => [1, 2],
        3 => [1,3],
        4 => [1,2,4],
        5 => [1, 5],
        6 => [1,2,3,6],
        7 => [1, 7],
        8 => [1, 2, 4, 8],
        9 => [1, 3, 9],
        10 => [1,2,5,10],
        11 => [1, 11],
        12 => [1, 2, 3, 4, 6, 12],
        13 => [1, 13],
        14 => [1, 2, 7, 14],
        15 => [1,3,5,15],
        16 => [1, 2, 4, 8, 16],
        21 => [1,3,7,21],
        24 => [1, 2, 3, 4, 6, 8, 12, 24],
        28 => [1, 2, 4, 7, 14, 28],
      }.each do |key, values|
        expect(subject.divisors_for(key)).to eql(values)
      end
    end

    it 'brute forces the answer' do
      subject = TriangleNumbers.new
      divisors = Divisors.new
      result = subject.find do |n|
        divisors.number_of_divisors_for(n) >= 500
      end
      expect(result).to eql(76576500)
    end
  end
end