Friday, May 22, 2015

Dynamic Programming : Largest Increasing Sub Sequence

Some Dynamic Programming from scratch!

The programming world is so rude, whenever they want to test you, they ask a problem and before you begin to solve, most of the times you have to tackle dynamic programming trick to get it done. I have been coding for decent times now. Only place where I have to use DP is contest. I wish, I get a job where I practically have to implement it as well..

Never the less, starting from scratch taking one problem today

Question: Length of Largest Increasing Sub-sequence.

Defining array : A[] = {a1,a2,a3....an};

Answer = Length of largest increasing sub-sequence L

So, I define another array L[] = {empty of size N} which will numbers such that

L[r] = Length of largest sub-sequence starting at index r

What we know... L[N] = 1....yaaaay!!!!! --> get this setup in my array!

going bottom up... and building my array now!!


L[N-1] = {1 if A[N-1] > A[N] else 2 }

L[N-2] = {1 if A[N-2] > A[N-1] else (L[N-1]+1) }

so L[r] = {1 if A[r] > A[r+1] ; else (L[r+1]+1) with L[N]=1}

loop r from N to 1 and there we go


(please see, in notations above, I have used 1 as first index not zero)


Crux Code

public static void largestIncSeq(int[] A){

int N = A.length;

int n = N-1; //human readable indexing!

int[] L = new int[N];

L[n] = 1; //sure answer

for (int r=n-1; r>0; r--){

if (A[r+1] < A[r])

L[r] = 1;

else

L[r] = L[r+1]+1;

}

}


Complete code that demonstrate the same:


public class LargestSubSeqLen{

public static void main(String[] a){

int[] input = {1,4,5,4,5,6,7,8,3,2,1};

System.out.print("Input Array = ");

for (int i =0 ; i< input.length; i++){

System.out.print(input[i]);

if (i!=input.length-1){

System.out.print(",");

}

}

System.out.println();

int output = largestIncSeq(input);

System.out.println("Largest Sequence Size : "+output);

}

public static int largestIncSeq(int[] A){

int N = A.length;

int n = N-1; //human readable indexing!

int[] L = new int[N];

L[n] = 1; //sure answer

System.out.println("Setting L["+n+"] as 1");

for (int r=n-1; r>=0; r--){

if (A[r+1] < A[r])

L[r] = 1;

else

L[r] = L[r+1]+1;

System.out.println("Setting L["+r+"] as "+L[r]);

}

int max = 0;

int maxInitIndex = 0;

for (int r=0; r<N; r++){

if (L[r]>max) {

max = L[r];

maxInitIndex = r;

}

}

System.out.print("Largest Increasing Sequence:");

for (int i=maxInitIndex; i<max+maxInitIndex; i++){

System.out.print(A[i]);

if (i!=max+maxInitIndex-1)

System.out.print(",");

}

System.out.println();

return max;

}

}


Sample I/O:

zeek@zeek ~/code/java/dynamicProb $ javac LargestSubSeqLen.java

zeek@zeek ~/code/java/dynamicProb $ java LargestSubSeqLen

Input Array = 1,4,5,4,5,6,7,8,3,2,1

Setting L[10] as 1

Setting L[9] as 1

Setting L[8] as 1

Setting L[7] as 1

Setting L[6] as 2

Setting L[5] as 3

Setting L[4] as 4

Setting L[3] as 5

Setting L[2] as 1

Setting L[1] as 2

Setting L[0] as 3

Largest Increasing Sequence:4,5,6,7,8

Largest Sequence Size : 5

Thursday, May 14, 2015

ZeeK Monitor

This setup lets user to plot any comma separated values at real time. The plotted chart is published on a webpage.
This is a good tool to show realtime statistics.
Special Thanks to JFreeChart. 
Please go thru "http://www.jfree.org/lgpl.php"

Technically the client needs to broadcast (on UDP) comma separated values to server being used to process chart and push to a webpage. The intermediate dataProcessor will capture the data. The chartProcessor will process and create images (every X interval for last Y data) and webpage/html will display the chart.

Their are various options to display chart, order charts, group charts etc.



This is an attempt to simplify Real Time Charting solution. What I would do to make it work 1. Download complete bin folder first 2. Download chart.properties 3. Download Either Monitor.war within dist directory or create a new web Archieve using src/WebContent/build.xml/build.properties 4. A Client Script is a must for demo. If I happen to receive any request, I will upload a sample client script. Meanwhile, there is a sendUDP.pl that should help. Perl is not necessary. I have seen my associates coding in Java and plain bash to ceate client scripts. 5. Adjust chart.properties based on needs. 6. Read how to setup Real time monitors from docx uploaded at same location. This is an ongoing process. Any Suggestion for improvement is appreciated and will be done. Also, the code is so simple, anyone can actually change and run. Would appreciate if any generic feature is communicated back to me so that I could upload it for the world. Please note, This project would not be possible without JFreeChart. I have not upgraded to JFreeChart latest release but I intend to do so in future, based on response. 

Go For it --> SOURCE CODE AND PRODUCT Thanks Aman ZeeK Verma

Thursday, March 15, 2012

Prime Numbers

Mathematics that includes prime numbers are quite tough for me. They have unique kind of property that we all are aware of (i.e, the number is divisible by only two distinct numbers being one and itself).


To test a number to be prime or not, has a very basic approach:
1. Find all divisors of the number.
2. If it is 1 and number itself (excluding 1) then its a prime number.


So a nested task is how to get all the divisors. And a very basic approach is:
1. 1 is a divisor
2. for i in 2 to Number if i divides Number, i is a divisor.


A little better approach could be
1. 1 is a divisor
2. Number is a divisor
3. for i in 2 to Number/2 if i divides Number, i is a divisor.
(This approach works since a divisor(apart from number) will not be greater than half of the number)


Another good approach to me is
1. 1 is a divisor
2. Number is a divisor
3. from i = 2 to Sqrt(Number) if i divides Number, i is a divisor and (Number/i) is also a divisor.


Back to prime Numbers!! What if we need to keep generating prime numbers (mind it!... there is no such wonder in maths/computer that has generated all the primes yet!.. obviously they are infinite and everyday a new prime is discovered). Ok!...Lets have an upper bound. Its like generate all prime numbers upto 100
Oh! thats easy... any naive approach could get it.
Naive approach:
1. if number is less than 2 => NOT PRIME
2. if number is 2 => PRIME
3. if number is divisible by 2 => NOT PRIME (special case already handled)
4. for i in 3 to UPPER_BOUND (100 here), if number is divisible by i => NOT PRIME
5. loop in step 4 completed, ok! its a prime number!!


Step 4 in naive approach can be optimized when increment of i is set by 2 instead of 1 (since number is definately not even)


How can we further optimize Step 4, no need to go upto UPPER_BOUND.
We can go till UPPER_BOUND/2
And in similar way we can further optimize by iterating upto Sqrt(UPPER_BOUND)
(Similar explaination with divisor algo)


Are we ok!... Not satisfied.. true, even this approach fails when UPPER_BOUND gets into category of 'large numbers' something like 10^7


How about memoization?... doesn't help much, you cannot pre compute anything that helps to check if a number is prime or not.


There google googles down another fantastic approach, a totally different perception and so far the quickest approach to generate list of primes and it is called
*drum beats*... tada...
"Sieve of Eratosthenes"
directly pasted from wiki:


"To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:
Create a list of consecutive integers from 2 to n: (2, 3, 4, ..., n).
Initially, let p equal 2, the first prime number.
Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.
Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.
When the algorithm terminates, all the numbers in the list that are not marked are prime"


Boom!
This is fast...
Here is a sample private method in java to do the same




private static void generateSieve(){
System.out.println("generating sieve");
int MAX = 1000000;
boolean[] primeSieve = new boolean[MAX+2];
int MAXplus2 = MAX+2;
for (int i=0; i
primeSieve[i]=true;
for (int i=2; i<=MAXplus2/2; i++){
if (primeSieve[i]){
for (int j=(2*i); j
primeSieve[j]=false;
}
}
}
System.out.println("DONE");
}


time for prime time..
-ZeeK

Thursday, February 23, 2012

Java Unique Exception Extractor Utility

During development of a java application, the greatest problem is runtime Exceptions that occur in background. These background RuntimeExceptions are generally important to fix the code. Some of them are SQLException, NullPointerException, RuntimeUserRuntimeException, ClassCastException, IndexOutOfBoundException etc. These exception are hard to be caught during construction and are generally logged in background (It may even get unnoticed, if something went wrong in a thread which is not main thread).
Java logging frameworks used in standard java application development, somehow makes the log quite verbose. Each and every step/flow fired in application gets logged (For instance, current value of x = someDynamicAppValue.
A developer is interested in only exceptions that is useful for them.

Please find link to one such utility that I created recently which helps an analyst to just collect unique stack traces from the logs and rest of the logs need not be scanned. The utility was tested with >500MB of txt java logs, and it did it job within 3 minutes.

https://sourceforge.net/projects/uniqxceptnxtrct/files/

Suggestion / Bugs / Feedback will be highly appreciated.

Wednesday, June 22, 2011

More on Integer Partition

I posted (searched and posted) a standard way to partition number few weeks back...  (as a part of euler project).. The one liner problem was to find number of ways to split an integer as sum of other Positive integers. (http://zeektech.blogspot.com/2010/08/project-euler-76-ways-can-one-hundred.html)

I recently got similar challenge (seems to be famous problem again).. which deals with Integer partition but restricted integers to be used.

Problem: Find Ways to Split $N into $0.01, $0.05, $0.10, $0.25
Here is the solution: (obviously it again uses DP)
import java.io.*;
public class coin_changes{
public static int[] d = {1, 5, 10, 25};
public static int[][] table;
public static void main(String[] args) throws Exception{
table = new int[10000][4];
for (int i=0; i<10000; i++)
   for (int j=0; j<4; j++)
     table[i][j]=-1;
DataInputStream dis = new DataInputStream(new FileInputStream(new File(args[0])));
String a = dis.readLine();
while (a != null){
System.out.println(recF(Integer.parseInt(a),3));
a = dis.readLine();
}
}
public static int recF(int i, int j){
       if (j < 0 || i < 0)
          return 0;
       if (i == 0) {
          return 1;
        }
      if (table[i][j]!=-1)
             return table[i][j];
      else
             table[i][j]=recF(i, j-1) + recF(i-d[j], j);
      return table[i][j];
      //return recF(i, j-1) + recF(i-d[j], j);
 }
}


The code above does the same work...with memoization... The memoization (google it for details) is a way to store previous computation. The table here stores the value of previously computed recursion, hence less function calls.

The array produced finally is similar to array produced in previous post, with a slight modification.

PS: Each line of input file (passed in argument) contains value of "N" for which ways has to be counted

Happy Coding!!

Friday, February 18, 2011

Project Euler 98:

This is getting interesintg... Project Euler is taking all my brains out now.. every question seems simple when solved. but how to start
Problem:
http://projecteuler.net/index.php?section=problems&id=98

My approach checks for all the perfect squares first and then checks to anagrams... Here is the solution... 

        int maxmaxmaxmax=0;
        String input = (new DataInputStream(new FileInputStream(new File("words.txt")))).readLine();
        StringTokenizer st = new StringTokenizer(input, ",");
        ArrayList list = new ArrayList();   
        while (st.hasMoreTokens()) {
            list.add(st.nextToken().replace("\"", ""));
        }
        long now = System.currentTimeMillis();
        for (int i = 0; i < list.size(); i++) {
            char[] word1 = list.get(i).toCharArray();
            Arrays.sort(word1);
            for (int j = 0; j < list.size(); j++) {
                if (i == j)
                    continue;
                char[] word2 = list.get(j).toCharArray();
                if (word1.length != word2.length)
                    continue;
                Arrays.sort(word2);
                boolean isAnagram = true;
                for (int k = 0; k < word1.length; k++) {
                    if (word1[k] != word2[k]) {
                        isAnagram = false;
                        break;
                    }
                }
                if (!isAnagram)    continue;

                boolean isPalindrome = true;
                for (int m = 0; m < word1.length; m++) {
                    if (list.get(i).charAt(m) != list.get(j).charAt(
                            word1.length - m - 1)) {
                        isPalindrome = false;
                        break;
                    }
                }
                if (isPalindrome) break;
                int max = (int) Math.floor((Math.pow(10, word1.length) - 1));
                int min = (int) Math.ceil(Math.pow(10,(word1.length - 1)));
                for (int number = min; number < max; number++) {
                    if (Math.sqrt(number) - Math.floor(Math.sqrt(number)) == 0) { // perfect
                        String squareNumber = ""+number;
                        int[] square = new int[word1.length];
                        for (int m=0; m
                            square[m] = Integer.parseInt(""+squareNumber.charAt(m));
                        HashMap tempMapping = new HashMap();
                        int[] digits = new int[10];
                        int[] disWord = new int[26];
                        for (int m=0; m<10; m++){
                            digits[m]=0;
                        }
                        for (int m=0; m
                            tempMapping.put(""+list.get(i).charAt(m),square[m]);
                            digits[square[m]] = 1;
                            disWord[(int)list.get(i).charAt(m)-65] = 1;
                        }
                        int countDistinctDigit=0;
                        int countDistinctLetter=0;
                        for (int m=0; m<10; m++)
                            if (digits[m]==1)
                                countDistinctDigit++;
                        for (int m=0; m<26; m++)
                            if (disWord[m]==1)
                                countDistinctLetter++;
                       
                        if (countDistinctDigit != countDistinctLetter) continue;
                        String tempValue="";
                        for (int m=0; m
                            tempValue+=(tempMapping.get(""+list.get(j).charAt(m)));
                        }
                        if (tempValue.charAt(0)=='0')
                            continue;
                        int number2 = Integer.parseInt(tempValue);
                        if (Math.sqrt(number2) - Math.floor(Math.sqrt(number2)) == 0) { //YAPS
                            int tempMax=(number>number2)?number:number2;
                            if (tempMax>maxmaxmaxmax){
                                System.out.println(list.get(i)+"-"+number+" vs "+list.get(j)+"-"+number2+" has max = "+tempMax+"(ans) its sqrt ="+Math.sqrt(tempMax));
                            }
                            maxmaxmaxmax=(tempMax>maxmaxmaxmax)?tempMax:maxmaxmaxmax;
                        }   
                    }
                }
            }
        }
        System.out.println("Total Time Taken = "+(System.currentTimeMillis() - now)/1000 +" sec");
   

Wednesday, January 5, 2011

My Personal Square Root

It was really a fun to revise how to actually calculate square roots on paper!..
Following is my attempt, it works fine, but I am sure there are faster methods.

public static String squareRoot(int number, int decimal_precision){
String answer="";
String pairedNumber = ""+number;
int precision=1;

if (Math.sqrt(number) - Math.floor(Math.sqrt(number)) == 0)
return ""+Math.sqrt(number);

int initialGuess = (int) Math.sqrt(number);
answer+=(""+initialGuess+".");

if ((""+number).length() % 2 != 0)
pairedNumber="0"+pairedNumber;

for (int i=0; i<3*decimal_precision; i++)
pairedNumber=pairedNumber+"0";

String remainder = ""+(number - (initialGuess*initialGuess));
String factor = ""+(2*initialGuess);

while (precision <= decimal_precision){
//System.out.println("remainder="+remainder);
String dropPair = remainder+pairedNumber.substring(2*precision+2, 2*precision+4);
//System.out.println("drop : "+dropPair);
//System.out.println("factor :"+factor);
for (int i=0; i<=9; i++){
String newFactor = factor+i;
// System.out.println("new factor chk = "+newFactor);
BigInteger a = new BigInteger(newFactor).multiply(BigInteger.valueOf(i));
BigInteger b = new BigInteger(dropPair);
BigInteger c = (new BigInteger(newFactor).add(BigInteger.ONE)).multiply(BigInteger.valueOf(i+1));
//System.out.println(a+" "+b+" "+c);
if (a.compareTo(b) == -1 && b.compareTo(c) == -1)
//if (Integer.parseInt(newFactor)*i <= Integer.parseInt(dropPair) && Integer.parseInt(dropPair) < Integer.parseInt(newFactor)*(i+1))
{ //System.out.println("Found new factor : "+newFactor +" with i="+i);
answer=answer+i;
factor = ""+(new BigInteger(newFactor).add(BigInteger.valueOf(i)));
//factor = ""+(Integer.parseInt(newFactor)+i);
remainder = ""+(new BigInteger(dropPair).subtract(a));
//remainder=""+(Integer.parseInt(dropPair) - (Integer.parseInt(newFactor)*i));
break;
}
}
precision++;
// System.out.println("answer="+answer);
}


return answer;
}

Sample I/O:
System.out.println(squareRoot(2, 100));
1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727

Is my blog being read?