## Google Code Jam Global Round 1A

24 May

Okay so I didn’t make this time. I had enough solutions right to qualify but didn’t do it fast enough. And considering that the competition was on the same weekend that I had to move out of Princeton, I didn’t have the time or energy to do compete in Rounds 1B or 1C. But it’s all okay because I had a fun time and now summer is here! At least for the next two weeks before I have to get back and start summer research.

But regardless, below I have posted my solution to the first problem of Round 1A. I had a somewhat fast algorithm but nothing too special. Regardless, here is the source:

import java.util.*;
import java.io.*;

public class Join
{
private String filename;
private char[][] board;

public Join(String f)
{
filename = f;
openFiles();
}

private void openFiles()
{
Scanner s;

try
{
s = new Scanner(new File(filename));
int ct;

ct = s.nextInt();

for (int i = 0; i < ct; i++)
{
int N = s.nextInt();
int K = s.nextInt();

board = new char[N][N];

for (int j = 0; j < N; j++)
{
String line = s.next();

for (int k = 0; k < N; k++)
board[j][k] = line.charAt(k);
}
output(i + 1, process(K, N));
}

s.close();
}
catch (Exception e)
{
System.err.println("I/O error: " + e);
System.exit(0);
}
}

private String matchesRed(String tmp, String retval, int K)
{
String regexRed = ".*R{" + K + "}.*";

if (tmp.matches(regexRed))
{
if (retval.equals("Red"))
return retval;
if (retval.equals("Neither"))
retval = "Red";
else
retval = "Both";
}

return retval;
}

private String matchesBlue(String tmp, String retval, int K)
{
String regexBlue = ".*B{" + K + "}.*";

if (tmp.matches(regexBlue))
{
if (retval.equals("Blue"))
return retval;
if (retval.equals("Neither"))
retval = "Blue";
else
retval = "Both";
}

return retval;
}

private String process(int K, int N)
{
String retval = "Neither";
gravity(N);

// Check vertical
for (int i = 0; i < N; i++)
{
String tmp = new String(board[i]);

retval = matchesRed(tmp, retval, K);

if (retval.equals("Both"))
return retval;

retval = matchesBlue(tmp, retval, K);

if (retval.equals("Both"))
return retval;
}

// Check horizontal
for (int j = 0; j < N; j++)
{
String tmp = "";

for (int i = 0; i < N; i++)
tmp += board[i][j];

retval = matchesRed(tmp, retval, K);

if (retval.equals("Both"))
return retval;

retval = matchesBlue(tmp, retval, K);

if (retval.equals("Both"))
return retval;
}

// Check diagonal 1
for (int i = 0; i < N; i++)
{
int orig = i;
String tmp = "";

for (int j = 0; i >= 0;)
tmp += board[i--][j++];

retval = matchesRed(tmp, retval, K);

if (retval.equals("Both"))
return retval;

retval = matchesBlue(tmp, retval, K);

if (retval.equals("Both"))
return retval;

i = orig;
}

int i = N - 1;

for (int j = 0; j < N; j++)
{
int orig = j;
String tmp = "";

for (; j < N;)
tmp += board[i--][j++];

retval = matchesRed(tmp, retval, K);

if (retval.equals("Both"))
return retval;

retval = matchesBlue(tmp, retval, K);

if (retval.equals("Both"))
return retval;

i = N - 1;
j = orig;
}

// Check diagonal 2
for (int j = N-1; j >= 0; j--)
{
int orig = j;
String tmp = "";

for (i = 0; j < N;)
tmp += board[i++][j++];

retval = matchesRed(tmp, retval, K);

if (retval.equals("Both"))
return retval;

retval = matchesBlue(tmp, retval, K);

if (retval.equals("Both"))
return retval;

j = orig;
}

int j = 0;
for (i = 0; i < N - K; i++)
{
int orig = i;
String tmp = "";

for (; i < N;)
tmp += board[i++][j++];

retval = matchesRed(tmp, retval, K);

if (retval.equals("Both"))
return retval;

retval = matchesBlue(tmp, retval, K);

if (retval.equals("Both"))
return retval;

j = 0;
i = orig;
}

return retval;
}

private void gravity(int N)
{
int j;

for (int i = 0; i < N; i++)
{
String tmp = "";

for (j = 0; j < N; j++)
if (board[i][j] != '.')
tmp += board[i][j];

int diff = N - tmp.length();

for (j = 0; j < diff; j++)
board[i][j] = '.';

for (; j < N; j++)
board[i][j] =  tmp.charAt(j - diff);

}
}

private void output(int caseNum, String result)
{
System.out.println("Case #" + caseNum + ": " + result);
}

public static void main(String args[])
{
Join app = new Join(args[0]);
}
}


So basically, I first took the input and put it inside a two-dimensional character array. Then, I implemented gravity (if only it were so easy always!). I made the observation that all gravity does is move the non-period characters to the right side and pushes all intermediate period characters to the left. Originally, I had a recursive algorithm to do this, but this was way simpler. So, I parsed each line and collected the non-period characters in a temporary string. Then, I added sufficient periods as padding and then just threw my collected string at the end of each line. Do this N times, and you’re done. Of course, I could’ve used some regex fu to make this even faster, but it was straightforward enough and did the job in $\mathcal{O}(N^2)$ which is the best asymptotic performance you can get (gotta read every character..).

Then, I did a series of checks to see if any K consecutive letters had been formed as a result. To do so, I decided that the simplest way to do so would be to just read in my array vertically, horizontally, and by diagonals and check to see a match. Rather than dealing with messy DFAs, a one-line regex check did the trick. Here, the regex I used was constructed as the following: ".*R{" + K + "}.*" for the red pieces. It’s a really simple one and basically it just looks at an arbitrary number of lead characters (“.*”) and then checks for exactly K characters of value “R” (R{K}) and then ignores an arbitrary number of characters that trail (“.*”). Of course, the regex string has to actually have a number in the place of K, which is why I constructed in this way. Similarly, to check for blue pieces, I just used ".*B{" + K + "}.*";.

You can check out the code to see how verbose, ugly, and unoptimized it is. But given that the largest value for N was 50, doing about 5 traversals of a 50×50 grid was acceptable. And in fact I was correct on this point. For the small input, the code run in 0.298s and for the large input, it runs in 0.980s. Good enough.