Solution for 'Fair And Square' problem statement from Google Code Jam 2013

FairAndSquare.java

package com.bchetty.gcj2013;

import java.io.*;
import java.math.BigInteger;
import java.util.Map;
import java.util.NavigableMap;
import org.jscience.mathematics.number.LargeInteger;
import org.mapdb.DB;
import org.mapdb.DBMaker;

/**
 * Program to solve "Fair And Square" problem statement from Google Code Jam 2013.
 * This program is part of Maven project and uses JScience library (for LargeInteger's) and 
 * MapDB (Off-heap memory, which provides TreeMap and HashMap backed by disk storage).
 * 
 * @author Babji Prashanth, Chetty
 */
public class FairAndSquare {
    private DB mapDB = null;
    private NavigableMap<LargeInteger, Boolean> cache = null;
    
    /**
     * Main method, where the Disk-Based-Storage (Java Map is persisted to disk) is initialized, input is 
     * parsed from a file and required methods are called.
     * 
     * @param args 
     */
    public static void main(String[] args) {
        FairAndSquare fairAndSquare = new FairAndSquare();
        LineNumberReader lineNumberReader = null;
        BufferedWriter bufferedWriter = null;

        try {
            fairAndSquare.init(); //Initialize Cache
            lineNumberReader = new LineNumberReader(new FileReader("/Users/babjichetty/Downloads/A-small.txt"));
            bufferedWriter = new BufferedWriter(new FileWriter("/Users/babjichetty/Downloads/A-small.out.txt"));
            String line = null;
            int index = 0;
            int count = 0;

            while ((line = lineNumberReader.readLine()) != null) {
                if (index == 0) {
                    count = Integer.parseInt(line);
                    System.out.println("Count : " + count);
                    index++;
                    continue;
                }
                if (index > count) {
                    break;
                }
                String[] arr = line.split(" ");
                //int x = Integer.parseInt(arr[0]);
                //int y = Integer.parseInt(arr[1]);
                BigInteger bigX = new BigInteger(arr[0]);
                BigInteger bigY = new BigInteger(arr[1]);

                LargeInteger largeX = LargeInteger.valueOf(bigX);
                LargeInteger largeY = LargeInteger.valueOf(bigY);

                bufferedWriter.write("Case #" + index + ": " + fairAndSquare.findNumOfFairSquares(largeX, largeY));
                bufferedWriter.newLine();
                index++;
            }
        } catch (FileNotFoundException ex) {
            ex.printStackTrace();
        } catch (IOException ex) {
            ex.printStackTrace();
        } finally {
            //Close the BufferedWriter
            try {
                fairAndSquare.closeMapDB(); //Close Cache
                
                if (lineNumberReader != null) {
                    lineNumberReader.close();
                }
                if (bufferedWriter != null) {
                    bufferedWriter.close();
                }
            } catch (IOException ex) {
                ex.printStackTrace();
            }
        }
    }
    
    /**
     * 
     */
    private void initCache() {
        mapDB = DBMaker.newFileDB(new File("fairSquaresCache"))
               .writeAheadLogDisable()
               .make();
        
        cache = mapDB.getTreeMap("fairSquaresMap");
    }
    
    /**
     * Close Cache (MapDB - Off-heap memory, which provides TreeMap and HashMap backed by disk storage)
     */
    private void closeMapDB() {
        if(mapDB != null) {
            mapDB.close();
        }
    }
    
    /**
     * Initialize Cache (MapDB - Off-heap memory, which provides TreeMap and HashMap backed by disk storage)
     */
    private void init() {
        initCache();
        LargeInteger min = LargeInteger.valueOf(BigInteger.ONE);
        LargeInteger max = LargeInteger.valueOf(new BigInteger("100000000000000"));
        
        if(cache != null) {
            LargeInteger startKey = cache.ceilingKey(min);
            LargeInteger endKey = cache.floorKey(max);
            
            if(startKey != null && endKey != null) {
                initFairSquaresMap(min, max);
            }
        }
    }
    
    /**
     * Initialize Cache (MapDB - Off-heap memory, which provides TreeMap and HashMap backed by disk storage)
     * 
     * @param x
     * @param y
     * @return 
     */
    private void initFairSquaresMap(LargeInteger x, LargeInteger y) {
        LargeInteger min = findMinPerfectSquare(x, y);
        if (min == null) {
            return;
        }
        
        LargeInteger max = findMaxPerfectSquare(x, y);
        System.out.println("Min : " + min.toString() + "  Max  : " + max.toString());

        for (LargeInteger i = min; i.compareTo(max) <= 0; i = i.plus(LargeInteger.ONE)) {
            if (isPalindrome(i.toString())) {
                LargeInteger tempLargeInt = i.times(i);
                if(isPalindrome(tempLargeInt.toString())) {                    
                    cache.put(tempLargeInt,true);
                }
            }
        }
        
        System.out.println("Completed Caching!");
    }
    
    /**
     * Method to find number of "Fair And Square" numbers in a given range of numbers.
     * 
     * @param x
     * @param y
     * @return 
     */
    private long findNumOfFairSquares(LargeInteger x, LargeInteger y) {
        NavigableMap<LargeInteger, Boolean> fairSquareMap = mapDB.getTreeMap("fairSquaresMap");
        LargeInteger startKey = fairSquareMap.ceilingKey(x);
        LargeInteger endKey = fairSquareMap.floorKey(y);
        
        if(startKey == null || endKey == null || startKey.compareTo(y) > 0) {
            return 0;
        }
        
        Map subMap = fairSquareMap.subMap(startKey, true, endKey, true);
        return (subMap != null) ? subMap.size() : 0;
    }
    
    /**
     * Method to find the minimum perfect square within a range of numbers.
     * 
     * @param x
     * @param y
     * @return 
     */
    private LargeInteger findMinPerfectSquare(LargeInteger x, LargeInteger y) {
        for (LargeInteger i = x; i.compareTo(y) <= 0; i = i.plus(LargeInteger.ONE)) {
            LargeInteger res = isPerfectSquare(i);
            if (res != null) {
                return res;
            }
        }

        return null;
    }
    
    /**
     * Method to find the maximum perfect square within a range of numbers.
     * 
     * @param x
     * @param y
     * @return 
     */
    private LargeInteger findMaxPerfectSquare(LargeInteger x, LargeInteger y) {
        for (LargeInteger i = y; i.compareTo(x) >= 0; i = i.minus(LargeInteger.ONE)) {
            LargeInteger res = isPerfectSquare(i);
            if (res != null) {
                return res;
            }
        }

        return null;
    }
    
    /**
     * Method to find if a number is a perfect square.
     * 
     * @param num
     * @return 
     */
    public static LargeInteger isPerfectSquare(LargeInteger largeInt) {
        LargeInteger sqrt = largeInt.sqrt();
        return (((sqrt.times(sqrt)).compareTo(largeInt) == 0) ? sqrt : null);
    }
    
    /**
     * Method to find if a string is a palindrome or not.
     * 
     * @param input
     * @return 
     */
    public static boolean isPalindrome(String input) {
        return (input != null && 
                    (input.isEmpty() || input.length() == 1 || input.equals((new StringBuilder(input).reverse().toString()))));
    }
}

hi

In an easier method can someone help me solve this problem i am using eclipse .

Zoe likes palindromes, and thinks them to be nice. A palindrome is just an integer that reads the same backwards and forwards - so 6, 11 and 121 are all palindromes, while 10, 12, 223 and 2244 are not (even though 010=10, we don't consider leading zeroes when determining whether a number is a palindrome).

She recently became interested in squares as well, and formed the definition of a nice and square number - it is a number that is a palindrome and the square of a palindrome at the same time. For instance, 1, 9 and 121 are nice and square (being palindromes and squares, respectively, of 1, 3 and 11), while 16, 22 and 676 are not nice and square: 16 is not a palindrome, 22 is not a square, and while 676 is a palindrome and a square number, it is the square of 26, which is not a palindrome.

Now he wants to search for bigger nice and square numbers. Your task is, given an interval Zoe is searching through, to tell her how many nice and square numbers are there in the interval, so she knows when she has found them all.

Input

The first line of the input gives the number of test cases, T. T lines follow. Each line contains two integers, A and B - the endpoints of the interval Zoe is looking at.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of fair and square numbers greater than or equal to A and smaller than or equal to B.
Limits

Small dataset
1 ≤ T ≤ 100. 1 ≤ A ≤ B ≤ 1000.

Large dataset
1 ≤ T ≤ 10000. 1 ≤ A ≤ B ≤ 1014.

Sample

Input
3
1 4
10 120
100 1000

Output
Case #1: 2
Case #2: 0
Case #3: 2