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 Python):

# 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 */
def getFactors(n):

    factors = [] # list of factors to be returned

    i = n
    while (i >= n ** 0.5): # 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.append(i) # if the looping variable is a factor of the number, add it to the factors list
        i -= 1

    size = len(factors) # size of the factors

    # add the other half of the factors of the number
    for i in range(size - 1, -1, -1): # for every factor in the factors list
        if (factors[i] != n ** 0.5): # only add the corresponding factor if the factor is not the square root of the number (the corresponding factor is itself - a duplicate)
            factors.append(int(n / factors[i])) # add the corresponding factor (the number divided by this factor) to the list

    return factors;

list = []

# read in the file to list
with open('C:\\Users\\Mike\\Desktop\\problem_2_black_and_grey_DATA21.txt') as f:
    for line in f:
        list.append(line.split('\n')[0])

index = 0

while index < len(list):

    # generate this data set in file (data sets come in increments of six lines)
    dataSet = []
    for i in range(index, index + 6):
        dataSet.append(list[i])
    index += 6
    
    # do stuff with data set
    n = (int)(dataSet[0])
    dataSet.remove(dataSet[0]) # don't need it anymore

    # find largest row and column in any of the six tiles
    maxRow = 0
    maxCol = 0
    for s in dataSet:
        rowAndCol = s.split() # split by whitespace. array has two elements: row and column
        row = (int)(rowAndCol[0])
        col = (int)(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)
    board = [[0 for x in range(maxCol)] for x in range(maxRow)]
    transformed = [[0 for x in range(maxCol)] for x in range(maxRow)]
    
    factors = getFactors(n) # factors of the board dimensions (not reduced board)
    
    for factor in factors: # for every factor
        
        gridDimensions = n / factor # the square dimensions of the grids inside the larger board
        numberOfGrids = factor # the number of grids per side inside the larger board
        
        # make the checkerboards for each factor
        for i in range(0, numberOfGrids): # for every grid in each row
            for j in range(0, numberOfGrids): # 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
                k = (int)(i * gridDimensions)
                while k < i * gridDimensions + gridDimensions and k < maxRow:
                    l = (int)(j * gridDimensions)
                    while l < j * gridDimensions + gridDimensions and l < maxCol:
                        # 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
                        l += 1
                    k += 1
        
        # 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 i in range(0, maxRow):
            for j in range(0, maxCol):
                
                # 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 squares 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

    result = ""
    for i in range(0, len(dataSet)): # for every tile to be looked at in the data set
        row = (int)(dataSet[i].split()[0]) # split the row and column string for the tile by whitespace and the first element will be the row
        col = (int)(dataSet[i].split()[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:
            result += "G" # grey
        else:
            result += "B" # black
            
    print(result) # print the result of this data set

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

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

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