Solution for Double Square Problem in Facebook Hacker Cup 2011 Qualification Round

peg_game.py

import sys

def find_prob(row, col, x, exempt):
    size = (row,col) 
    arr = []
    broken = exempt
    for i in range(size[0]):
        k = []
        for j in range(size[1]*2-1):
            if(i%2==0): 
                if(j%2==0):
                    value = '^' if (i, j/2) not in broken else '.'
                    if value == '^' and j == 0:
                        value = '\\'
                    if value == '^' and j == size[1]*2-2:
                        value = '/'
                    k.append({'type':'peg', 'value':value})
                else:
                    k.append({'type':'pit', 'value':0.0})
            else: 
                if(j%2==0):
                    val = 0.0
                    if val == '.' and j == 0:
                        val = -1.0
                    if val == '.' and j == size[1]*2-2:
                        val = -1.0
                    k.append({'type':'pit', 'value':val})
                else:
                    value = '^' if (i, j/2) not in broken else '.'
                    if value == '^' and j == 1:
                        value = '\\'
                    if value == '^' and j == size[1]*2-3:
                        value = '/'
                    
                    k.append({'type':'peg', 'value':value})
        arr.append(k)
        
    ret = get_prob(arr,size , x)
    print str(ret[0])+ ' '+ret[1]

        
def get_prob(arr,size, x=0):
    X = x*2 + 1
    row = size[0] - 1
    arr[row][X]['value'] = 1.0
    row -= 1
    while row >= 0:
        for j in range(size[1]*2-1):
            #print row, j
            if arr[row][j]['type'] == 'pit' and arr[row][j]['value'] != -1:
                if arr[row+1][j]['value'] == '\\':
                    arr[row][j]['value'] = arr[row+1][j+1]['value']
                if arr[row+1][j]['value'] == '/':
                    arr[row][j]['value'] = arr[row+1][j-1]['value']
                if arr[row+1][j]['value'] == '^':
                    left = arr[row+1][j-1]['value'] if j-1 >= 0 else 0
                    right = arr[row+1][j+1]['value'] if j+1 <= size[1]*2-1 else 0
                    arr[row][j]['value'] = left/2 + right/2
                if arr[row+1][j]['value'] == '.':
                    arr[row][j]['value'] = arr[row+2][j]['value'] if row+3 <= size[0] else 0
            
        row -= 1

    l = [item['value'] for item in arr[0] if item['type'] == 'pit']
    return l.index(max(l)), trunc(max(l))


def trunc(f):
    return str(round(f,6)).ljust(8).replace(' ','0')
        

def main(filename):
    f = open(filename,'r')
    s = f.readlines()[1:];
    for case in s:
        case = case.split(' ')
        row = int(case[0])
        col = int(case[1])
        x = int(case[2])
        exempt = []
        j = 4
        for i in range(int(case[3])):
            k = j + 1
            exempt.append((int(case[j]), int(case[k])))
            j = j + 2
        find_prob(row, col, x, exempt)

if __name__ == '__main__':
    main(sys.argv[1])

មនុស្ស៚កំដរគេ

[email protected]