#!/usr/bin/python2
from minesweeper import *
import itertools
import random


# Patterns syntax:
# Each pattern is an array of string
# Each string contains pairs <matcher, action> characters (e.g. ?o) separated by whitespace for readability
# match - is a matcher against which element on board will be matched. All elements in patterns must match for action to occur
# possible matchers are:
#   ? - match anything, including out of bonds cells
#   0..9 - match against reduced strength
#          Reduced strength is (written number in field) - (number of marked mines adjacent to the cell)
#          doesn't match out of bonds cells
#   K    - known cell, impossible for the new mine cell. Matches out-of-bounds, known 0-9, known mines, not unknowns
#   .    - matches unknown
#   A    - matches empty cell when TOTAL_MINES_LEFT = 1
# action is an action regarding this cell
# o - open it. Action is ignored if cell already marked as mine or open or out of bounds
# * - mark mine
# _ - ignore cell.



PATTERNS = [
    ["?o ?o ?o",
     "?o 0_ ?o",
     "?o ?o ?o"],

    [ "K_ K_ K_",
      "1_ 2_ K_",
      "?_ ?_ .*"],

    [ "K_ K_ K_ K_",
      "K_ 1_ 1_ K_",
      "?o ?_ ?_ K_"],

    ["K_ 1_ 1_ K_",
     "K_ ._ ._ K_",
     "K_ 1_ .o K_",
     "K_ K_ K_ K_"],

]

A_PATTERNS = [
    ["K_ 1_",
     "1_ A*"],

    ["1_ ?_",
     "K_ A*",
     "K_ 1_"],

    ["1_ ?_",
     "K_ A*",
     "1_ ?_"],
]


TRANSPOSED_PATTERNS = {}
HFLIPPED_PATTERNS = {}

def transpose_pattern(p):
    if id(p) in TRANSPOSED_PATTERNS:
        return TRANSPOSED_PATTERNS[id(p)]

    res = []
    splitted = [x.split() for x in p]
    z = zip(*splitted)
    z = [" ".join(x) for x in z]
    TRANSPOSED_PATTERNS[id(p)] = z
    return z

def hflip_pattern(p):
    if id(p) in HFLIPPED_PATTERNS:
        return HFLIPPED_PATTERNS[id(p)]

    res = []
    splitted = [reversed(x.split()) for x in p]
    z = [" ".join(x) for x in splitted]
    HFLIPPED_PATTERNS[id(p)] = z
    return z

def calculate_pattern_offsets(pattern):
    """ Calculate pattern offset. Since ? matcher can match against empty cell, we need to know how far out of bonds we can go
:return: (row_from, row_to, col_from, col_to)
"""
    row_from = 0
    row_to   = 0
    col_from = 0
    col_to   = 0

    pattern_height = len(pattern)
    patter_width = len(pattern[0])

    def impl(p):
        xfrom = xto = 0
        # First try to find how far we can move pattern out of top bounds
        for row in p:
            if any(map(lambda p:p[0] not in '?K', row.split())):
                break
            xfrom -= 1

        # Now bottom
        for row in reversed(p):
            if any(map(lambda p:p[0] not in '?K', row.split())):
                break
            xto += 1
        return xfrom, xto

    row_from, row_to = impl(pattern)
    col_from, col_to = impl(transpose_pattern(pattern))

    return (row_from, row_to, col_from, col_to)

PATTERN_OFFSETS = { id(p) : calculate_pattern_offsets(p) for p in PATTERNS }
for pa in A_PATTERNS:
    PATTERN_OFFSETS[id(pa)] = calculate_pattern_offsets(pa)




def print_grid(grid):
    for row in range(grid.nrows):
        s = ""
        for col in range(grid.ncols):
            s += "%2s " % grid[row,col]
        print(s)

    print("Mines left: %d" % TOTAL_MINES_LEFT)



def check_match_at(grid, reduced, pattern, row, col):
    cols = grid.nCols()
    rows = grid.nRows()
    y = row
    res = set()

    for prow in pattern:
        x = col - 1
        for pair in prow:
            x += 1
            matcher = pair[0]
            action = pair[1]
            in_bounds = 0 <= y < rows and 0 <= x < cols
            if in_bounds and reduced[y,x] == '.' and action != '_':
                res.add((y,x, action == 'o'))

            if matcher == 'A':
                if TOTAL_MINES_LEFT != 1:
                    return None
                if not in_bounds or reduced[y, x] != '.':
                    return None
                continue

            if matcher == '.':
                if not in_bounds or reduced[y, x] != '.':
                    return None
                continue

            if matcher == '?':
                continue

            if matcher == 'K':
                if in_bounds and reduced[y, x] in ['.']:
                    return None
                continue

            if not in_bounds:
                return None

            if int(matcher) != reduced[y,x]:
                return None
        y += 1
    return res



def do_check_match(grid, reduced, pattern, pattern_offset):
    pattern_height = len(pattern)
    patter_width = len(pattern[0])
    row_from, row_to, col_from, col_to = pattern_offset
    col_to = grid.nCols() - col_to
    row_to = grid.nRows() - row_to
    pairs = [p.split() for p in pattern]
    for row in range(row_from, row_to):
        for col in range(col_from, col_to):
            res = check_match_at(grid, reduced, pairs, row, col)
            if res:
                return res
    return None

def set_add(the_set, elt):
    if elt in the_set:
        return False
    the_set.add(elt)
    return True

def check_match(grid, reduced, pattern):
    processed = set()

    def check_flips(p, ofs):
        # Vertically flipped pattern
        # E R N _
        # P A T T
        vpattern = list(reversed(p))
        voffset = (-ofs[1], -ofs[0], ofs[2], ofs[3])
        if set_add(processed, "_".join(vpattern)):
            res = do_check_match(grid, reduced, vpattern, voffset)
            if res:
                return res

        # Horizontally flipped pattern
        # T T A P
        # _ N R E
        hoffset = (ofs[0], ofs[1], -ofs[3], -ofs[2])
        hpattern = hflip_pattern(p)
        if set_add(processed, "_".join(hpattern)):
            res = do_check_match(grid, reduced, hpattern, hoffset)
            if res:
                return res

        # Flipped both way
        # _ N R E
        # T T A P
        vhoffset = (-ofs[1], -ofs[0], -ofs[3], -ofs[2])
        vhpattern = hflip_pattern(vpattern)
        if set_add(processed, "_".join(vhpattern)):
            res = do_check_match(grid, reduced, vhpattern, vhoffset)
            return res
        return None

    # normal pattern
    # P A T T
    # E R N _
    offset = PATTERN_OFFSETS[id(pattern)]
    res = do_check_match(grid, reduced, pattern, offset)
    if res:
        return res

    res = check_flips(pattern, offset)
    if res:
        return res



    # transposes pattern
    # P E
    # A R
    # T N
    # T _

    tpattern = transpose_pattern(pattern)

    toffset = (offset[2], offset[3], offset[0], offset[1])
    res = do_check_match(grid, reduced, tpattern, toffset)
    if res:
        return res

    res = check_flips(tpattern, toffset)
    return res

def iter_neigbours(arr2d, row, col):
    for dx in (-1,0,1):
        for dy in (-1,0,1):
            if dx == dy == 0:
                continue
            cx, cy = col + dx, row + dy
            if 0 <= cx < arr2d.ncols and 0 <= cy < arr2d.nrows:
                yield cy, cx

def mark_mine_at(reduced, y, x):
    global TOTAL_MINES_LEFT

    if reduced[y, x] == '*':
        return False

    reduced[y, x] = '*'
    TOTAL_MINES_LEFT -= 1
    for row, col in iter_neigbours(reduced, y, x):
        r = reduced[row, col]
        if type(r) == int and r > 0:
            r -= 1
            reduced[row, col] = r
    return True

def try_to_fill(grid, reduced):
    res = False
    for y in range(reduced.nrows):
        for x in range(reduced.ncols):
            if not type(reduced[y,x]) == int:
                continue
            if reduced[y,x] == 0:
                continue


            total_neighbours = 0
            unknowns = 0

            for cy, cx in iter_neigbours(reduced, y, x):
                total_neighbours += 1
                if reduced[cy,cx] == ".":
                    unknowns += 1

            if reduced[y,x] == unknowns:
                for cy, cx in iter_neigbours(reduced, y, x):
                    if reduced[cy,cx] == ".":
                        res = mark_mine_at(reduced, cy, cx) or res

    if TOTAL_MINES_LEFT == 0:
        res = set([])
        for y in range(reduced.nrows):
            for x in range(reduced.ncols):
                if reduced[y,x] == '.':
                    do_guess(grid, reduced, y, x)
                    res.add((y, x, True))


    return res


TOTAL_MINES_LEFT = 0

STEP = 0

def do_guess(grid, reduced, row, col):
    grid.guess(row, col)
    m = grid.nMinesAround(row, col)
    for cy, cx in iter_neigbours(reduced, row, col):
        if reduced[cy, cx] == '*':
            m -= 1
    reduced[row,col] = m

def exampleSolveGame(grid):
    global STEP
    global TOTAL_MINES_LEFT
    STEP += 1
    TOTAL_MINES_LEFT = grid.nMines()
    reduced = Array2D(grid.nRows(), grid.nCols(), ".");
    do_guess(grid, reduced, 4, 4)
    while not grid.isSolved():
        old=True

        l = PATTERNS
        if TOTAL_MINES_LEFT == 1:
            l += A_PATTERNS

        for p in l:
            res = check_match(grid, reduced, p)
            if res:
                for row, col, is_empty in res:
                    if is_empty:
                        do_guess(grid, reduced, row, col)
                    else:
                        mark_mine_at(reduced, row, col)
                    old = False
                break
        if not old:
            continue

        res = try_to_fill(grid, reduced)

        if res:
            continue

        while True:
            cy = random.randint(0, reduced.nrows-1)
            cx = random.randint(0, reduced.ncols-1)
            if reduced[cy,cx] == '.':
                do_guess(grid, reduced, cy, cx)
                break


def main():
    # Set this to True if you want to play a game of Minesweeper with a
    # crappy text interface.  Set this to False if you want to test
    # how good the example AI is (spoiler: not very).
    doYouWantToPlayAGame = False

    if doYouWantToPlayAGame:
        playGame(9, 9, 10)
    else:
        testSolver(exampleSolveGame)

if __name__ == "__main__":
    random.seed(12475)
    main()