challenge #8: find the largest palindrome made from the product of two 3-digit numbers

challenge8-palindrome-number.rb

# challenge #8
# 'find the largest palindrome made from the product of two 3-digit numbers'
# see also http://projecteuler.net/index.php?section=problems&id=4

# simple one-line solution, seems fast enough
# => [906609, 993, 913]
999.downto(100).map { |a| 999.downto(100).map { |b| [a*b, a, b] }.select { |arr| s = arr.first.to_s; s == s.reverse } }.flatten(1).sort { |a, b| a.first <=> b.first }.reverse.uniq.first

# more performant solution for n-digit numbers
# 4 => [99000099, 9999, 9901]
# 5 => [9966006699, 99979, 99681]
# 6 => [999000000999, 999999, 999001]
# 7 => [99956644665999, 9998017, 9997647]
# 8 => [9999000000009999, 99999999, 99990001]
# 9 did not finish after 20 minutes

require 'pp'

def largest_palindrome(digits)
  max = (10 ** digits) - 1
  min = 10 ** (digits - 1)

  # first find the largest palindrome of n**2 to establish a lower bound
  lower_bound = max.downto(min).find do |n|
    s = (n ** 2).to_s
    s == s.reverse
  end

  # if nothing was found, use regular minimum
  lower_bound ||= min

  # now do the real search inside these bounds
  result = [lower_bound ** 2, lower_bound, lower_bound]

  for a in max.downto(lower_bound)
    # a instead of max avoids duplicate calculations
    for b in (a - 1).downto(lower_bound)
      product = a * b
      # if the product is already smaller than the current max
      # multiplying smaller numbers won't find anything
      break if product <= result.first
      # converting to string and reversing seems pretty fast
      s = product.to_s
      result = [product, a, b] if s == s.reverse
    end
  end

  result
end

if __FILE__ == $0
  pp largest_palindrome(ARGV.first.to_i)
end