It’s time for some basic finger exercise. The Google Code Jam Rotate is very trivial, so relax and fire up your IDE.

I was a bit lazy, so there is no reading of the input sets, just a two-dimensional array and two functions

### Rotating

As the Google solution pointed out, there is actually no need to really rotate the 2dim array. Just push everything to the right, as if gravity would be to the right. That’s the same as rotating everything and keeping gravity towards the bottom. But we save a few lines this way.

So here is the “gravity from the right” code

public static void fakeRotate(char[][] board) { for (int i = 0; i < N; i++) { for (int j = N - 1; j >= 0; j--) { if (board[i][j] != '.') { // push to right int m = 1; while ((j + m) < N && board[i][j + m] == '.') { board[i][j + m] = board[i][j + (m - 1)]; board[i][j + (m - 1)] = '.'; m++; } } } } }

### Checking for a winner

Now we have everything ready to look for a winner. I decided to start from the top left and walk through the game board step by step. I keep going right till I'm at the end, then go to the beginning of the next line.

Progressing this way, I only need to check in four directions. Towards right, bottom, diagonally upwards-right and diagonally downwards-right.

public static void checkForWinner(char[][] board) { boolean redWins = false; boolean blueWins = false; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (board[i][j] != '.') { // winning once is good enough if (board[i][j] == 'B' && blueWins == true) { break; } if (board[i][j] == 'R' && redWins == true) { break; } // check to the right int m = 1; while (j + m < N && board[i][j + m] == board[i][j]) { if (++m == K) { switch (board[i][j]) { case 'R': redWins = true; System.out.println("RED"); break; case 'B': blueWins = true; System.out.println("BLUE"); break; } } } // check bottom m = 1; while (i + m < N && board[i + m][j] == board[i][j]) { if (++m == K) { switch (board[i][j]) { case 'R': redWins = true; System.out.println("RED"); break; case 'B': blueWins = true; System.out.println("BLUE"); break; } } } // check diagonal bottom m = 1; while (i + m < N && j + m < N && board[i + m][j + m] == board[i][j]) { if (++m == K) { switch (board[i][j]) { case 'R': redWins = true; System.out.println("RED"); break; case 'B': blueWins = true; System.out.println("BLUE"); break; } } } // check diagonal top m = 1; while (i - m >= 0 && j + m < N && board[i - m][j + m] == board[i][j]) { if (++m == K) { switch (board[i][j]) { case 'R': redWins = true; System.out.println("RED"); break; case 'B': blueWins = true; System.out.println("BLUE"); break; } } } } } } }

That's a bit of copy and paste, maybe you have a better solution.

That was already it. Not much to say, is there?

If you're bored you can do some improvements and share it in the comments.

- optimize the code for checking for a winner, e.g. stop checking if the space is not sufficient for K stones to win
- use multiple threads to check the board
- write a parser to read the input file from the Google Code Jam

I hope you had some fun, questions and improvements are welcome. If you want to submit a patch write me using the contact form.

The code can be found as usual on github