palindromic_products.rb

class Palindromes
  attr_reader :largest, :smallest

  PalindromicProduct = Struct.new(:value, :factors) do
    def to_str
      "#{value} -> #{factors}"
    end
  end

  def initialize(opts)
    @min = opts[:min_factor] || 1
    @max = opts[:max_factor] or raise ArgumentError, 'missing :max_factor'
  end

  def generate
    pair_up do |x, y|
      p = x * y
      @smallest ||= PalindromicProduct.new(p, [])
      if p < @smallest.value
        @smallest.value = p
        @smallest.factors = [[x, y]]
      elsif p == @smallest.value
        @smallest.factors << [x, y]
      end
    end

    pair_down do |x, y|
      p = x * y
      @largest ||= PalindromicProduct.new(p, [])
      if p > @largest.value
        @largest.value = p
        @largest.factors = [[x, y]]
      elsif p == @largest.value
        @largest.factors << [x, y]
      end
    end
  end

  private

  def pair_up
    ceil = @max
    (@min..@max).each do |x|
      break if x >= ceil
      (@min..ceil).find { |y| palindrome?(x * y) }.tap do |y|
        next if !y
        yield x, y
        ceil = y
      end
    end
  end

  def pair_down
    floor = @min
    @max.downto(@min) do |y|
      break if y <= floor
      @max.downto(floor).find { |x| palindrome?(x * y) }.tap do |x|
        next if !x
        yield x, y
        floor = x
      end
    end
  end

  def palindrome?(n)
    xs = n.to_s
    (1..xs.length / 2).all? { |i| xs[i - 1] == xs[-i] }
  end

  def self.debug(a, b, m=:pair_down)
    new(min_factor: a, max_factor: b).tap do |ps|
      ps.generate
      puts "min: " << ps.smallest, "max: " << ps.largest
    end.enum_for(m)
  end

  def self.brute(min, max)
    result = Array.new(2) { PalindromicProduct.new(0, []) }
    Enumerator.new do |out|
      (min..max).each do |x|
        (x..max).each do |y|
          s = (x * y).to_s
          out << [x, y] if (1..s.length / 2).all? { |i| s[i-1] == s[-i] }
        end
      end
    end.each_with_object(result) do |(x, y), (smallest, largest)|
      p = x * y
      if largest.value < p
        largest.value = p
        largest.factors = [[x, y]]
      elsif largest.value == p
        largest.factors << [x, y]
      end
      if smallest.value == 0 || smallest.value > p
        smallest.value = p
        smallest.factors = [[x, y]]
      elsif smallest.value == p
        smallest.factors << [x, y]
      end
    end
  end
end

params = [1000, 9999]
Palindromes.debug(*params, :pair_down).each do |x, y|
  puts "%d * %d = %d" % [x, y, x*y]
end

bmin, bmax = Palindromes.brute(*params)
puts "brute-min: " + bmin, "brute-max: " + bmax

__END__
max: 99000099 -> [[9901, 9999]]
min: 1002001 -> [[1001, 1001]]
9901 * 9999 = 99000099
brute-min: 1002001 -> [[1001, 1001]]
brute-max: 99000099 -> [[9901, 9999]]