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.
Example output on my 2.5Ghz Macbook:
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.
"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.
#!/usr/bin/env coffee {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 } }
Comments