## 24 July, 2015

### Programming exercise: find palindromic numbers!

"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 } }
```

#### 1 comment:

Joseph Farah said...

I like your code! :D interesting way of solving the problem.