Here is the task:

"A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers."
(originally

posted by

Joseph Farah)

Here is my quick solution. I know that the palindrome test may be improved, e.g., by excluding some of the numbers based on the arithmetic properties.

{floor} = Math
{now} = Date
print = console.log.bind console, "palindromes:"
assert = (expr,msg) -> throw new Error "AssertionError: #{msg}" unless expr
bench = (name,fn) -> t = now(); r = fn(); print "#{name} took #{now() - t}ms"; r
isPalindrome = (n) ->
str = "#{n}"; len = str.length
mid = floor len / 2; last = len - 1
for i in [0..mid]
if str[i] != str[last - i] then return false
return true
findPalindromes = (n=999) ->
list = []
for x in [0..n]
for y in [x..n]
list.push {x,y,palindrome: p} if isPalindrome p = x*y
list
byPalindrome = (a,b) -> a.palindrome - b.palindrome
testSuite1 = do ->
f1 = (n) -> assert isPalindrome(n), "'#{n}' must be a palindrome!"
f2 = (n) -> assert not isPalindrome(n), "'#{n}' must not be a palindrome!"
[9009, 919, 1, 11, 123321, "abba", "aba", NaN, "" ].forEach f1
[991,9919,10,"01","abc",null,-1,undefined].forEach f2
main = (n) ->
list = bench "findPalindromes(#{n})", -> findPalindromes n
largest = list.sort(byPalindrome)[list.length - 1]
print "found #{list.length} palindromes:", {last5: list[-5..], largest}
module.exports = {isPalindrome,findPalindromes,byPalindrom}
if process.mainModule == module then main 1 * process.argv[2]

Example output on my 2.5Ghz Macbook:

$ ./palindrom.coffee 999
palindromes: findPalindromes(999) took 52ms
palindromes: found 3539 palindromes: { last5:
[ { x: 894, y: 957, palindrome: 855558 },
{ x: 924, y: 932, palindrome: 861168 },
{ x: 916, y: 968, palindrome: 886688 },
{ x: 924, y: 962, palindrome: 888888 },
{ x: 913, y: 993, palindrome: 906609 } ],
largest: **{ x: 913, y: 993, palindrome: 906609 } }**
$ ./palindrom.coffee 9999
palindromes: findPalindromes(9999) took 6893ms
palindromes: found 36433 palindromes: { last5:
[ { x: 9631, y: 9999, palindrome: 96300369 },
{ x: 9721, y: 9999, palindrome: 97200279 },
{ x: 9811, y: 9999, palindrome: 98100189 },
{ x: 9867, y: 9967, palindrome: 98344389 },
{ x: 9901, y: 9999, palindrome: 99000099 } ],
largest: { x: 9901, y: 9999, palindrome: 99000099 } }

**Update:** I just needed to take a break from writing my PhD thesis and optimized the search for the

*largest* palindrome. Here is an improved version of the above script.

findPalindromes = (n=999,pruneSmallProducts=false) ->
list = []
pmax = x:0, y:0, palindrome:0
for x in [n..0]
break if x * n < pmax.palindrome and pruneSmallProducts
for y in [n..x]
p = x * y
break if p < pmax.palindrome and pruneSmallProducts
if isPalindrome p
list.push o = {x,y,palindrome:p}
pmax = o if o.palindrome > pmax.palindrome
list
main = (n) ->
list = bench "findPalindromes(#{n})", -> findPalindromes n,true
largest = list.sort(byPalindrom)[list.length - 1]
print "found #{list.length} palindromes:", {last5: list[-5..], largest}

The speed up is significant.

$ ./palindrom.coffee 999
palindroms: findPalindromes(999) took 1ms
palindroms: found 2 palindromes: { last5:
[ { x: 924, y: 962, palindrome: 888888 },
{ x: 913, y: 993, palindrome: 906609 } ],
largest: { x: 913, y: 993, palindrome: 906609 } }
$ ./palindrom.coffee 9999
palindroms: findPalindromes(9999) took 1ms
palindroms: found 1 palindromes: { last5: [ ... ],
largest: { x: 9901, y: 9999, palindrome: 99000099 } }
$ ./palindrom.coffee 99999
palindroms: findPalindromes(99999) took 19ms
palindroms: found 1 palindromes: { last5: [ ... ],
largest: { x: 99681, y: 99979, palindrome: 9966006699 } }
$ ./palindrom.coffee 999999
palindroms: findPalindromes(999999) took 129ms
palindroms: found 1 palindromes: { last5: [ ... ],
largest: { x: 999001, y: 999999, palindrome: 999000000999 } }
$ ./palindrom.coffee 9999999
palindroms: findPalindromes(9999999) took 1402ms
palindroms: found 1 palindromes: { last5: [ ... ],
largest: { x: 9997647, y: 9998017, palindrome: 99956644665999 } }