2011-07-05

CodeJam 2009 - Qualification Round - (B)Watersheds - Solution

Comments

Today, I’m posting the solution for problem B in 2009’s Qualification Round which was called “Watersheds”.

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

The solution is straightforward, without any tricks. For each cell in the map I throw a recursive function which checks whether that cell is already in a basin or it calls recursively with the cell where the water goes to. In case that the water can’t go any further then a new basin is set at that cell and returned so that  the rest of the recursive calls set theirs to that basin.

The python file is GCJ2009-Q-B.py and it contains the following:

last_letter = 'a'
W = 0
H = 0

def run_water(height_map, basin_map, i, j):
    global last_letter, H, W
    if basin_map[i][j]:
        return basin_map[i][j]
    min_h = height_map[i][j]
    direction = 0
    if i > 0 and height_map[i-1][j] < min_h:
        direction = 1
        min_h = height_map[i-1][j]
    if j > 0 and height_map[i][j-1] < min_h:
        direction = 2
        min_h = height_map[i][j-1]
    if j < W-1 and height_map[i][j+1] < min_h:
        direction = 3
        min_h = height_map[i][j+1]
    if i < H-1 and height_map[i+1][j] < min_h:
        direction = 4
        min_h = height_map[i+1][j]
    if direction == 0:
        basin_map[i][j] = last_letter
        last_letter = chr(ord(last_letter) + 1)
    elif direction == 1:
        basin_map[i][j] = run_water(height_map, basin_map, i-1, j)
    elif direction == 2:
        basin_map[i][j] = run_water(height_map, basin_map, i, j-1)
    elif direction == 3:
        basin_map[i][j] = run_water(height_map, basin_map, i, j+1)
    elif direction == 4:
        basin_map[i][j] = run_water(height_map, basin_map, i+1, j)
    return basin_map[i][j]

def solve():
    global last_letter, H, W
    H, W = map(int, input().split(' '))
    height_map = []
    for i in range(H):
        height_map.append(list(map(int, input().split(' '))))
    basin_map = [[''] * W for i in range(H)]
    last_letter = 'a'
    for i in range(H):
        for j in range(W):
            run_water(height_map, basin_map, i, j)
    for i in range(H):
        print(' '.join(basin_map[i]))

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

CodeJam 2009 - Qualification Round - (A)Alien Language - Solution

Comments

I now present the solution from problem A in 2009 Qualification Round which was called “Alien Language”.

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

The solution is not complex but it has a tricky thing.

The first thing to do is to populate a set of words which will be the dictionary containing the D words of the Alien Language.

Then the tricky part comes, how to process the sequence of characters that might conform a word. There are basically two choices:

  • Try each possible combination and see which of those match a valid word.
  • For each valid word see if the characters received can conform it.

Both of the choices lead to a right answer but time plays a crucial part in the competence and if you choose the wrong one the program will never end, not at least in a reasonable amount of time.

Let’s analyze the solutions:

  • If we try each possible combination based on the characters received it can lead to process 27^15 combinations for the large set which is 2954312706550833698643. Forget about processing that in 8 minutes. And that’s only for one test case! If the number of cases is the highest your program may end up trying to process 27^15 * 500 which is even more!
  • If we try to match each valid word to the characters received we will have to try 5000 words per each case. That gives as a 500 * 5000 = 2500000 combinations to process which is definitively not much.

So once decided the approach to take, how to implement it? What I did is to process each sequence of characters received and generate a list consisting of L sets, each containing the possible characters in that position. After parsing the case it was a piece of cake, for each word I determined the character at each position was in the set of characters at that position in the sequence, if for all characters that happened then the word was possible.

The python file is GCJ2009-Q-A.py and it contains the following:

words = set()

if __name__ == '__main__':
    L, D, N = map(int, input().split())
    for i in range(D):
        words.add(input())
    for i in range(1, N+1):
        characters = input()
        characters_set = []
        s = set()
        flag = True
        for c in characters:
            if c == '(':
                flag = False
            elif c == ')':
                flag = True
            else:
                s.add(c)
            if flag:
                characters_set.append(s)
                s = set()
        result = 0
        for word in words:
            t = True
            for k in range(L):
                if word[k] not in characters_set[k]:
                    t = False
                    break
            if t:
                result += 1
        print("Case #{0}: {1}".format(i, result))
2011-05-16

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

Comments

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

I now present 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()))