David Tran's blog

Macbook Pro

admin — Fri, 02 Dec 2011 03:56:49 +0000

2011-11-23 BlackFriday purchased macbook pro
2011-11-30 Received
2011-12-01 First post via macbook pro

My Java 7 Presentation

admin — Mon, 19 Sep 2011 18:20:33 +0000

Sum Columns

admin — Tue, 24 May 2011 02:13:47 +0000


Problem:
  Input .... : a "matrix" of numbers.
  Output ... : each column's sum.

Example:
Input (stdin):
1 2 3 4 5
2 6 10 1 1
3 3 3 4 4
5 4 3 2 0

Output (stdout):
11 15 19 11 10

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Ruby one-liner
==============
puts readlines.map{|l|l.split.map(&:to_i)}.transpose.map{|c|c.inject(&:+)}.join(' ')

Haskell almost one-liner
========================
import Data.List (transpose)
main = interact $ unwords . map (show . sum . map read) . transpose . map words . lines

Ugly Numbers

admin — Mon, 23 May 2011 00:33:24 +0000

{-
 - Problem: Ugly Numbers  ( http://uva.onlinejudge.org/external/1/136.html )
 -
 - Ugly numbers are numbers whose only prime factors are 2, 3 or 5.
 - The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
 - shows the first 11 ugly numbers. By convention, 1 is included.
 -
 - Write a program to find and print the 1500'th ugly number.
 -}

ugly :: [Integer]
ugly = 1 : merge (map (2*) ugly) (map (3*) ugly) (map (5*) ugly)
  where merge xxs@(x:xs) yys@(y:ys) zzs@(z:zs)
          | x < y && x < z  =  x : merge xs yys zzs
          | y < x && y < z  =  y : merge xxs ys zzs
          | z < x && z < y  =  z : merge xxs yys zs
          | x == y          =      merge xs yys zzs
          | y == z          =      merge xxs ys zzs
          | z == x          =      merge xxs yys zs

main = putStrLn $ "The 1500'th ugly number is " ++ show (ugly !! 1499) ++ "."

My first two BlackBerry PlayBook applications

admin — Sun, 27 Mar 2011 02:54:23 +0000

First application: Chinese Calendar and Zodiac

Start around 2010-12-03; part time work on it; application finished and submitted on 2011-01-21.
Approved by RIM on 2011-02-14 and get a free PlayBook offer email on 2011-02-15.

Second application: Peg Solitaires

Start on 2011-01-27; part time work on it; application finished and submitted on 2011-02-13 and approved by RIM on 2011-02-21.

PlayBook will be my first tablet!

Bracket balance checking regex (2)

admin — Thu, 07 Oct 2010 00:19:58 +0000


=begin
Bracket balance checking regex (2)
==================================

 ::= *
 ::= 
      | (  )
      | [  ]

=end

def check(s); s =~
/^
  (?

    [^\(\)\[\]]+    # 
  |
    \( \g
* \)    # ( 
* )
  |
    \[ \g
* \]    # [ * ]
  )*
$/x
end

Brackets balance checking

admin — Mon, 04 Oct 2010 18:22:41 +0000

Brackets balance checking ========================= Quiz ...... : write a method/function to check the blance of               (nested) brackets [] and () for a given string. Example ... : "..([..])..((..))..[[]].."  ==> True               "(()"  or "..[..(..]..).."  ==> False Source .... : http://yen3rc.blogspot.com/2010/09/haskell-practice-parenthesis-balance.html My Java/Haskell/Ruby solutions: Java ----   public static boolean check(String s) {     assert(s != null);     final Character OPEN_PARENTHESE = '(';     final Character OPEN_BRACKET = '[';     Stack stack = new Stack();     for (char c : s.toCharArray()) {       if (c == '(') {         stack.push(OPEN_PARENTHESE);       } else if (c == '[') {         stack.push(OPEN_BRACKET);       } else if (c == ')') {         if (stack.empty() || stack.pop() != OPEN_PARENTHESE) {           return false;         }       } else if (c == ']') {         if (stack.empty() || stack.pop() != OPEN_BRACKET) {           return false;         }       }     }     return stack.empty();   } Haskell ------- check :: String -> Bool check = check' [] where   check' []       []       = True   check' _        []       = False   check' ss       ('(':xs) = check' ('(':ss) xs   check' ss       ('[':xs) = check' ('[':ss) xs   check' ('(':ss) (')':xs) = check' ss xs   check' _        (')':xs) = False   check' ('[':ss) (']':xs) = check' ss xs   check' _        (']':xs) = False   check' ss       (_  :xs) = check' ss xs Ruby (version 1.9) ------------------ YEN3 said that no matter what language, they solve this almost the same way. I disagree with her; in fact, with the power of recursive regular expression, the ruby version could solve it on one liner code and without any explicit stack. def check(s)   s =~ /^(?[^\[\]]*($\g *$|\[\g
*\])*)*$/ end For more detail about recursive regular expression and detail analyze of this regex, have look at http://davidtran.doublegifts.com/blog/?p=162

Recursive Regular Expressions

admin — Mon, 04 Oct 2010 18:20:30 +0000

Recursive Regular Expressions ============================= on Ruby 1.9 (?...) ==> define named group \g     ==> subexp call by group name Example #1 ---------- Regex matchs the set {a^nb^n | n >= 1} such as "ab", "aabb", "aaabbb", ... etc. /^(?a\g*b)$/   # define subexp group and recursive reuse Example #2 ---------- BNF of arithmetic expressions grammar: ::= + ::= - ::= ::= * ::= / ::= ::= ( )       | number Below regex matchs the expression %r{ ^   (?     (?       (?         $ \g $           # ::= ( )       |         ([1-9]\d* | 0)        # ::= number       )       ( ( \* | \/ ) \g )?  # ::=   |   *   |   /     )     (   ( \+ | \- ) \g )?  # ::=   |   +   |   -   ) $ }x Example #3 ---------- Checking the balance of (nested) brakets [] and (); such "..([..])..((..))..[[]].."  ==> True "(()"  or "..[..(..]..).."  ==> False Below regex will do the job. /^   (?                  # named group     [^\[\]]*         # 0 or more non-bracket chars     (         $  \g *  $   #    ( * )     |                    # or         \[  \g *  \]   #    [
* ]     )*   )* $/x

Negating Regular Expression

admin — Sun, 03 Oct 2010 14:47:41 +0000

Negating Regular Expression Examples: * Like grep -v option * Negate a regular expression so that a search finds everything that does NOT match the pattern. /^((?! exp ).)*$/ or /^(.(?

Prime numbers

admin — Sun, 18 Jul 2010 02:07:10 +0000

{- Program : Prime.hs Author : David Tran Date : 2010-07-17 Below references show many ways to construct prime numbers: * http://www.haskell.org/haskellwiki/Prime_numbers * Melissa E. O’Neill, The Genuine Sieve of Eratosthenes http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf http://lambda-the-ultimate.org/node/3127 The classic one-liner is very elegant: primes = sieve [2..] where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p > 0] However, it may be also the slowest… The reason that I wrote my own version is because, after read yen3’s blog (Chinese) http://yen3rc.blogspot.com/2010/03/haskell-practice-prime-2.html I like to try the idea of list 6n+1 and 6n+5. -} module Prime (isPrime, primes) where primes :: [Integer] primes = 2:3:5: filter isPrime' ns where ns = foldr (\n acc -> 6*n+1 : 6*n+5 : acc) [] [1..] -- ns = concat $ zipWith (\x y -> [x,y]) [7, 13..] [11, 17..] isPrime' :: Integer -> Bool isPrime' n = check primes where check (p:ps) | p < n' = if (n `mod` p == 0) then False else check ps | otherwise = True n' = truncate (sqrt $ fromIntegral n) + 1 isPrime :: Integer -> Bool isPrime n | n < 2 = False | otherwise = isPrime' n {- isPrime :: Integer -> Bool isPrime n = n `elem` takeWhile (<=n) primes -}