Python solution for Problem C. Minesweeper Master - Google Code Jam 2014

minesweeper_master.py

# Google Code Jam 2014
# Problem C. Minesweeper Master
#     https://code.google.com/codejam/contest/2974486/dashboard#s=p2
# Author: jamie.xu - https://github.com/eytoss
PROBLEM_ID = "C" # A B or C
PROBLEM_SIZE = "large"

# `impossible` look up tables, used as short cut
# G4[9] == 1 means 9 mines for a 4 by 4 grid is impossible
# actually in my algorithm, it might just check G3[2] depending where I put this short-cut
# which gives the same answer, of course :)
# Note: index is 1-based for readability
I = []
I.append([])
I.append([None, 1])
I.append([None, 1, 1, 1, 1])
I.append([None, 0, 1, 0, 1, 0, 1, 1, 1, 1])
I.append([None, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1])
I.append([None, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1])
IS_MINE = "*"
NOT_MINE = "."

def run():
    """I/O handler"""
    file_name = "{}-{}".format(PROBLEM_ID, PROBLEM_SIZE)
    in_f = open('{}.txt'.format(file_name), 'r')
    out_f = open('{}.out'.format(file_name), 'w')
    num_of_case = int(in_f.readline().rstrip('\n'))
    #print "num of cases:{}".format(num_of_case)
    for i in range(1, num_of_case+1):
        solve_case(in_f, out_f, i)

def solve_case(in_f, out_f, case_index):
    """problem solver"""
    R, C, M = [int(x) for x in in_f.readline().rstrip('\n').split()]
    global G # grid info of mine position
    G = [[{"is_mine":NOT_MINE} for x in range(C)] for y in range(R)]
    find_solution = solve(R, C, M)
    out_f.write("Case #{}:\n".format(case_index))
    if find_solution:
        print_solution(out_f)
    else:
        out_f.write("Impossible\n")

def solve(R, C, M):
    """
    Recursive function for this problem, basically we are trying to put mines
    in a way that give us the minimum length of the `scars`(the tiles adj. to mine) 
    Basic strategies:
    1. try to fill the bottom row and right column with mines, to reduce the problem size
        also that way the G could be reused with natural indexes
    2. try to reduce the problem from R C M(where R != C) to problem R R M
    """
    if not M:
        return True # what else can you expect!
    # handle special cases here
    if R * C - M == 1:
        mark_all_mines()
        return True
    if 2 in (R, C) and M % 2 == 1:
        return False
    # not a square, trying to reduce it towards a square!
    if R > C:
        if M >= C:
            mark_button_row(R, C, C)
            return solve(R-1, C, M-C)
        mark_bottom_two_rows(R, C, M)
        return True
    elif C > R:
        if M >= R:
            mark_right_column(C)
            return solve(R, C-1, M-R)
        mark_right_two_columns(R, C, M)
        return True
    # we have perfect solution for square!
    if M >= 2*R-1:
        mark_button_and_right_mines(R)
        return solve(R-1, C-1, M+1-2*R) # reduced problem to a smaller square

    # short cut for Impossible.
    if R <= 5 and I[R][M]: 
        return False

    # guaranteed a solution here!
    if M == R-1: 
        mark_bottom_two_rows(R, C, M)
        return True
    else:
        if M <= C:
            mark_button_row(R, C, M)
        else:
            mark_button_row(R, C, C)
            mark_button_row(R-1, C, M-C)
        return True

def mark_right_two_columns(R, C, M):
    """mark mines in two right most columns, one for R-2, another for M+2-R"""
    global G
    if M <= R-2:
        for x in range(0, M): # right most column
            G[R-x-1][C-1]["is_mine"] = IS_MINE
    else:
        for x in range(0, R-2): # right most column
            G[R-x-1][C-1]["is_mine"] = IS_MINE
        for x in range(0, M+2-R): # next buttom row
            #print "222"
            G[R-x-1][C-2]["is_mine"] = IS_MINE
    inspect()

def print_solution(out_f, type="is_mine", message=None):
    """always chose top left tile as C"""
    global G
    G[0][0][type] = "c"
    for row in G:
        line = "".join([tile[type] for tile in row])
        out_f.write("{}\n".format(line))

### start of mark functions which support marking mine position on the grid
### TODO: consolidate these!
def mark_bottom_two_rows(R, C, M):
    """
    mark them in two bottom lines, one for C-2, second for M+2-C
    """
    global G
    if M <= C-2:
        for x in range(0, M): # buttom row
            G[R-1][C-x-1]["is_mine"] = IS_MINE
    else:
        for x in range(0, C-2): # buttom row
            G[R-1][C-x-1]["is_mine"] = IS_MINE
        for x in range(0, M+2-C): # next buttom row
            G[R-2][C-x-1]["is_mine"] = IS_MINE
    inspect()
            
def mark_button_row(R, C, M):
    """
    Reduce the problem size by marking mines on the button row
    R is the grid row for current iteration
    """
    global G
    for x in range(0, M): # buttom row
        G[R-1][C-x-1]["is_mine"] = IS_MINE
    inspect()

def mark_right_column(C):
    """
    Reduce the problem size by marking mines on right column
    C is the grid column for current iteration
    """
    global G
    for tile in [row[C-1] for row in G]:
        tile["is_mine"] = IS_MINE
    inspect()

def mark_button_and_right_mines(R):
    """
    Reduce the problem size by marking mines on the button row & right column
    R is the grid size for current iteration
    """
    global G
    for tile in G[R-1]: # button row
        tile["is_mine"] = IS_MINE
    for tile in [row[R-1] for row in G]: # right column
        tile["is_mine"] = IS_MINE
    inspect()

def mark_all_mines():
    """used to support 3 4 11 -- only one which is not mine could mark as c!"""
    global G
    for row in G:
        for tile in row:
            tile["is_mine"] = IS_MINE
### end of mark functions section
def inspect(type="is_mine", message=None):
    """test function"""
    return
    global G
    for row in G:
        print[tile[type] for tile in row]

run()

This one was tricky and took me a few hours and three wrong tries to get it solved :)

Wrong try bugs:

1. in if M >= 2*R-1: instead of using >=, I used >.
2. failed to consider the situation where only one non-mine tile on the grid: R*C=M+1
3. a hidden syntax error caused the mark_all_mines() didn't work. I should have tested before submit, I was just too eager to solve it!