1require 'spec_helper'
  2require 'prime'
  3=begin
  4The 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:
  5
  61, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
  7
  8Let us list the factors of the first seven triangle numbers:
  9
 10 1: 1
 11 3: 1,3
 12 6: 1,2,3,6
 1310: 1,2,5,10
 1415: 1,3,5,15
 1521: 1,3,7,21
 1628: 1,2,4,7,14,28
 17We can see that 28 is the first triangle number to have over five divisors.
 18
 19What is the value of the first triangle number to have over five hundred divisors?
 20
 21help:
 22* http://www.wikihow.com/Determine-the-Number-of-Divisors-of-an-Integer
 23* https://www.khanacademy.org/math/pre-algebra/factors-multiples/prime_factorization/v/prime-factorization
 24=end
 25
 26class TriangleNumbers
 27  include Enumerable
 28
 29  def each(&block)
 30    n = 1
 31    loop do
 32      block.call(sum_of(n))
 33      n += 1
 34    end
 35  end
 36
 37  private
 38
 39  def sum_of(n)
 40    n.downto(0).inject(0) { |total, m| total += m }
 41  end
 42
 43end
 44
 45describe 'problem 12' do
 46  describe TriangleNumbers do
 47    it 'produces the first 7 triangle numbers' do
 48      expect(subject.take(7)).to eql([1, 3, 6, 10, 15, 21, 28])
 49    end
 50
 51    it 'produces the first 10 triangle numbers' do
 52      expect(subject.take(10)).to eql([1, 3, 6, 10, 15, 21, 28, 36, 45, 55])
 53    end
 54  end
 55
 56  class Divisors
 57    def divisors_for(n)
 58      1.upto(n).find_all do |x|
 59        (n % x).zero?
 60      end
 61    end
 62
 63    def number_of_divisors_for(n)
 64      prime_factors = n.prime_division
 65      powers_plus_one = prime_factors.map do |(prime, exponent)|
 66        exponent + 1
 67      end
 68      powers_plus_one.inject(1) { |total, power| total *= power }
 69    end
 70  end
 71
 72  describe Divisors do
 73    it 'returns each factor for a number' do
 74      {
 75        1 => [1],
 76        2 => [1, 2],
 77        3 => [1,3],
 78        4 => [1,2,4],
 79        5 => [1, 5],
 80        6 => [1,2,3,6],
 81        7 => [1, 7],
 82        8 => [1, 2, 4, 8],
 83        9 => [1, 3, 9],
 84        10 => [1,2,5,10],
 85        11 => [1, 11],
 86        12 => [1, 2, 3, 4, 6, 12],
 87        13 => [1, 13],
 88        14 => [1, 2, 7, 14],
 89        15 => [1,3,5,15],
 90        16 => [1, 2, 4, 8, 16],
 91        21 => [1,3,7,21],
 92        24 => [1, 2, 3, 4, 6, 8, 12, 24],
 93        28 => [1, 2, 4, 7, 14, 28],
 94      }.each do |key, values|
 95        expect(subject.divisors_for(key)).to eql(values)
 96      end
 97    end
 98
 99    it 'brute forces the answer' do
100      subject = TriangleNumbers.new
101      divisors = Divisors.new
102      result = subject.find do |n|
103        divisors.number_of_divisors_for(n) >= 500
104      end
105      expect(result).to eql(76576500)
106    end
107  end
108end