David Tran’s blog

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

Slides and Demos

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

{-
 - 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) ++ "."

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.

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!

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

<s> ::= <p>*
<p> ::= <non_bracket_chars>
      | ( <s> )
      | [ <s> ]

=end

def check(s); s =~
/^
  (?<p>
    [^\(\)\[\]]+    # <non_bracket_chars>
  |
    \( \g<p>* \)    # ( <p>* )
  |
    \[ \g<p>* \]    # [ <p>* ]
  )*
$/x
end

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<Character> stack = new Stack<Character>();
    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 =~ /^(?<p>[^\(\)\[\]]*(\(\g<p>*\)|\[\g<p>*\])*)*$/
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
=============================

on Ruby 1.9
(?<name>...) ==> define named group
\g<name>     ==> subexp call by group name

Example #1
----------
Regex matchs the set {a^nb^n | n >= 1} such as "ab", "aabb", "aaabbb", ... etc.

/^(?<c>a\g<c>*b)$/   # define subexp group <c> and recursive reuse

Example #2
----------
BNF of arithmetic expressions grammar:
<E> ::= <T> + <E>
<E> ::= <T> - <E>
<E> ::= <T>
<T> ::= <F> * <T>
<T> ::= <F> / <T>
<T> ::= <F>
<F> ::= ( <E> )
      | number

Below regex matchs the expression <E>

%r{
^
  (?<E>
    (?<T>
      (?<F>
        \( \g<E> \)           # <F> ::= ( <E> )
      |
        ([1-9]\d* | 0)        # <F> ::= number
      )

      ( ( \* | \/ ) \g<T> )?  # <T> ::= <F>  |  <F> * <T>  |  <F> / <T>
    )

    (   ( \+ | \- ) \g<E> )?  # <E> ::= <T>  |  <T> + <E>  |  <T> - <E>
  )
$
}x

Example #3
----------
Checking the balance of (nested) brakets [] and (); such
"..([..])..((..))..[[]].."  ==> True
"(()"  or "..[..(..]..).."  ==> False
Below regex will do the job.

/^
  (?<p>                  # named group <p>
    [^\(\)\[\]]*         # 0 or more non-bracket chars

    (
        \(  \g<p>*  \)   #    ( <p>* )
    |                    # or
        \[  \g<p>*  \]   #    [ <p>* ]
    )*
  )*
$/x

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  /^(.(?<! exp ))*$/

* Match string that does NOT content "hello" word.
/^((?!hello).)*$/  or  /^(.(?<!hello))*$/

{-
    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
-}