Sunday, April 14, 2013

solutions for the google codejam qualifications 2013

Code Jam 2013 Qualification Round Answers to problems a-b-c

problem A : Tic-Tac-Toe

you can check the problem statement from codejam 2013 site:
https://code.google.com/codejam/contest/2270488/dashboard#s=p0

Answer

First loop on the diagonals , then loop on each row and column. While looping maintain two variable Xcount and Ycount , which you will increase whenever you counter a symbol (increase Xcount on finding 'X', increaseYcount on finding 'Y', increase Xcount and Ycount on finding 'T') , after each loop end check those variables, if one of them equals 5 (not 4 because I initialized them with 1) , the corresponding player is a winner, else you have two possibilities Draw or NotComplete, if there was a '.' in the input, the result is NoTcomleteGame else, Draw.

Coding

 import java.io.BufferedReader;  
 import java.io.BufferedWriter;  
 import java.io.File;  
 import java.io.FileNotFoundException;  
 import java.io.FileReader;  
 import java.io.FileWriter;  
 import java.io.IOException;  
 public class qual1 {  
      static BufferedWriter writer;  
      static BufferedReader reader;  
      public static void main(String args[]) throws IOException {  
           int newLineChar = 13;  
           File inFile = new File("input.txt"); // input file  
           File outFile = new File("output.out"); // outfile  
           FileWriter fwriter = new FileWriter(outFile);  
           writer = new BufferedWriter(fwriter);  
           FileReader freader = new FileReader(inFile);  
           reader = new BufferedReader(freader);  
        int numCases = Integer.parseInt(reader.readLine());  
           System.out.println("numcases = " + numCases);  
           for (int i = 0; i < numCases; ++i) {  
                System.out.println();  
                char[][] board = new char[4][4];  
                int curr;  
                char currC;  
                boolean notComplete = false;  
                for (int row = 0; row < 4; ++row) {  
                     String line = reader.readLine();// read thr row  
                     for (int col = 0; col < 4; ++col) {  
                          currC = line.charAt(col);  
                          board[row][col] = currC;  
                          System.out.print(currC);  
                          if (currC == '.') {  
                               notComplete = true;  
                          }  
                     }  
                     System.out.println();  
                }  
                checkScore(board, i, notComplete);  
                reader.readLine();  
           }  
           writer.close();  
      }  
      private static void checkScore(char[][] board, int caseNum,  
                boolean notComplete) throws IOException {  
           // TODO Auto-generated method stub  
           // check diagonals first  
           // first diagonal  
           int j = 0;  
           int xcount = 1;  
           int ycount = 1;  
           boolean tFound = false;  
           for (int i = 0; i < 4; ++i) {  
                if (board[i][j] == 'T') {  
                     ++xcount;  
                     ++ycount;  
                } else if (board[i][j] == 'X') {  
                     ++xcount;  
                } else if (board[i][j] == 'O') {  
                     ++ycount;  
                }  
                ++j;  
           }  
           if (xcount == 5) {  
                writer.write("Case #" + (caseNum + 1) + ": X won");  
                writer.newLine();  
                return;  
           }  
           if (ycount == 5) {  
                writer.write("Case #" + (caseNum + 1) + ": O won");  
                writer.newLine();  
                return;  
           }  
           // ///////////////////////////////////////////////////////////////////////  
           // second diagonal  
           j = 3;  
           xcount = 1;  
           ycount = 1;  
           tFound = false;  
           for (int i = 0; i < 4; ++i) {  
                if (board[i][j] == 'T') {  
                          ++xcount;  
                          ++ycount;  
                } else if (board[i][j] == 'X') {  
                          ++xcount;  
                } else if (board[i][j] == 'O') {  
                          ++ycount;  
                     }  
                --j;  
           }  
           if (xcount == 5) {  
                writer.write("Case #" + (caseNum + 1) + ": X won");  
                writer.newLine();  
                return;  
           }  
           if (ycount == 5) {  
                writer.write("Case #" + (caseNum + 1) + ": O won");  
                writer.newLine();  
                return;  
           }  
           // ////////////////////////////////////////////////////////////////////////  
           // checking rows and cols  
           for (int i = 0; i < 4; ++i) {  
                xcount = 1;  
                ycount = 1;  
                tFound = false;  
                for (int row = 0; row < 4; ++row) {  
                     if (board[row][i] == 'T') {  
                          ++xcount;  
                          ++ycount;  
                     } else if (board[row][i] == 'X') {  
                          ++xcount;  
                     } else if (board[row][i] == 'O') {  
                          ++ycount;  
                     }  
                }  
                if (xcount == 5) {  
                     writer.write("Case #" + (caseNum + 1) + ": X won");  
                     writer.newLine();  
                     return;  
                }  
                if (ycount == 5) {  
                     writer.write("Case #" + (caseNum + 1) + ": O won");  
                     writer.newLine();  
                     return;  
                }  
                xcount = 1;  
                ycount = 1;  
                tFound = false;  
                for (int col = 0; col < 4; ++col) {  
                     if (board[i][col] == 'T') {  
                          ++xcount;  
                          ++ycount;  
                     } else if (board[i][col] == 'X') {  
                          ++xcount;  
                     } else if (board[i][col] == 'O') {  
                          ++ycount;  
                     }  
                }  
                if (xcount == 5) {  
                     writer.write("Case #" + (caseNum + 1) + ": X won");  
                     writer.newLine();  
                     return;  
                }  
                if (ycount == 5) {  
                     writer.write("Case #" + (caseNum + 1) + ": O won");  
                     writer.newLine();  
                     return;  
                }  
           }  
           if (notComplete) {  
                writer.write("Case #" + (caseNum + 1) + ": Game has not completed");  
                writer.newLine();  
                return;  
           }  
           writer.write("Case #" + (caseNum + 1) + ": Draw");  
           writer.newLine();  
           return;  
      }  
 }  
codejam 2013 prob a



problem B : Lawnmower

you can check the problem statement from  codejam 2013 site:
https://code.google.com/codejam/contest/2270488/dashboard#s=p1

Answer

First we map the desired pattern into a two dimensional array.
The idea is to find an element in the pattern which will make it an impossible pattern. Such element will be the one that you cant cut it vertically or horizontally, because if you do you will mess up another element.

                                           codejam 2013 prob b

Therefore, we start by calculating the max elements for each row and maximum element in each column, then we loop on the array elements, if we found an element that is not maximum in its row and not maximum in its column we mark the pattern as impossible.

Coding

 import java.io.BufferedReader;  
 import java.io.BufferedWriter;  
 import java.io.File;  
 import java.io.FileReader;  
 import java.io.FileWriter;  
 import java.io.IOException;  
 public class qua2 {  
      static BufferedWriter writer;  
      static BufferedReader reader;  
      /**  
       * @param args  
       * @throws IOException  
       */  
      public static void main(String[] args) throws IOException {  
           File inFile = new File("input2.txt"); // input file  
           File outFile = new File("output2.out"); // outfile  
           FileWriter fwriter = new FileWriter(outFile);  
           writer = new BufferedWriter(fwriter);  
           FileReader freader = new FileReader(inFile);  
           reader = new BufferedReader(freader);  
           int numCases = Integer.parseInt(reader.readLine());  
           System.out.println("numcases = " + numCases);  
           // looping on number of cases  
           for (int i = 0; i < numCases; ++i) {  
                boolean impossible = false;  
                String[] intalizingString = reader.readLine().split(" ");  
                String rows = intalizingString[0];  
                String cols = intalizingString[1];  
                int N = Integer.parseInt(rows);  
                int M = Integer.parseInt(cols); // M---->cols  
                System.out.println("N-->rows = " + N);  
                System.out.println("M-->cols = " + M);  
                // creating the int array representing the lawn  
                int[][] lawn = new int[N][M];  
                // reading the array  
                for (int j = 0; j < lawn.length; ++j) {  
                     String line = reader.readLine();// read the row  
                     int spointer = 0;  
                     String nums[]=line.split(" ");  
                     for (int k = 0; k < lawn[j].length; ++k) {  
                          lawn[j][k] = Integer.parseInt(nums[k]);  
                          System.out.print(lawn[j][k] + " ");  
                          spointer = spointer + 2;  
                     }  
                     System.out.println();  
                }  
                // ///starting the algorithm/////  
                int[] maxRows = new int[N];  
                int[] maxCols = new int[M];  
                // calculating the max of each row  
                for (int row = 0; row < N; ++row) {  
                     int max = -1;  
                     for (int col = 0; col < M; ++col) {  
                          if (lawn[row][col] > max)  
                               max = lawn[row][col];  
                     }  
                     maxRows[row] = max;  
                }  
                // calculating the max of each column  
                for (int col = 0; col < M; ++col) {  
                     int max = -1;  
                     for (int row = 0; row < N; ++row) {  
                          if (lawn[row][col] > max)  
                               max = lawn[row][col];  
                     }  
                     maxCols[col] = max;  
                }  
                // checking each element  
                for (int row = 0; row < N; ++row) {  
                     if (impossible)  
                          break;  
                     for (int col = 0; col < M; ++col) {  
                          if (lawn[row][col] < maxRows[row]  
                                    && lawn[row][col] < maxCols[col]) {  
                               // pattern is impossible  
                               impossible = true;  
                               break;  
                          }  
                     }  
                }  
                if (impossible) {  
                     System.out.println("NO");  
                     writer.write("Case #" + (i + 1) + ": NO");  
                     writer.newLine();  
                } else {  
                     System.out.println("YES");  
                     writer.write("Case #" + (i + 1) + ": YES");  
                     writer.newLine();  
                }  
           }  
           writer.close();  
      }  
 }  
codejam 2013 prob b


problem C : Fair and Square

you can check the problem statement from  codejam 2013 site:
https://code.google.com/codejam/contest/2270488/dashboard#s=p2

Answer

Here we start form index zero, if the current index is palindrome  we check its square, if the square is outside the range, then we are done,else if the square is palindrome we increase the count, 


                                                               codejam 2013 prob c

Coding

 import java.io.BufferedReader;  
 import java.io.BufferedWriter;  
 import java.io.File;  
 import java.io.FileReader;  
 import java.io.FileWriter;  
 import java.io.IOException;  
 public class qual3 {  
      static BufferedWriter writer;  
      static BufferedReader reader;  
      public static void main(String[] args) throws IOException {  
           File inFile = new File("input3.txt"); // input file  
           File outFile = new File("output3.out"); // outfile  
           FileWriter fwriter = new FileWriter(outFile);  
           writer = new BufferedWriter(fwriter);  
           FileReader freader = new FileReader(inFile);  
           reader = new BufferedReader(freader);  
           int numCases = Integer.parseInt(reader.readLine());  
           System.out.println("numcases = " + numCases);  
           // looping on number of cases  
           double current = 0;  
           int count = 0;  
           for (int i = 0; i < numCases; ++i) {  
                String[] intalizingString = reader.readLine().split(" ");  
                String ss = intalizingString[0];  
                String es = intalizingString[1];  
                double start = Double.parseDouble(ss);  
                double end = Double.parseDouble(es);  
                System.out.println("start = " + start);  
                System.out.println("end = " + end);  
                count = 0;  
                for (double j = 0; j <= end; ++j) {  
                     String currS = getNumberFormated(j+"");  
                     //System.out.println(currS);  
                     double square = Math.pow(j, 2);  
                     if (square > end) {  
                          break;  
                     }  
                     if (square < start) {  
                          continue;  
                     }  
                     if (checkPalindrom(currS)) {  
                           square = Math.pow(j, 2);  
                          String sq = getNumberFormated(square+"");  
                          if (checkPalindrom(sq)) {  
                               ++count;  
                          }  
                     }  
                }  
                writer.write("Case #" + (i + 1) + ": " + count);  
                writer.newLine();  
           }  
           writer.close();  
      }  
      static boolean checkPalindrom(String num) {  
           int n = num.length();  
           for (int i = 0; i < n / 2; i++)  
                if (num.charAt(i) != num.charAt(n - i - 1))  
                     return false;  
           return true;  
      }  
      static String getNumberFormated(String number)  
      {  
           if(number.contains("E")){  
                String[] splited = number.split("E");  
                double zeros = Double.parseDouble(splited[1]);  
                String[] numParts = splited[0].split("\\.");  
                StringBuilder firstPart = new StringBuilder();  
                firstPart.append(numParts[0]+numParts[1]);  
                for (int i = 0; i < zeros; i++) {  
                firstPart.append("0");  
                }  
                return firstPart.toString();       
           }  
           return number.split("\\.")[0];  
      }  
 }  
codejam 2013 prob c



1 comment: