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()))
2011-04-14

Project Euler problem 323 - Solved

Comments

You can find the statement of this problem here.

To solve this problem I used, as usual, dynamic programming as top-down approach with memoization.

The DP dictionary will be indexed by a tuple consisting of the number of tries left and the number of bits still in 0.

The base cases are:

  • remaining tries > 0 and bits in 0 = 0: Then I already have all bits in 1 so it doesn’t count, thus the probability is 0.
  • remaining tries = 0 and bits in 0 > 0: I have no or operations left to do, so I couldn’t complete it, thus the probability is 0.
  • remaining tries = 0 and bits in 0 = 0: I have all bits in 1 and finished with the or operations, so this is a good case, probability of 1.

If what we are dealing with is not one of the base cases and it’s not stored in the DP dictionary then we calculate the probability of finishing with all bits in 1 using exactly remaining tries or operations.  This will calculate the probabilities by using the probabilities stored in the DP.

In order to calculate the result we use the function that retrieves the probability of fulfilling all the bits in exactly i or operations to calculate the weight of that i in the total(this is done by multiplying i to that probaility), we add up the sum for i from 1 to 50, and we get the correct result.

The python code is problem323.py:

factorial = {0:1}
for i in range(1, 33):
    factorial[i] = factorial[i-1] * i

bits = 32

comb = lambda n, k: factorial[n] // (factorial[k] * factorial[n-k])

dp = {
    (0, 0) : 1
}

def get_value(*args):
    if args in dp:
        return dp[args]

    length, rem = args
    if length > 0 and rem == 0:
        return 0
    if length == 0 and rem > 0:
        return 0
    result = 0
    for i in range(bits+1):
        for overlooked in range(max(0, i-rem), min(i, bits-rem)+1):
            result += get_value(length-1, rem-i+overlooked) * ((comb(bits-rem, overlooked) * comb(rem, i-overlooked) / (2 ** bits)))

    dp[args] = result
    return result

iters = 50

if __name__ == '__main__':
    result = 0
    for i in range(1, iters+1):
        result += get_value(i, bits) * i
    print("The result is:", result)
2011-04-11

Project Euler problem 158 - Solved

Comments

You can find the statement of this problem here.

As in many of the posts you can find here, the solution for this problem is using DP.

I used a top-down approach with memoization. The dp dictionary will be indexed by three things: length, number of numbers which are greater than the previous and the number of times that the a[i] < a[i+1].

The base cases are:

  • (0, 0, 0) = 0: Meaning we finished choosing the strings but no a[i] < a[i+1] so its not valid.
  • (0, 0, 1) = 1: Meaning we finished choosing the strings and there’s only one occurrence where a[i] < a[i+1] so its valid and there’s only one possibility.
  • (,,2) = 0: Any case where there is more than one occurrence where a[i] > a[i+1] is not valid so 0 is returned.

In my python code I implemented a method get_num that receives the 3 indexes. It first checks if the result is in the dp dictionary, in that case returns the saved value; if the 3rd index is greater than 1 it returns 0. If none applies it calls recursively for each case that we could pick from, adds them all up and stores the value for not recalculating it.

It is important to notice that we don’t need to take the 26 possible characters to calculate the different number of ways of generating different strings of length x. We just calculate from the base that we have x characters and then multiply the result by the number of combinations we can take x from 26.

The Python code can be downloaded problem158.py:

factorial = {0:1}
for i in range(1, 27):
    factorial[i] = factorial[i-1] * i

dp = {
    (0, 0, 0) : 0,
    (0, 0, 1) : 1
}
def get_num(*args):
    if args in dp:
        return dp[args]

    length, num_greater, count = args
    if count > 1:
        return 0
    result = sum(get_num(length-1, i, count + ((i < num_greater) and 1 or 0)) for i in range(length))
    dp[args] = result
    return result

p = lambda n: sum(get_num(n-1, i, 0) for i in range(n)) * (factorial[26] // (factorial[n] * factorial[26 - n]))

if __name__ == '__main__':
    max_pn, max_n = max((p(n), n) for n in range(2, 27))
    print("The result is:", max_pn, "found at n:", max_n)

And the equivalent in Haskell problem158.hs:

import Data.Map
import Data.Maybe

factorial n = factorial' n 1
    where
        factorial' n res
            | n < 2 = res
            | n >= 2 = factorial' (n-1) (res * n)

comb x y = ((factorial x) `div` ((factorial y) * (factorial (x-y))))

getValue :: (Integer, Integer, Integer) -> Map (Integer, Integer, Integer) Integer -> (Integer, Map (Integer, Integer, Integer) Integer )
getValue (length, greater, count) dp
    | count > 1 = (0, dp)
    | member (length, greater, count) dp = (fromJust (Data.Map.lookup (length, greater, count) dp), dp)
    | notMember (length, greater, count) dp = getValue' (length, greater, count) dp 0 0
        where
            getValue' (length, greater, count) dp i res
                | i == length = (res, insert (length, greater, count) res dp)
                | i < length = getValue' (length, greater, count) nDp (i+1) (res + nRes)
                where
                    nCount = if i < greater then count+1 else count
                    (nRes, upDp) = getValue ((length -1), i, nCount) dp
                    nDp = insert ((length -1), i, nCount) nRes dp

p :: Integer -> Map (Integer, Integer, Integer) Integer -> (Integer, Map (Integer, Integer, Integer) Integer)
p n dp = p' 0 dp 0
    where
        p' x dp res 
            | x == n = (res * (comb 26 n), dp)         
            | x < n  = p' (x + 1) nDp (res + nRes)
            where
                (nRes, nDp) = getValue ((n-1), x, 0) dp

initialDp = fromList [((0,0,0), 0), ((0,0,1), 1)]

main = print ("The result is: " ++ (show (first (foldl f (0, initialDp) [1..26]))))
    where
        first (x, y) = x
        f (r, dp) n = 
            let
                (nRes, nDp) = p n dp
                maxR = max r nRes
            in
                (maxR, nDp)