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

### How fast does your browser render line charts?

Here is quick demo that tries to draw hundreds to millions of lines using your browsers drawing APIs of the HTML canvas. (Click on the "Result" of tab of the JSFiddle to show the app)

For instance, you can try to set the number of lines to 6 Million, for which I get the following results on my Macbook.

 Firefox 39 Chrome 44 tcreate = 817 ms tpack = 3047 ms tunpack = 5484 ms trender = 55383 ms tcreate = 1490 ms tpack = 3066 ms tunpack = 4116 ms trender = 13789 ms

You may need to increase tmax to 60k or more milliseconds on slower machines or browsers. Otherwise the processing will stop after  tmax ms

Feel free to post your results in the comments. Note that this demo is copy my former jsPerf test. However, since jsPerf is down due to spam activities, I moved it over to JSFiddle for everyone to experiment with it.

Cheers, Juve

## 23 July, 2015

### Line Rendering Demo

Sorry, I had to remove this older post of my line rendering demo, to be able to modify the permalink for one of my publications.

I am using the KOMA-Script book document class for my thesis and was irritated that my

`\thispagestyle{empty}`

commands were ignored in LyX (LaTeX). Luckily, there is a soluton. Just add the following code after the TOC.

`\addtocontents{toc}{\protect\thispagestyle{empty}}`

Hint: In "book" classes you may often also use `\frontmatter` and `\mainmatter` to indicate where the parts of your book start. This way you do not have to change the `\pagenumbering` manually.

## 13 July, 2015

Data processing in nodejs requires handling data in Buffer objects.
Here is a quick implementation for parsing + appending incoming buffer data to an array.

```
pre { font-family: monospace; color: #ffffff; background-color: #333333; }
* { font-size: 10pt; }
.Type { color: #bdb76b; font-weight: bold; }
.Statement { color: #f0e68c; font-weight: bold; }
.PreProc { color: #cd5c5c; }
.Constant { color: #ffa0a0; }

len0 = trg.length
(buf) ->
len    = trg.length
lines  = "#{buf}".split "\n"
if len - len0 > 0 then trg[len - 1] = trg[len - 1] + lines[0]
else                   trg.push lines[0]
trg.push line for line in lines[1..]
return

selfTest = do ->
input = []
buf = (str) -> input.push new Buffer str
buf "abc\nx"
buf "yz\n"
buf "12"
buf "34"
buf "\n"

output = ["opq",""]