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