Home ›

Google Code Jam - Rotate

Nico Heid's picture
by Nico Heid on Sun, 08/15/2010 - 17:33
in

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

  1. public static void fakeRotate(char[][] board) {
  2.  
  3.     for (int i = 0; i < N; i++) {
  4.         for (int j = N - 1; j >= 0; j--) {
  5.             if (board[i][j] != '.') {
  6.                 // push to right
  7.                 int m = 1;
  8.                 while ((j + m) < N && board[i][j + m] == '.') {
  9.                     board[i][j + m] = board[i][j + (m - 1)];
  10.                     board[i][j + (m - 1)] = '.';
  11.                     m++;
  12.                 }
  13.             }
  14.         }
  15.     }
  16. }

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.

  1. public static void checkForWinner(char[][] board) {
  2.     boolean redWins = false;
  3.     boolean blueWins = false;
  4.  
  5.     for (int i = 0; i < N; i++) {
  6.         for (int j = 0; j < N; j++) {
  7.             if (board[i][j] != '.') {
  8.  
  9.                 // winning once is good enough
  10.                 if (board[i][j] == 'B' && blueWins == true) {
  11.                     break;
  12.                 }
  13.                 if (board[i][j] == 'R' && redWins == true) {
  14.                     break;
  15.                 }
  16.  
  17.                 // check to the right
  18.                 int m = 1;
  19.                 while (j + m < N && board[i][j + m] == board[i][j]) {
  20.                     if (++m == K) {
  21.                         switch (board[i][j]) {
  22.                         case 'R':
  23.                             redWins = true;
  24.                             System.out.println("RED");
  25.                             break;
  26.                         case 'B':
  27.                             blueWins = true;
  28.                             System.out.println("BLUE");
  29.                             break;
  30.                         }
  31.                     }
  32.                 }
  33.  
  34.                 // check bottom
  35.                 m = 1;
  36.                 while (i + m < N && board[i + m][j] == board[i][j]) {
  37.                     if (++m == K) {
  38.                         switch (board[i][j]) {
  39.                         case 'R':
  40.                             redWins = true;
  41.                             System.out.println("RED");
  42.                             break;
  43.                         case 'B':
  44.                             blueWins = true;
  45.                             System.out.println("BLUE");
  46.                             break;
  47.                         }
  48.                     }
  49.                 }
  50.  
  51.                 // check diagonal bottom
  52.                 m = 1;
  53.                 while (i + m < N && j + m < N && board[i + m][j + m] == board[i][j]) {
  54.                     if (++m == K) {
  55.                         switch (board[i][j]) {
  56.                         case 'R':
  57.                             redWins = true;
  58.                             System.out.println("RED");
  59.                             break;
  60.                         case 'B':
  61.                             blueWins = true;
  62.                             System.out.println("BLUE");
  63.                             break;
  64.                         }
  65.                     }
  66.                 }
  67.  
  68.                 // check diagonal top
  69.                 m = 1;
  70.                 while (i - m >= 0 && j + m < N && board[i - m][j + m] == board[i][j]) {
  71.                     if (++m == K) {
  72.                         switch (board[i][j]) {
  73.                         case 'R':
  74.                             redWins = true;
  75.                             System.out.println("RED");
  76.                             break;
  77.                         case 'B':
  78.                             blueWins = true;
  79.                             System.out.println("BLUE");
  80.                             break;
  81.                         }
  82.                     }
  83.                 }
  84.  
  85.             }
  86.  
  87.         }
  88.  
  89.     }
  90.  
  91. }

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

Comments

Twitter Trackbacks for Google Code Jam - Rotate | united-co's picture
Pingback
Twitter Trackbacks for Google Code Jam - Rotate | united-co (not verified) - Sun, 08/15/2010 - 18:12

[...] Google Code Jam - Rotate | united-coders.com united-coders.com/nico-heid/google-code-jam-rotate – view page – cached It's time for some basic finger exercise. The Google Code Jam Rotate is very trivial, so relax and fire up your IDE. Tweets about this link [...]

Google Code Jam - Rotate | united-coders.com's picture
Pingback
Google Code Jam - Rotate | united-coders.com (not verified) - Sun, 08/15/2010 - 19:52

[...] post: Google Code Jam - Rotate | united-coders.com Filed under Uncategorized « SPD: Heil will Spitzensteuersatz erst ab 80.000 Euro - [...]

The rotate google contest in 15 lines | united-coders.com's picture
Pingback
The rotate google contest in 15 lines | united-coders.com (not verified) - Thu, 08/19/2010 - 13:46

[...] rotate example nico last week reported was funny to solve: No rotating needed! Read the complete problem [...]

Solutions for the google code jam 2012 qualify round | unite's picture
Pingback
Solutions for the google code jam 2012 qualify round | unite (not verified) - Mon, 04/16/2012 - 06:17

[...] rotate problem from the Round 1A 2010 from nico and my [...]