Skip to content

Instantly share code, notes, and snippets.

@mooware
Last active December 31, 2015 13:49
Show Gist options
  • Save mooware/7995353 to your computer and use it in GitHub Desktop.
Save mooware/7995353 to your computer and use it in GitHub Desktop.
challenge #8: find the largest palindrome made from the product of two 3-digit numbers
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment