Algorithms and Java Technology

Generate Prime Numbers With "Dynamic Programming"

2009-01-09T23:28:00.000-08:00

Here I present one technique to generate the first N prime numbers with dynamic programming. Dynamic Programming is a paradigm for designing algorithms where the next solution was taken from previous solution.

The memory complexity is O(N).
The time complexity is O(N*C), where C is the number of prime between 2 and sqrt(N) (inclusive).

Advantages:
* flexibility (generate first N prime numbers).
* can check prime until N^2 with complexity O(C).
* in my computer can generate first 200,000 prime numbers below 1 secs.

Disadvantages:
* slow when N is too large.

public class PrimeDP {

 int primes[];
 public boolean isPrime(int x) {
  if(x<2) return false;
  for(int k=0;k < primes.length && primes[k]*primes[k] <= x;k++)
   if(x%primes[k]==0) return false;
  return true;
 }

 public int getPrime(int index) {
  return primes[index];
 }

 public PrimeDP(int n) {
  primes = new int[n];
  primes[0] = 2;
  primes[1] = 3;
  for(int k=2,i=6;k < n;i+=6) {
   if(isPrime(i-1)) primes[k++]=i-1;
   if(k < n && isPrime(i+1))
   primes[k++]=i+1;
  }
 }

 public static void main(String []args) {
  long a = System.currentTimeMillis();
  int n = 200000;
  PrimeDP p = new PrimeDP(n);
  long b = System.currentTimeMillis();

  System.out.println("time = " + (b-a) + " ms.");
 }
}

Sieve Of Erasthothenes (Optimize Memory Version)

2009-01-04T22:25:00.000-08:00



public class Sieve {
 
 private int prime[]; 
 
 public boolean isPrime(int x) {  
  if(x==2) return true;
  if(x<2 || x%2==0) return false;
  x>>=1;
  return (prime[x>>5] & (1<<(x&31))) == 0;
 }  
 
 public Sieve(int n) {
  prime = new int[(n>>6)+1];
  for(int i=3;i*i<=n;i+=2) {
   int hi = i>>1;
   if( (prime[hi>>5] & (1<<(hi&31))) == 0) {
    for(int j=i*i;j<=n;j+=i)
     if((j&1)!=0) {
      int hj = j>>1;
      prime[hj>>5] |= (1<<(hj&31));
     }
   }
  }  
 }
 
 public static void main(String []args) {
  
  long start = System.currentTimeMillis();  
  Sieve sieve = new Sieve(10000000);
  long finish = System.currentTimeMillis();
  
  for(int i=0;i<100;i++)
   if(sieve.isPrime(i)) System.out.print(i + " ");
  System.out.println("");
      
  System.out.println("Time : " + (finish-start)/1000.0 + " secs");  
 }
 
}

3: Bit Manipulation (check the bit and flip the bit)

2009-01-04T18:29:00.000-08:00

In the previous post, we already learn how to set the bit and clear the bit. To check whether the k-th bit is 0 or 1 we can use & operator. To flip(change from 0 to 1 or 1 to 0) the bit simply use ^ (XOR) operator. This is the last series from "Trilogy Of Bit Manipulation".


int x = 10; // 00001010

// check the bit
if( (x & (1<<3)) != 0 )
   printf("3-th bit is 1");
else
   printf("3-th bit is 0");

// flip the bit
x = x ^ (1<<3); // long version
printf("%d\n",x); // x = 2 = 00000010

// flip the bit again
x ^= (1<<3); // short version
printf("%d\n",x); // x = 10 = 00001010

2: Bit Manipulation (clear the bit)

2009-01-03T23:13:00.001-08:00

In the first series you have learn how to set the bit, now you will learn how to clear the bit.
This is the second series from "Trilogy Of Bit Manipulation".


int x = 0;
x |= (1<<2); // x = 00000100
x |= (1<<4);

To clear the k-th bit, we can use & and ~ operator.
x = x & ~(1<<2); // I clear the 2-th bit.
How does it work ?
& is AND operation:
1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0

~ is NEGATE operation:
~ 1 = 0
~ 0 = 1


x = x & ~(1<<2); // long version
x &= ~(1<<2); // short version

initial x = 17 = 00010001
and I want to clear the 0-th bit.

(1<<0) = 00000001
~(1<<0) = 11111110

00010001
11111110
-------- AND operation
00010000 (the 0-th bit is clear)

1: Bit Manipulation (set the bit)

2009-01-03T22:42:00.000-08:00

In 32-bit Compiler, int size is 4 byte (32 bit).
Today we will play with bit ( I will type the last 8 bit rather than 32 bit to simplify my explanation).
This is the first series from "Trilogy Of Bit Manipulation".


int x = 0; 
//The bit value is : 00000000 (all the bit is 0).

 
x = x | (1<<0); // set the 0-th bit from right. 
// The bit value is : 00000001 (the last bit is 0).

 
x = x | (1<<2); // set the 2-th bit from right. 
// The bit value is : 00000101.

How does it work ?

| is OR operation :
1 or 1 = 1
1 or 0 = 1
0 or 1 = 1
0 or 0 = 0

<< is Shift Left operation :
1<<0 = 1 = 00000001
1<<1 = 2 = 00000010
1<<2 = 4 = 00000100
1<<3 = 8 = 00001000

So when I have x = 10 = 00001010

And I want to set the 5-th bit:
x = x | (1<<5); // long version
x |= (1<<5); // short version


x    = 10   = 00001010
1<<5 = 32   = 00100000
OR operation-----------
              00101010

Sudoku Solver (C++)

2009-01-03T07:26:00.000-08:00

What is Sudoku ?
Sudoku is a logic-based number-placement puzzle. The objective is to fill a 9×9 grid so that each column, each row, and each of the nine 3×3 boxes (also called blocks or regions) contains the digits from 1 to 9 only one time each. The puzzle setter provides a partially completed grid.

Here I present a solution to solve sudoku with a simple backtracking. I use bitmask to mark the number already used in each row, column and block. I can't estimate what is the time complexity of my code, but I guarantee it's fast enough (< 1 secs on my laptop). There is another efficient solution using dancing link but more harder to code.

Here's the full c++ code:


#include "stdio.h"

int board[9][9];

int fi[9]; // forbidden row
int fj[9]; // forbidden column
int fk[9]; // forbidden block

int solve(int p) { 

if(p==0)
{
for(int a=0;a<9;a++) fi[a]=fj[a]=fk[a]=0;
for(int i=0;i<9;i++)
 for(int j=0;j<9;j++)
  if(board[i][j]!=0)
  {
   int x = 1<<(board[i][j]-1);
   int k = i / 3 * 3 + (j / 3);
   fi[i] |= x;
   fj[j] |= x;
   fk[k] |= x;
  }
}

 if(p==81) return 1;

 int i = p / 9; // calculate row position
 int j = p % 9; // calculate column position
 int k = i / 3 * 3 + (j / 3); // calculate block position
 
 if(board[i][j]!=0) return solve(p+1);
 for(int no=1;no<=9;no++) 
 {
  int x = 1<<(no-1);

  // check the bit
  if(fi[i] & x) continue;
  if(fj[j] & x) continue;
  if(fk[k] & x) continue;
   
  // mark the bit
  fi[i] |= x; 
  fj[j] |= x; 
  fk[k] |= x;
   
  board[i][j] = no;
  // recurse the next level
  if(solve(p+1)==1) return 1;
  board[i][j] = 0;
   
  // clear the bit
  fi[i] &= ~x; 
  fj[j] &= ~x; 
  fk[k] &= ~x;
 }
 return 0;
}

int main() {

 // fill the board in here

 // end of fill the board 

 // print the result
 if(solve(0)==0) puts("no solution");
 else {
  for(int i=0;i<9;i++,puts(""))
   for(int j=0;j<9;j++)
    printf("%d",board[i][j]);
 }
 return 0;
}

How to create TextField that only accept letter (Java)

2009-01-02T11:25:00.001-08:00

If you use a normal JTextField then all character(s) can be accepted. But sometimes we need a textfield that only accept letter ('a'-'z' and 'A'-'Z').
I Hope this JLetterField.java can solve your problem.


import javax.swing.JTextField;
import javax.swing.text.AttributeSet;
import javax.swing.text.BadLocationException;
import javax.swing.text.Document;
import javax.swing.text.PlainDocument;

public class JLetterField
extends JTextField
{
    public JLetterField(int cols) {
        super("",cols);
    }

    protected Document createDefaultModel() {
        return new LetterDocument();
    }
    
    class LetterDocument extends PlainDocument {
        public void insertString(int offs,String str,AttributeSet a)
        throws BadLocationException
        {
            if(str==null) return;
            char [] before = str.toCharArray();
            String after = "";
            for(int i=0;i < before.length;i++)
            {
                if( (before[i]>='a' && before[i]<='z') || (before[i]>='A' && before[i]<='Z') )
                    after += before[i];
            }
            super.insertString(offs,after,a);
        }
    }    
}

Sieve Of Eratosthenes (C++)

2009-01-02T00:29:00.000-08:00

In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer.

The Algorithm:
1. Create a contiguous list of numbers from two to some highest number n.
2. Strike out from the list all multiples of two (4, 6, 8 etc.).
3. The list's next number that has not been struck out is a prime number.
4. Strike out from the list all multiples of the number you identified in the previous step.
5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list).
6. All the remaining numbers in the list are prime.

The C++ code:


#include "stdio.h"
#include "conio.h"

const int SIZE = 10000;
char f[SIZE + 1];

int main() {
    
    // 0 and 1 is not prime
    f[0]=f[1]=1;
    
    // every even number (except 2) is not prime
    for(int i=4;i<=SIZE;i+=2) f[i]=1;
    
    // iterate every odd number (start from 3) 
    for(int i=3;i*i<=SIZE;i+=2)
    {
        // if the current number is prime then the multiple is not prime 
        if(f[i]==0)
        {
            for(int j=i*i;j<=SIZE;j+=i)
                f[j]=1;
        }
    }
    
    // display prime numbers between 0 and 100
    for(int i=0;i<=100;i++)
        if(f[i]==0) printf("%d\n",i);
             
    getch();
                    
    return 0;
}

How to create replaceAll() (C++) ?

2009-01-01T09:54:00.000-08:00

Happy New Year World, this is my first post in 2009. This time I will tell about how to create replaceAll() function. This function are used to replace part of original string that contains old value to new value. The idea just iterate the string you want to replace and take the substring from each index then compare to the value you want to replace.

You can see the fullcode below :


#include "iostream"
#include "string"
using namespace std;

string replaceAll(string text,string from,string to) {
 string result = "";
 int i = 0;
 while(i < text.size()) 
 {
  if(i+from.size() <= text.size() && text.substr(i,from.size())==from )
  {
   result += to;
   i += from.size();
  }
  else 
  {
   result.push_back(text[i]);
   i++;
  }
 }
 return result;
}

int main() {
 string a = "C++ is easy";
 cout << a << endl;
 a = replaceAll(a,"C++ is","C++ and Java are");
 cout << a << endl; 
 return 0;
}

Terbilang (Java)

2008-12-30T01:23:00.000-08:00

Here's Terbilang.java, it's to convert decimal notation into word (Indonesia).

Example:

100 ==> one hundred (seratus)
1020 ==> one thousand and twenty (seribu dua puluh)

So it's very useful for people that want to learning Indonesia ^^.


public class Terbilang {    
    public static String bilang(long uang) {
        String nama[]={"nol","satu","dua","tiga","empat","lima","enam","tujuh","delapan","sembilan"};
        String besar[]={"triliun","milyar","juta","ribu",""};                
        if(uang==0) return nama[0];
        long p = 1000000000000l;
        String hasil = "";
        for(int i=0;i < besar.length;i++,p /= 1000)
        {
            if(uang < p) continue;
            long temp = uang / p;                
            boolean seribu = p==1000;
            if(temp>=100) {
                hasil += nama[(int)temp/100] + " ratus ";
                temp %= 100;
                seribu = false;
            }
            if(temp>=11 && temp<=19) {
                hasil += nama[(int)temp-10] + " belas ";
                temp = 0;
                seribu = false;
            }
            if(temp>=10) {
                hasil += nama[(int)temp/10] + " puluh ";
                temp %= 10;
            }
            if(temp > 0) {
             if(seribu && temp==1)
              hasil += "se";
             else
              hasil += nama[(int)temp] + " ";  
            }
            uang %= p;
            hasil += besar[i] + " ";
        }
        hasil=hasil.replaceAll("satu ratus", "seratus");
        hasil=hasil.replaceAll("satu belas", "sebelas");
        hasil=hasil.replaceAll("satu puluh", "sepuluh");
        return hasil.trim();
    }
}

How To Create Tic Tac Toe AI (Java)

2008-12-29T21:21:00.000-08:00

What is TicTacToe ?

Tic-tac-toe, also spelled tick tack toe, and alternatively called noughts and crosses, hugs and kisses, and many other names, is a pencil-and-paper game for two players, O and X, who take turns marking the spaces in a 3×3 grid, usually X going first. (source: http://en.wikipedia.org/wiki/Tic-Tac-Toe)

Now I will present a simple code to create Tic Tac Toe AI.

I will create one java file: TicTacToeAI.java

The Variable


    /* the board */
    private int board[][];    
    /* empty */
    public static final int EMPTY = 0;
    /* player one */
    public static final int ONE = 1;
    /* player two */
    public static final int TWO = 2;

Simple Constructor
it will initialize all value in board to 0.


    public TicTacToeAI() {
        board = new int[3][3];
    }

Method

if position (i,j) is outside the boundary it will return EMPTY


    /* get the board value for position (i,j) */
    public int getBoardValue(int i,int j) {
        if(i < 0 || i >= 3) return EMPTY;
        if(j < 0 || j >= 3) return EMPTY;
        return board[i][j];
    }

My winning move definition is one single move that lead to victory.


    /* calculate the winning move for current token */
    public int []nextWinningMove(int token) {
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)            
                if(getBoardValue(i, j)==EMPTY) {
                    board[i][j] = token;
                    boolean win = isWin(token);
                    board[i][j] = EMPTY;
                    if(win) return new int[]{i,j};
                }
        return null;
    }

I calculate the best move based on this priority:
1. lead to win
2. prevent enemy to win
3. center position
4. first available position


    /* calculate the best move for current token */
    public int []nextMove(int token) {
                
        /* if we can move on the next turn */
        int winMove[] = nextWinningMove(token);
        if(winMove!=null) return winMove;

        /* choose the move that prevent enemy to win */
        for(int i=0;i<3;i++) 
            for(int j=0;j<3;j++)
                if(getBoardValue(i, j)==EMPTY)
                {
                    board[i][j] = token;
            boolean ok = nextWinningMove(token==ONE ? TWO : ONE ) == null;                    
                    board[i][j] = EMPTY;
                    if(ok) return new int[]{i,j};
                }
        
        /* lucky position in the center of board*/
        if(getBoardValue(1, 1)==EMPTY) return new int[]{1,1};
        
        /* choose available move */
        for(int i=0;i<3;i++) 
            for(int j=0;j<3;j++)
                if(getBoardValue(i, j)==EMPTY)
                    return new int[]{i,j};
        
        /* no move is available */
        return null;
    }


    /* determine if current token is win or not win */
    public boolean isWin(int token) {
        final int DI[]={-1,0,1,1};
        final int DJ[]={1,1,1,0};
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++) {    
                
                /* we skip if the token in position(i,j) not equal current token */
                if(getBoardValue(i, j)!=token) continue;
                
                for(int k=0;k<4;k++) {
                    int ctr = 0;
                while(getBoardValue(i+DI[k]*ctr, j+DJ[k]*ctr)==token) ctr++;
                    if(ctr==3) return true;
                }
            }
        return false;
    }
}

Count number of word ( C )

2008-12-29T08:03:00.000-08:00

Word in my definition is sequence of non-space character.
Count number of word in sentence was an easy task if you already know the trick.

Example:

My name is Timo ==> counted as four word
I like to solve problems ==> counted as five word

So to create a computer program that count number of word, we can count based on how many space that separate the word (trailing space will be counted once).


int count(char sentence[]) {
  int i;
  int ret = 0;
  int x = 0;
  for(i=0;sentence[i];i++)
  {
      if(sentence[i]!=' ')
      {
          x = 1;
      }
      else
      {
          ret += x;
          x = 0;
      }
  }
  return ret + x;
}

Hope this tutorial will be useful :D.

The future of Java - Closures

2008-12-28T08:07:00.000-08:00

With Java SE 6 recently released, the discussion about what features should be in Dolphin is raging hotter than ever. Perhaps the most intereresting – and invasive – proposal is the one for closures. But this is complicated by there actually being two proposals. One is called Closures for the Java Programming Language, by Gilad Brach, Neal Gafter, James Gosling and Peter van der Ahé (the BGGA proposal). The other one is called Concise Instance Creation Expressions by Joshua Bloch, Bob Lee and Doug Lea (the CICE proposal). Neither of these two have been finished enough to actually create a JSR for them.

So, what’s the difference and what does it mean for Java programmers all over the world? Well, the CICE version is really just some syntactic sugar for anonymous interface implementations. To get closer to the closure ideal, there is some allowance for making it possible to setting variables in the enclosing scope, but there isn’t really anything in here you couldn’t do with a few clever hacks in the Java compiler. As such, it’s better than nothing, but I will be disappointed if this is all we get.

The BGGA proposal then; this is more ambitious. There is new syntax, new function types, two new reference types (Null and Unreachable). It allows some neat things with using the for keyword in new ways, and will also allow closing over break, return and continue (but not in the general way, since that would equal implementing continuations). This is all good. The new syntax have a shortcut, the looks very much like Ruby code blocks, but there are ways of chaining them that looks actually useful (just look at the with-method in the proposal).

Of course, there are problems with the BGGA proposal too. Not so much in the lack of power, but possibly because it will involve to many new concepts (or new for Java programmers at least), to much new syntax, and it is possible that this isn’t even enough to make the closures really useful.

And this is the real problem with adding closures to Java at this point. I commend what they’re trying to achieve, but I believe it’s to late. Having closures from the beginning will shape the API in ways it’s not possible to do right now. The only way we can get the full benefits of all these new toys would be for Sun to revamp the standard library, adding new versions of most classes and making the old ones softly deprecated. Changing the interfaces will be impossible, so we will haft to get used to referencing java.util.CCollection to get at the new each() internal iterator. And that each is needed. Java needs internal iterators. But that’s another rant.

In conclusion; I’m looking forward to see the end result of these proposals, but I’m very wary of what they will bring too. It is very double edged and it sometimes feels like the Java class library should be ripped out and restarted from scratch. This would remove much cruft and create a new, leaner language. And that language should have full closures and have a class library designed to maxime closure goodness.

Resource: http://java.apress.com/article/407/the-future-of-java-closures