Pages

24 July, 2015

Programming exercise: find palindromic numbers!

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.
#!/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
= 817 ms
= 3047 ms
= 5484 ms
= 55383 ms  
= 1490 ms
= 3066 ms
= 4116 ms
= 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.

Disable page numbers in table of contents in Lyx/LaTeX

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

Tiny linereader implementation (CoffeeScript)

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


  readline = (trg) ->
    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",""]
    input.forEach readline(output)

    assert.equal output.join(";"), "opq;;abc;xyz;1234;", "Messed up!"