CodeJam 2010 - Round 1A - (A)Rotate - Solution

Now that I'm practicing for the CodeJam 2011 I've started doing (or re-doing in fact) some problems from previous years.

This is the solution from problem A in Round 1A which was called "Rotate".

You can find the statement of the problem in the Google CodeJam page or follow this link.

The solution is quite straightforward: load, rotate, apply gravity and verify. Nothing really exciting.

I do the first two things at once, I load the matrix rotated. In order to accomplish that you have to notice that each row is going to be a column and that the first row becomes the last column, the second column becomes the column n-1, etc. Knowing that it's pretty obvious how I do that.

As gravity is applied per column, meaning that one column doesn't affect the effect of gravity in other column I apply it as soon as I finished loading a column. The algorithm is quite simple: I process each position from bottom to top and while there's a point I shift the string from top to bottom filling with useless characters.

And for searching I just brute-force on each row, column and diagonal (in both directions) line to see if blue or red have achieved K characters together. And based in those findings I return 'Both', 'Blue', 'Red' or 'Neither'.

The python file is GCJ2010-1A-A.py and it contains the following:

def solve():
    n, K = map(int, input().split(' '))
    board = [['.' for i in range(n)] for j in range(n)]
    for i in range(n-1, -1, -1):
        # Load column n-i-1
        line = input()
        for j in range(n):
            board[j][i] = line[j]
        # Apply gravity in that column
        for j in range(n-1, -1, -1):
            while board[j][i] == '.':
                for k in range(j, 0, -1):
                    board[k][i] = board[k-1][i]
                board[0][i] = '#'

    blue = False
    red = False

    # Check for Vertical and horizontal
    for i in range(n):
        s = ''.join(board[i])
        if 'B' * K in s:
            blue = True
        if 'R' * K in s:
            red = True
        s = ''.join(board[j][i] for j in range(n))
        if 'B' * K in s:
            blue = True
        if 'R' * K in s:
            red = True

    # Check for Diagonal Right-Down and Left-Down
    for i in range(n):
        j = 0
        s = ''.join(board[i+d][j+d] for d in range(n-i))
        if 'B' * K in s:
            blue = True
        if 'R' * K in s:
            red = True
        s = ''.join(board[j+d][i+d] for d in range(n-i))
        if 'B' * K in s:
            blue = True
        if 'R' * K in s:
            red = True

        s = ''.join(board[j+d][i-d] for d in range(i+1))
        if 'B' * K in s:
            blue = True
        if 'R' * K in s:
            red = True
        s = ''.join(board[i+d][n-d-1] for d in range(n-i))
        if 'B' * K in s:
            blue = True
        if 'R' * K in s:
            red = True

    if blue and red:
        return 'Both'
    if blue:
        return 'Blue'
    if red:
        return 'Red'
    return 'Neither'

if __name__ == '__main__':
    t = int(input())
    for case in range(1, t+1):
        print("Case #{0}: {1}".format(case, solve()))