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

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");
   

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