David Tran's blog

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

SOE ex.5.9 (2)

admin — Sun, 22 Nov 2009 02:23:53 +0000


{-

    Program : make_change.hs
    Author  : David Tran
    Date    : 2008-10-25

    On the SOE exercise 5.9 (http://davidtran.doublegifts.com/blog/?p=37)
    I said that I will find a solution for it. Here it is.
    The make change question could be considered as partitions of integers
    problem. (http://davidtran.doublegifts.com/blog/?p=152)
    The amount money is the interger to be partition.
    The coins are the generating functions; only select functions matchs coins' value.

    Examples:
    makeChange 99 [5, 1]         ==> [19,4]
    makeChange 18 [10, 9, 3, 1]  ==> [0,2,0,0]

-}
import Data.List
import Data.Maybe

type Constant = (Int, Int)       -- "Constant" at "Position"
type Coefficient = [ Constant ]  -- "Sum" of Constant
type Exponent = Int
type Term = (Coefficient, Exponent)
type Polynomial = [ Term ]       -- "Sum" of Term

term :: Int -> Int -> Polynomial
term max n = ([],0) : [ ([(n,i)], n * i) | i <- [1.. max `div` n ] ]

mult :: Int -> Polynomial -> Polynomial -> Polynomial
mult max p1 p2 = [ (c1++c2, e1+e2) | (c1,e1) <- p1, (c2,e2) <- p2, e1+e2 <= max ]

makeChange :: Int -> [Int] -> [Int]
makeChange n cs = to_solution $ min_change $ only_coeff $ filter_terms $ generate_terms 
  where
  generate_terms = foldr1 (mult n) (map (term n) cs)
  filter_terms   = filter (\(c, e) -> e == n)
  only_coeff     = map (\(c, e) -> c)
  min_change     = minimumBy (\x y -> compare (countCoin x) (countCoin y))
  countCoin      = foldr (\(c,t) sum -> sum + t) 0
  to_solution xs = map (\c -> fromMaybe 0 (lookup c xs)) cs

Partitions of Integers

admin — Sat, 21 Nov 2009 13:16:42 +0000


{-
 
  Program ...... : partition.hs (Partitions of Integers)
                   Partitions of Integers using generating function
  Author ....... : David Tran
  Date ......... : 2008-10-25
  References ... : http://en.wikipedia.org/wiki/Partition_%28number_theory%29
                   http://chowkafat.net/Enumeration15.html 

  ========================================================================
  
  Here shows example for n == 3
  * To simply the calculation, the coefficient of term x^0 is always ([],0)
  * most time we are interested only on term "n" (limited constant). 
    So any term > n is no need to calculate;
    that's the "max" for; so we will not have an infinity of terms Polynomial.

  term 3 1 = [ ([],0), ([(1,1)],1), ([(1,2)],2), ([(1,3)], 3) ]
           = ( 1 x^0 + (N1 x)^1 + (N1 x)^2 + (N1 x)^3 )
  term 3 2 = [ ([],0), ([(2,1)],2) ]
           = ( 1 x^0 + (N2 x)^1 )
  term 3 3 = [ ([],0), ([(3,1)],3) ]
           = ( 1 x^0 + (N3 x)^1 )

  multiple the 3 terms = (term 3 1) * (term 3 2) * (term 3 3)
  mult 3 (term 3 3) $ mult 3 (term 3 1) (term 3 2)
  = [ ([],0), ([(2,1)],2), ([(1,1)],1), ([(1,1),(2,1)],3),
      ([(1,2)],2), ([(1,3)],3), ([(3,1)],3) ]

  ([(1,1),1) is for term x^1 => (1,1)           => 1 = 1
  for term x^2, we got [(2,1)] and [(1,2)]      => 2 = 2 = 1+1
  for term x^3, [(1,1),(2,1)], [(1,3)], [(3,1)] => 3 = 1 + 2
                                                     = 1 + 1 + 1
                                                     = 3
  
  ========================================================================

  Example Usage:

  *Main> partition 5
  [[(5,1)],[(2,1),(3,1)],[(1,1),(4,1)],[(1,1),(2,2)],[(1,2),(3,1)],[(1,3),(2,1)],[(1,5)]]

  *Main> pp_partition 5
  5=5
  5=2+3
  5=1+4
  5=1+2+2
  5=1+1+3
  5=1+1+1+2
  5=1+1+1+1+1

  *Main> countPartition 5
  7

-}

type Constant = (Int, Int)       -- "Constant" at "Position"
type Coefficient = [ Constant ]  -- "Sum" of Constant
type Exponent = Int
type Term = (Coefficient, Exponent)
type Polynomial = [ Term ]       -- "Sum" of Term

term :: Int -> Int -> Polynomial
term max n = ([],0) : [ ([(n,i)], n * i) | i <- [1.. max `div` n ] ]

mult :: Int -> Polynomial -> Polynomial -> Polynomial
mult max p1 p2 = [ (c1++c2, e1+e2) | (c1,e1) <- p1, (c2,e2) <- p2, e1+e2 <= max ]

partition :: Int -> [ Coefficient ]
partition n = only_coeff $ filter_terms $ generate_terms
  where generate_terms = foldr1 (mult n) (map (term n) [1..n])
        filter_terms   = filter (\(c, e) -> e == n)
        only_coeff     = map (\(c, e) -> c)

countPartition :: Int -> Int
countPartition = length . partition

pp_partition :: Int -> IO()   -- pretty print partition
pp_partition n = sequence_ $ map showSum (partition n)
  where showSum s = do putStr $ (show n) ++ "=" ++ sumList (strList s) ++ "\n"
        strList = foldl (\acc (n,i) -> acc ++ replicate i (show n)) []
        sumList = foldl1 (\x y -> x ++ "+" ++ y)

Depth-first search and Breath-first search

admin — Sun, 15 Nov 2009 13:51:59 +0000


{-

Author ................. : David Tran
Date ................... : 2009-11-13
Breadth-first search ... : http://en.wikipedia.org/wiki/Breadth-first_search
Depth-first search ..... : http://en.wikipedia.org/wiki/Depth-first_search

Beath-first Algorithm (informal)
1. Enqueue the root node.
2. Dequeue a node and enqueue the direct child nodes.
3. If the queue is empty, every node has been examined. Done.
4. Repeat from Step 2.

Using a stack (put direct child nodes on the front instead of the back)
instead of a queue whould turn this algorithm into a depth-first search.

This program shows the similarity of breath-first and depth-first.
The "travel" function combines both into one!

-}

module Main where

-- http://www.haskell.org/haskellwiki/Algebraic_data_type
-- Rose Tree
data Tree a = Node a [Tree a]

df :: Tree a -> [a]
df (Node n st) = n : concat (map df st)
-- df (Node n st) = n : concat [df t | t <- st]

depthFirst :: Tree a -> [a]
depthFirst t = depthFirst' [t]
  where
  depthFirst' []                       = []
  depthFirst' ((Node n subTrees) : ts) = n : depthFirst' (subTrees ++ ts)

breadthFirst :: Tree a -> [a]
breadthFirst t = breadthFirst' [t]
  where
  breadthFirst' []                       = []
  breadthFirst' ((Node n subTrees) : ts) = n : breadthFirst' (ts ++ subTrees)

travel :: Tree a -> Bool -> [a]
travel t depthFirst = travel' [t]
  where 
  travel' [] = []
  travel' ((Node n st) : ts) = n : travel' nexts
    where nexts = if depthFirst then st ++ ts else ts ++ st

tree :: Tree Int
tree =   -- http://en.wikipedia.org/wiki/File:Depth-first-tree.svg
  Node 1 [
    Node 2 [
      Node 3 [
        Node 4 [], 
        Node 5 []
      ],
      Node 6 []
    ],
    Node 7 [],
    Node 8 [
      Node 9 [
        Node 10 [],
        Node 11 []
      ],
      Node 12 []
    ]
  ]

main :: IO ()
main = do 
       putStrLn $ show $ df tree
       putStrLn $ show $ depthFirst tree
       putStrLn $ show $ breadthFirst tree
       putStrLn $ show $ travel tree True
       putStrLn $ show $ travel tree False

JavaScript: The Good Parts

admin — Wed, 05 Aug 2009 12:00:45 +0000

Finish the book “JavaScript: The Good Parts”; excellent book, learned a lot.

Book
Google Video
Yahoo Video
Blog

My second digital camera

admin — Thu, 16 Jul 2009 20:56:52 +0000

Today (2009-07-16), I finally received my new camera!

It is Panasonic DMC-G1R and also got the DMW-BLB13 extra battery.
I ordered DMC-G1R camera, H-FS045200 lens, and DMW-BLB13 extra battery on 2007-07-10.

I also called Panasonic Customer Support today, because I found out that they forgot to take my promotion coupon discount and over charged me.
Hope this problem will fix soon.

This is my second digital camera; my first one is still working, but it is very very old now.
It is Nikon coolpix 4300.

Olympus E-P1 just came out and expensive; and because I can get discount and promotion coupon, so it is time to upgrade to DMC-G1R.

Flex in a week

admin — Sun, 26 Apr 2009 01:21:22 +0000

Good Flex Tutorial on Adobe Web Site: Flex in a week

Day 1 : done. (2009-04-25)
Day 2 : done. (2009-04-27)
Day 3 : done. (2009-04-29)
Day 4 : done. (2009-05-05)
Day 5 : done. (2009-05-08)

Book “Getting Started with Flex 3″ can be downloaded from the “Flex in a week” training page : done. (2009-05-10)

Power Set #2

admin — Fri, 22 Aug 2008 20:36:10 +0000

My power set solution is defined.
I just found there is challenge question about get the power set in “order” without using sort.
For example:


subsets [] = [[]]
subsets [1,2,3] = [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

My solution for this challenge is simply reuse my combination function.


combination :: [a] -> Int -> [[a]]
combination _   0    = [[]]
combination []  _    = []
combination (x:xs) n = map (x:) (combination xs (n-1)) ++ combination xs n

subset :: [a] -> [[a]]
subset xs = concat [combination xs k | k <- [0..n]] where n = length xs

Quiz: Count the ways to find a word by walking on a grid (5)

admin — Thu, 03 Apr 2008 15:32:33 +0000

/*
 * Author : David Tran
 * Date   : 2008-04-03
 * Quiz   : CountPaths
 */

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Quiz4 {
    
    public static void main(String[] args) throws Exception {
        new Quiz4().solve();
    }

    public void solve() {
        long start = System.currentTimeMillis();
        loadProblem();
        BigInteger solutions = BigInteger.ZERO;
        for (int index : starts) {
            solutions = solutions.add(findSolution(index / cols, index % cols, 0));
        }
        System.out.println("Total Solution = " + solutions);
        System.out.println("Total time (msec) to solve = " + (System.currentTimeMillis() - start));
    }
    
    public Quiz4() throws Exception {
        rows = 50;
        cols = 50;
        cellLength = 1;
        goal = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"; // 50x"A"
        gridData = new String[rows][cols];  // 50×50x"A"
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                gridData[i][j] = "A";
            }
        }
    }
    
    private int rows;
    private int cols;
    private int lastNumber;
    private List starts;
    private Map[][] grid;

    private int cellLength;
    private String goal;
    private String[][] gridData;
    
    
    @SuppressWarnings("unchecked")
    private void loadProblem() {
        // split goal string to build up dictionary
        Map> dictionary = new HashMap>();
        for (int nb = 0, position = 0, length = goal.length(); position < length; nb++, position += cellLength) {
            String substring = goal.substring(position, position + cellLength);
            if (dictionary.containsKey(substring)) {
                dictionary.get(substring).add(nb);
            } else {
                List values = new ArrayList();
                values.add(nb);
                dictionary.put(substring, values);
            }
        }
        if (dictionary.size() <= 0) {
            throw new IllegalArgumentException("No input data ?!");
        }
        
        lastNumber = (goal.length() / cellLength) - 1;
        starts = new ArrayList();
        grid = (Map [][]) new Map[rows][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                String key = gridData[i][j];
                if (dictionary.containsKey(key)) {
                    Map map = new HashMap();
                    for (int nb : dictionary.get(key)) {
                        map.put(nb, null);
                        if (nb == 0) {
                            starts.add(i * cols + j);
                        }
                    }
                    grid[i][j] = map;
                }
            }
        }
    }
    
    private BigInteger findSolution(int i, int j, int nb) {
        if (nb == lastNumber) {
            return BigInteger.ONE;
        } else {
            BigInteger solutions = grid[i][j].get(nb);
            if (solutions == null) {
                solutions = BigInteger.ZERO;
                for (int index : findNeighbors(i, j, nb)) {
                    solutions = solutions.add(findSolution(index / cols, index % cols, nb + 1));
                }
                grid[i][j].put(nb, solutions);
            }
            return solutions;
        }
    }
    
    private List findNeighbors(int i, int j, int nb) {
        int nextNb = nb + 1;
        List neighbors = new ArrayList();
        addNeighbor(i - 1, j - 1, nextNb, neighbors);
        addNeighbor(i - 1, j    , nextNb, neighbors);
        addNeighbor(i - 1, j + 1, nextNb, neighbors);
        addNeighbor(i    , j - 1, nextNb, neighbors);
        addNeighbor(i    , j + 1, nextNb, neighbors);
        addNeighbor(i + 1, j - 1, nextNb, neighbors);
        addNeighbor(i + 1, j    , nextNb, neighbors);
        addNeighbor(i + 1, j + 1, nextNb, neighbors);
        return neighbors;
    }
    
    private void addNeighbor(int i, int j, int nb, List list) {
        if (i >= 0 && i < rows && j >= 0 && j < cols && 
                grid[i][j] != null && grid[i][j].containsKey(nb)) {
            list.add(i * cols + j);
        }
    }
}

Result on my machine:


A:>java Quiz4
Total Solution = 303835410591851117616135618108340196903254429200
Total time (msec) to solve = 562

Quiz: Count the ways to find a word by walking on a grid (4)

admin — Wed, 02 Apr 2008 21:22:33 +0000

# Author : David Tran
# Date   : 2008-04-02
# Quiz   : http://davidtran.doublegifts.com/blog/?p=139
# File   : quiz.rb

class Quiz

  def initialize(grid_file, goal_file)
    grid_data = IO.readlines(grid_file).map {|e| e.chomp}.map {|e| e.split(/\s+/)}
    goal = IO.read(goal_file).chomp
  
    @rows = grid_data.size
    @cols = grid_data[0].size
    cell_size = grid_data[0][0].size
  
    # split goal string to build up dictionary
    dictionary = Hash.new {|h, e| h[e] = []}
    index = 0
    goal.scan(/#{'.' * cell_size}/).each do |w|
      dictionary[w] << index
      index += 1
    end
  
    @last_nb = (goal.size / cell_size) - 1
    @grid = Array.new(@rows) { Array.new(@cols) { Hash.new } }
    starts = []
  
    @rows.times do |r|
      @cols.times do |c|
        dictionary[grid_data[r][c]].each do |v|
          @grid[r][c][v] = -1
          starts << [r,c] if v == 0
        end
      end
    end

    solutions = starts.inject(0) { |s, (i,j)| s += find_solution(i, j, 0) }
    puts "Total Solution = #{solutions}"
  end
  
  def find_solution(i, j, nb)
    return 1 if nb == @last_nb
    return @grid[i][j][nb] if @grid[i][j][nb] >= 0
    @grid[i][j][nb] = get_neighbors(i, j, nb).inject(0) { |s, (x, y)| s += find_solution(x, y, nb+1) }
  end
  
  def get_neighbors(i, j, nb)
    [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]].inject([]) do |a, (x,y)|
      a << neighbor(i+x, j+y, nb+1)
    end.compact
  end
  
  def neighbor(i, j, nb)
    (i >= 0 && i < @rows && j >= 0 && j < @cols && @grid[i][j].key?(nb)) ? [i, j] : nil
  end
  
end

if $0 == __FILE__
  (puts "Usage: ruby quiz.rb  grid_file  goal_file"; exit) if ARGV.size < 2
  Quiz.new(ARGV[0], ARGV[1])
end

# ============================== #

# Author : David Tran
# Date   : 2008-04-02
# File   : test.rb
# Object : find the maximum solutions

open('grid.txt', 'w') {|f| 50.times { f << 'A ' * 50 << "\n"}}
max = 0
index = -1
50.times do |i|
  i += 1
  open('goal.txt', 'w') { |f| f << 'A' * i }
  result = %x{ ruby quiz.rb grid.txt goal.txt }
  if result =~ /Solution = (\d+)/
    solutions = $1.to_i
    puts "#{i.to_s.rjust(2, '0')} => #{solutions}"
    if (solutions > max)
      max = solutions
      index = i
    end
  end
end

puts
puts "Maximum => #{index} => #{max}"


__END__
Result:

01 => 2500
02 => 19404
03 => 152292
04 => 1198512
05 => 9453300
06 => 74662104
07 => 590305088
08 => 4670864544
09 => 36982919796
10 => 292979734056
11 => 2322050158968
12 => 18410909224368
13 => 146024921567904
14 => 1158535320863088
15 => 9194071282628352
16 => 72981174038164224
17 => 579439667561976564
18 => 4601415854638476552
19 => 36547133286285125864
20 => 290326968106929048336
21 => 2306684143572560961624
22 => 18329503368942296048880
23 => 145670217447616179975600
24 => 1157829208250036601664992
25 => 9203827271760017849641312
26 => 73171094997928920840845904
27 => 581774919929278927886179248
28 => 4626070561470449649010421664
29 => 36788241251602079481574654656
30 => 292579041503607826263355150176
31 => 2327088439774693588696558829376
32 => 18510420519854069350331486524800
33 => 147248802959429409354656962751220
34 => 1171434060031010511872752993856328
35 => 9319939961558447074697552088702600
36 => 74154290207123230340766878367722064
37 => 590046376097012157795995971369959624
38 => 4695281006073221324094307242033576432
39 => 37364705320671553187068052340260719824
40 => 297361737077320616265561468778248253728
41 => 2366634780471229416464762512469663693592
42 => 18836455040472517436022242181973614080112
43 => 149929836577708085403038515575864523777776
44 => 1193430584532300786500980677298194867380832
45 => 9500046751158181070821773471417360223448304
46 => 75626347587870791654047249972768528120486752
47 => 602058474789522292652482399670191674941123040
48 => 4793158368431771829259255859223541964804203200
49 => 38161186114402617099716572074367083097283018976
50 => 303835410591851117616135618108340196903254429200

Maximum => 50 => 303835410591851117616135618108340196903254429200