The cartesian product of sets

April 17th, 2013

-- The cartesian product of sets

prod2 :: [a] -> [b] -> [(a,b)]
prod2 xs ys = [(x, y) | x <- xs, y <- ys]
-- prod2 xs ys = concatMap (zip xs . repeat) ys

prod3 :: [a] -> [b] -> [c] -> [(a,b,c)]
prod3 xs ys zs = [(x, y, z) | x <- xs, y <- ys, z <- zs]

prod :: [[a]] -> [[a]]
prod = foldr f [[]]
  where f xs rss = concatMap (\x -> map (x:) rss) xs

5 min math for my kids

October 1st, 2012

#!/usr/bin/env ruby -w

#-----------------------------------------------------------------# 
#                                                                 #
#  Program : 5_min_math.rb                                        #
#  Object  : Generate 5 min math test postscript file for kids    #
#  Author  : David Tran                                           # 
#  Version : 2012-10-01                                           #
#                                                                 #
#-----------------------------------------------------------------# 

def generate_numbers( min1, max1, min2, max2 )
  random = Random.new
  range1 = min1..max1
  range2 = min2..max2
  result = ""
  100.times { result << "(#{random.rand(range1)}) (#{random.rand(range2)})\n" }
  result
end

def generate_postscript( filename, operator, min1, max1, min2, max2 )
  numbers = generate_numbers( min1, max1, min2, max2 )
  File.open( filename, 'w' ) do |f|
    f << eval("<<END_REEVAL\n" + DATA.read + "\nEND_REEVAL\n")
  end
end

if __FILE__ == $0
  help = <<-EOD
Usage: #{File.basename($0)} filename [ operator min1 max1 min2 max2 ]
\tfilename ... : filename (without .ps) to save to
\toperator ... : operator string to use, default to +
\tmin1 ....... : minimum for number #1, default to 0
\tmax1 ....... : maximum for number #1, default to 9
\tmin2 ....... : minimum for number #2, default to min1
\tmax2 ....... : maximum for number #2, default to max1
Example: ruby #{File.basename($0)} my_math + 11 55 0 9
EOD
  (puts help; exit 1) if ARGV.size < 1
  filename = ARGV.shift + '.ps'
  operator = ARGV.shift || '+'
  min1 = (ARGV.shift || '0').to_i
  max1 = (ARGV.shift || '9').to_i
  min2 = (ARGV.shift || min1).to_i
  max2 = (ARGV.shift || max1).to_i
  generate_postscript( filename, operator, min1, max1, min2, max2 )
end

# below are postscript code that needs #{numbers} and #{operator}
__END__
%!PS
%%Title: 5 minutes Math Test
%%Creator: David Tran (generated by 5_min_math.rb)

/data [ 
#{numbers}
] def

/idx 0 def

/concatstrings  % (a) (b) --> (ab)
{
  exch dup length
  2 index length add string
  dup dup 4 2 roll copy length
  4 -1 roll putinterval
} bind def

/Helvetica findfont 16 scalefont setfont

/pwidth 612 def
/pheight 792 def
/width 55 def
/height 70 def

/quiz  % x y
{       
  /s1 data idx get def
  /idx idx 1 add def 
  /s2 data idx get def
  /idx idx 1 add def
  /len1 s1 length def
  /len2 s2 length def
  gsave
  translate
  /s2 len2 len1 ge { (#{operator} ) } { (#{operator}  ) } ifelse s2 concatstrings def 

  width s1 stringwidth pop sub 37 moveto
  s1 show

  width s2 stringwidth pop sub 20 moveto
  s2 show

  width s2 stringwidth pop sub 2 sub 17 moveto
  width 2 add 17 lineto
  stroke

  grestore
} def

0 1 9 
{
  width mul 10 add

  0 1 9 
  {
    height mul 30 add
    1 index exch
    quiz
  } for

  pop
} for

35 792 50 sub moveto
(Name) show
10 0 rmoveto
190 0 rlineto

50 0 rmoveto
(Date) show
10 0 rmoveto
190 0 rlineto
stroke 

% 612 x 792
showpage

My Java 7 Presentation

September 19th, 2011

Slides and Demos

Sum Columns

May 23rd, 2011

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

May 22nd, 2011

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

March 26th, 2011
  • 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)

    October 6th, 2010
    
    =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

    October 4th, 2010
    
    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

    October 4th, 2010
    
    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

    October 3rd, 2010
    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))*$/