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

Is my blog being read?