Yos Riady software craftsman 🌱

Google Code Jam 2013 Solutions - Qualification

The Qualification Round for Code Jam 2013 kicked off on April 12. Here are my submissions for Google’s CodeJam problems, written in Java.

You can also check out all the solutions in the Github repo.

Tic-Tac-Toe-Tomek

Tic-Tac-Toe-Tomek is a game played on a 4 x 4 square board. The board starts empty, except that a single ‘T’ symbol may appear in one of the 16 squares. There are two players: X and O. They take turns to make moves, with X starting. In each move a player puts her symbol in one of the empty squares. Player X’s symbol is ‘X’, and player O’s symbol is ‘O’.

After a player’s move, if there is a row, column or a diagonal containing 4 of that player’s symbols, or containing 3 of her symbols and the ‘T’ symbol, she wins and the game ends. Otherwise the game continues with the other player’s move. If all of the fields are filled with symbols and nobody won, the game ends in a draw. See the sample input for examples of various winning positions.

Given a 4 x 4 board description containing ‘X’, ‘O’, ‘T’ and ‘.’ characters (where ‘.’ represents an empty square), describing the current state of a game, determine the status of the Tic-Tac-Toe-Tomek game going on. The statuses to choose from are:

“X won” (the game is over, and X won) “O won” (the game is over, and O won) “Draw” (the game is over, and it ended in a draw) “Game has not completed” (the game is not over yet) If there are empty cells, and the game is not over, you should output “Game has not completed”, even if the outcome of the game is inevitable.

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

public class TomekSolver {

	private static BufferedReader bufferedDataFile;
	private static String line;
	String newline = System.getProperty("line.separator");
	static String[][] board = new String[4][4];

	//returns numSymbols plus T
	public static int countHorizontal(String symbol, int row){
		int count = 0;
		for(int i = 0; i < 4; i++){
			if(board[row][i].equals(symbol) || board[row][i].equals("T")){
				count++;
			}
		}
		return count;
	}

	public static int countVertical(String symbol, int col){
		int count = 0;
		for(int i = 0; i < 4; i++){
			if(board[i][col].equals(symbol) || board[i][col].equals("T")){
				count++;
			}
		}
		return count;
	}

	public static boolean isFilled(String[][] board){
		for(int i = 0;i < 4;i++){
			for(int j = 0; j < 4; j++){
				//System.out.print(board[i][j]);
				if(board[i][j].equals(".")){
					return false;
				}
			}
		}
		return true;
	}


	public static int countDiagonals(String symbol){
		int count1 = 0;
		int count2 = 0;
		for(int i = 0; i < 4;i++){
			if(board[i][i].equals(symbol) || board[i][i].equals("T")){
				count1++; //left downwards diagonal
			}
			if(board[i][3-i].equals(symbol) || board[i][3-i].equals("T")){
				count2++; //right upwards diagonal
			}
		}

		return Math.max(count1,count2);
	}


	public static void main(String[] args) {
		String filename = "A-large.in";
		FileReader dataFile;
		try {
			dataFile = new FileReader(filename);
			bufferedDataFile = new BufferedReader(dataFile);
			final int numBoards = Integer.parseInt(bufferedDataFile.readLine());

			//if there is a row, column or a diagonal containing 4 of that player's symbols,
			//or containing 3 of her symbols and the 'T' symbol, she wins and the game ends.

			for(int j = 0; j < numBoards; j++){
			for(int i = 0 ; i< 4;i++){
				line = bufferedDataFile.readLine();
				for(int k = 0; k < line.length();k++){
					board[i][k] = line.substring(k,k+1);
				}
			}

			int maxXHorizontal = 0;
			for(int i=0;i<4;i++){
				maxXHorizontal = Math.max(maxXHorizontal,countHorizontal("X",i));
			}

			int maxOHorizontal = 0;
			for(int i=0;i<4;i++){
				maxOHorizontal = Math.max(maxOHorizontal,countHorizontal("O",i));
			}

			int maxXVertical = 0;
			for(int i=0;i<4;i++){
				maxXVertical = Math.max(maxXVertical,countVertical("X",i));
			}

			int maxOVertical = 0;
			for(int i=0;i<4;i++){
				maxOVertical = Math.max(maxOVertical,countVertical("O",i));
			}

			int xDiagonals = countDiagonals("X");
			int oDiagonals = countDiagonals("O");

			int maxX = Math.max(xDiagonals ,Math.max(maxXHorizontal,maxXVertical));
			int maxO = Math.max(oDiagonals ,Math.max(maxOHorizontal,maxOVertical));

			if(maxX == maxO && isFilled(board)){
				System.out.println("Case #" + (j+1) + ": Draw");
			} else if(maxX == 4){
				System.out.println("Case #" + (j+1) + ": X won");
			} else if(maxO == 4){
				System.out.println("Case #" + (j+1) + ": O won");
			} else {
				System.out.println("Case #" + (j+1) + ": Game has not completed");
			}
			line = bufferedDataFile.readLine(); //newline
			}

		} catch (FileNotFoundException e) {
			System.err.println("File not found!");
			e.printStackTrace();
		} catch (IOException e) {
			System.err.println("io exception!");
			e.printStackTrace();
		}
	}
}

Lawnmower

Alice and Bob have a lawn in front of their house, shaped like an N metre by M metre rectangle. Each year, they try to cut the lawn in some interesting pattern. They used to do their cutting with shears, which was very time-consuming; but now they have a new automatic lawnmower with multiple settings, and they want to try it out.

The new lawnmower has a height setting - you can set it to any height h between 1 and 100 millimetres, and it will cut all the grass higher than h it encounters to height h. You run it by entering the lawn at any part of the edge of the lawn; then the lawnmower goes in a straight line, perpendicular to the edge of the lawn it entered, cutting grass in a swath 1m wide, until it exits the lawn on the other side. The lawnmower’s height can be set only when it is not on the lawn.

Alice and Bob have a number of various patterns of grass that they could have on their lawn. For each of those, they want to know whether it’s possible to cut the grass into this pattern with their new lawnmower. Each pattern is described by specifying the height of the grass on each 1m x 1m square of the lawn.

The grass is initially 100mm high on the whole lawn.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;

public class Lawnmower {
	public static void main(String[] args){
		try {

			BufferedReader br = new BufferedReader(new FileReader("B-large.in"));
			FileWriter fstream = new FileWriter("output.txt");
			BufferedWriter out = new BufferedWriter(fstream);

			int casenum = Integer.parseInt(br.readLine());
	        for(int i = 0; i < casenum; i++){
	        	String[] s = br.readLine().split(" ");
	        	int row = Integer.parseInt(s[0]);
	        	int col = Integer.parseInt(s[1]);

	        	ArrayList<ArrayList<Integer>> al = new ArrayList<ArrayList<Integer>>();
	        	for(int r = 0; r < row; r++){
	        		al.add(new ArrayList<Integer>());
	        		String[] s1 = br.readLine().split(" ");

	        		for(int c = 0; c < col; c++){
	        			al.get(r).add(Integer.parseInt(s1[c]));
	        		}
	        	}

	        	while(true){
	        		int k = 0;
	        		while(k < al.size()){
	        			if (al.get(k).isEmpty()){
	        				al.remove(k);
	        				continue;
	        			}
	        			k++;
	        		}

	        		if(al.isEmpty())
	        			break;

	        		int min = Integer.MAX_VALUE;
	        		int minr = 0;
	        		int minc = 0;
	        		// We find min
		        	for(int r = 0; r < al.size(); r++){
		        		for(int c = 0; c < al.get(0).size(); c++){
		        			if (min > al.get(r).get(c)){
		        				minr = r;
		        				minc = c;
		        				min = al.get(r).get(c);
		        			}
		        		}
		        	}


		        	int numc = 0, numr = 0;
		        	boolean rb = true, cb = true;
		        	// We check the row		        	
		        	for(int j = 0; j < al.get(minr).size(); j++)
		        		if (al.get(minr).get(j) == min)
		        			numr++;

		        	if (numr != al.get(minr).size())
		        		rb = false;

		        	// We check the whole column of the global min
		        	for(int j = 0; j < al.size(); j++)
		        		if (al.get(j).get(minc) == min)
		        			numc++;
		        	if (numc != al.size())
		        		cb = false;

		        	// impossible case
		        	if((cb == false) && (rb == false)){
		        		out.write("Case #"+(i+1)+": NO\n");
		        		break;
		        	}


		        	if (cb){

		        		for(int j = 0; j < al.size(); j++)
			        		al.get(j).remove(minc);
		        		continue;
		        	}

		        	else if(rb){

			        	al.remove(minr);
		        		continue;
		        	}
	        	}
	        	if(al.size() !=0)	continue;
	        	out.write("Case #"+(i+1)+": YES\n");
	        }
	        out.close();
	    } catch (Exception e) {
	        System.err.println("Error:" + e.getMessage());
	    }
	}
}

Fair and Square

Little John likes palindromes, and thinks them to be fair (which is a fancy word for 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).

He recently became interested in squares as well, and formed the definition of a fair 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 fair and square (being palindromes and squares, respectively, of 1, 3 and 11), while 16, 22 and 676 are not fair 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 fair and square numbers. Your task is, given an interval Little John is searching through, to tell him how many fair and square numbers are there in the interval, so he knows when he has found them all.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.math.BigInteger;

public class FairandSquare {

	public static boolean isPalindrome(int number) {
		return number == reverse(number);
	}

	public static int reverse(int number) {
		int result = 0;
		while (number != 0) {
			int remainder = number % 10;
			result = result * 10 + remainder;
			number /= 10;
		}
		return result;
	}

	public final static boolean isPerfectSquare(long n)
	{
	  if (n < 0)
	    return false;

	  long tst = (long)(Math.sqrt(n) + 0.5);
	  return tst*tst == n;
	}

	public static void main(String[] args){

		try {
			BufferedReader br = new BufferedReader(new FileReader("C-large-1.in"));
			FileWriter fstream = new FileWriter("output.txt");
			BufferedWriter out = new BufferedWriter(fstream);
			int numCases = Integer.parseInt(br.readLine());

			for(int i =0; i<numCases;i++){
				String[] s = br.readLine().split(" ");
				int low = Integer.parseInt(s[0]);
	        	int high = Integer.parseInt(s[1]);
	        	int count = 0;
	        	//We count how many fair and square numbers between low and high inclusive
	        	for(int j = low; j < high+1; j++){
	        		if(isPalindrome(j) && isPerfectSquare(j)){
	        			if(isPalindrome((int)Math.sqrt(j))){
	        				count++;
	        			}
	        		}		
	        	}
	        	out.write("Case #"+(i+1)+": " + count + "\n");
			}
			out.close();
	    } catch (Exception e) {
	        System.err.println("Error:" + e.getMessage());
	    }
	}
}

Author

Yos is a software craftsman based in Singapore.

📬 Subscribe to my newsletter

Get notified of my latest articles by providing your email below.


Going Serverless book

Interested to find out more about serverless? Going Serverless teaches you how to build scalable applications with the Serverless framework and AWS Lambda. You'll learn how to design, develop, test, deploy, and secure Serverless applications from planning to production.

Learn More →