ECOO 2014 Regional - Problem #2: Black and Grey

The problem:

You have a 10x10 board made of tiles that are black on one side and light grey on the other, but right now they're all showing their grey side. Imagine the patterns you could make! For example, suppose you imposed a grid over the tiles to divide them into squares of the same size with no tiles left over. There are four grid sizes that would work: 1x1, 2x2, 5x5 and 10x10, as shown below (the tiles are in grey, the grids are shown with black lines).

Now imagine that each grid is a checkerboard where the top left square is a black square, like this:

Now imagine flipping over all the tiles that are underneath black grid squares. Do the 1x1 grid first, then 2x2, then 5x5, then 10x10. You're going to get some cool patterns. The pictures below show the results.

DATA21.txt (DATA22.txt for the second try) will contain 10 test cases. Each test case consists of six lines. The first line contains a single integer N (1 ≤ N ≤ 1000000) representing the size of the board. The next 5 lines each contain two integers R and C, separated by a space. R and C represent the row and column of a tile on the board (1 ≤ R,C ≤ N). Rows are numbered top down starting at 1 and columns are numbered left to right starting at 1. Your job is to simulate the pattern-making process described above for an NxN board, and then output a single line of 5 characters representing the five tiles in the locations given in the test case, in the order they originally appeared in the file. Each tile should be represented by an uppercase B or G depending on whether it is showing its black or grey side in the final pattern. Note that there are 2 test cases in the sample data below, but the real data files will contain 10 test cases.

Sample Input	5 5	10 10
10	12
5 1	6 6	Sample Output
5 2	7 7	GBBGG
5 3	8 8	GGGGG
5 4	9 9

My solution (in Java):

import java.util.ArrayList;
import java.util.Scanner;
import java.io.File;

public class Problem_2_Black_And_Grey {

    public static void main(String[] args) {

        try {
            Scanner file = new Scanner(new File("C:\\Users\\Mike\\Desktop\\problem_2_black_and_grey_DATA21.txt"));

            while(file.hasNextLine()) {

                ArrayList<String> dataSet = new ArrayList<String>(); // ArrayList that represents the current data set for the board

                // for the next 6 lines in the file (current data set for the board)
                for (int l = 0; l < 6; l++) {
                    dataSet.add(file.nextLine());
                }

                // get the size of the board and then remove it from the data set (it's unneeded after recorded)
                int n = Integer.parseInt(dataSet.get(0));
                dataSet.remove(0);
                
                // find largest row and column in any of the six tiles
                int maxRow = 0, maxCol = 0;
                for (String s : dataSet) {
                    String[] rowAndCol = s.split("\\s+"); // split by whitespace. array has two elements: row and column
                    
                    int row = Integer.parseInt(rowAndCol[0]);
                    int col = Integer.parseInt(rowAndCol[1]);
                    
                    // if this row is larger than the previous largest row, this row is the new largest row
                    if (row > maxRow) maxRow = row;
                    if (col > maxCol) maxCol = col;
                }

                // board and transformed board matrices: are used to perform transformations throughout the stages
                // the dimensions are reduced to the maximum row and column values. the board won't need to be any
                // larger than that because no tiles on the board outside of this range will be tested (calculated above)
                int[][] board = new int[maxRow][maxCol], transformed = new int[maxRow][maxCol];

                ArrayList<Integer> factors = getFactors(n); // factors of the board dimensions (not reduced board)
                
                for (int factor : factors) { // for every factor
                    
                    int gridDimensions = n / factor; // the square dimensions of the grids inside the larger board
                    int numberOfGrids = factor; // the number of grids per side inside the larger board
                    
                    // make the checkerboards for each factor
                    for (int i = 0; i < numberOfGrids; i++) { // for every grid in each row
                        for (int j = 0; j < numberOfGrids; j++) { // for every grid in each column
                            // colour each grid going row by row
                            // i and j increment each grid
                            // k and l increment each tile in each grid
                            // start at the beginning of a grid (i * gridDimensions) and go until the end of the grid is reached (i * gridDimensions + gridDimensions)
                            // the + gridDimensions would mean that it's iterating over a new grid
                            // k < maxRow just makes sure that it's iterating within the reduced board array
                            for (int k = i * gridDimensions; k < i * gridDimensions + gridDimensions && k < maxRow; k++) {
                                for (int l = j * gridDimensions; l < j * gridDimensions + gridDimensions && l < maxCol; l++) {
                                    // if one of the row and column is even and one is odd, the grid is grey (if the checkerboard has the top left grid being black)
                                    if ( (i+j)%2 == 1) {
                                        board[k][l] = 0; // grey tile
                                    } else {
                                        board[k][l] = 1; // black tile
                                    }
                                }
                            }
                        }
                    }
                    
                    // add matrices (board matrix, which is the factored checkerboard, and transformed matrix, which is the last transformed board by adding, but will become the new transformed board)
                    // I call it adding the matrices, but it's really just putting them together and getting the resultant matrix
                    for (int i = 0; i < maxRow; i++) {
                        for (int j = 0; j < maxCol; j++) {
                            
                            // this is like an XOR operation: if either one is black, but not both, the result is black; otherwise (both the same), the result is grey.
                            if (transformed[i][j] == board[i][j]) { // if both tiles are the same colour
                                transformed[i][j] = 0; // turns grey
                            } else { // different colours
                                transformed[i][j] = 1; // turns black
                            }
                            
                            /* Another way of doing is using the actual XOR operator:
                            if ((transformed[i][j] ^ board[i][j]) == 1) { // use XOR operator to test if the tiles are not the same colour (one of them is black, but not both; or the same thing with grey)
                                transformed[i][j] = 1; // turns black                       
                            } else { // same colour; failed the XOR test
                                transformed[i][j] = 0; // turns grey
                            }*/
                        }
                    }
                }
                
                for (int i = 0; i < dataSet.size(); i++) { // for every tile to be looked at in the data set
                    int row = Integer.parseInt(dataSet.get(i).split("\\s+")[0]); // split the row and column string for the tile by whitespace and the first element will be the row
                    int col = Integer.parseInt(dataSet.get(i).split("\\s+")[1]); // second element is the column
                    
                    // find the tiles that the data set requests to be looked at
                    // and remember to subtract 1 from the array index because arrays start indexing at 0, but the data set starts at 1
                    if (transformed[row-1][col-1] == 0) {
                        System.out.print("G"); // grey
                    } else {
                        System.out.print("B"); // black
                    }
                }
                System.out.println();
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    /* returns the factors (as an ArrayList of integers) of the parameter n
       and this needs to return the list in descending order, hence the direction of the loops */
    public static ArrayList<Integer> getFactors(int n) {

        ArrayList<Integer> factors = new ArrayList<Integer>(); // ArrayList of factors to be returned
        
        for (int i = n; i >= Math.sqrt(n); i--) { // only test up to the square root of the number because that will contain exactly half of the factors, excluding the square root (increases speed)
            if (n % i == 0) factors.add(i); // if the looping variable is a factor of the number, add it to the factors list
        }

        int size = factors.size(); // size of the factors

        // add the other half of the factors of the number
        for (int i = size - 1; i >= 0; i--) { // for every factor in the factors list
            if (factors.get(i) != Math.sqrt(n)) { // only add the corresponding factor if the factor is not the square root of the number (the corresponding factor is itself - a duplicate)
                factors.add(n / factors.get(i)); // add the corresponding factor (the number divided by this factor) to the list
            }
        }
        return factors;
    }
}

10
5 1
5 2
5 3
5 4
5 5
12
6 6
7 7
8 8
9 9
10 10

GBBGG
GGGGG

1
1 1
1 1
1 1
1 1
1 1
5
4 1
5 1
1 3
4 3
4 5
27
14 1
24 22
15 8
13 22
4 20
319
307 214
234 311
137 19
267 154
240 109
1538
783 351
1506 1197
477 439
1325 842
784 418
13711
2348 7747
5816 1804
10205 2840
10332 12335
1277 2310
34214
25681 30923
32867 2906
18070 18771
9621 21171
33276 19876
614576
173191 304281
117755 193532
85644 136805
247497 148351
315064 276058
410114
3527 330138
69103 115910
251323 359304
328877 71422
409274 89398
587138
183328 314509
437196 203282
169760 324622
131740 301442
352404 158612

BBBBB
BGGBB
GGGBB
GGBGG
BBBBG
BGBBB
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at Problem_2_Black_And_Grey.main(Problem_2_Black_And_Grey.java:41)

5
3 3
1 5
1 1
5 5
5 1
41
35 14
3 38
8 41
23 4
22 40
82
47 37
45 34
36 68
20 26
68 67
1445
101 370
101 430
431 255
1126 654
687 1160
6702
4809 523
4257 5094
6414 1986
5624 4159
6673 39
9594
1683 3751
8567 7491
8723 8739
1137 5924
231 8237
279066
76150 149858
5431 157348
275668 30742
187266 148885
197615 236474
789635
120147 481547
327898 252985
477382 285895
595923 103869
154417 62088
337263
22311 96668
30460 131774
109613 15105
128666 259127
90148 138195
778168
132111 466313
765166 582561
182188 650557
96282 765697
482808 675730

GGGGG
BBBBG
GGBBB
GBBGG
GBBGB
GGBGG
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at Problem_2_Black_And_Grey.main(Problem_2_Black_And_Grey.java:41)

         Created: July 5, 2014
Completed in full by: Michael Yaworski