#!/usr/bin/python2
from minesweeper import *
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
# 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.


def do_print(s):
    pass

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_"],

]

SINGLE_MINE_PATTERNS = [
    ["K_ 1_",
     "1_ .*"],

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

    ["1_ ?_",
     "K_ .*",
     "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 SINGLE_MINE_PATTERNS:
    PATTERN_OFFSETS[id(pa)] = calculate_pattern_offsets(pa)




def print_grid(grid):
    for row in xrange(grid.nrows):
        s = ""
        for col in xrange(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 = reduced.ncols
    rows = reduced.nrows
    y = row
    res = set()

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

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

            elif matcher == '?':
                continue

            elif matcher == 'K':
                if in_bounds and reduced[y, x] == '.':
                    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, bounds = None):
    if bounds == None or bounds[0] == None:
        bounds  = (0, reduced.nrows-1, 0, reduced.ncols-1)
    pattern_height = len(pattern)
    patter_width = len(pattern[0])
    row_from, row_to, col_from, col_to = pattern_offset

    col_to = min(reduced.ncols, bounds[3]) + col_to
    row_to = min(reduced.nrows, bounds[1]) + row_to
    row_from += bounds[0]
    col_from += bounds[2]
    pairs = [p.split() for p in pattern]
    if pattern == PATTERNS[0]:
        do_print("Checking at %dR%d %dC%d" % (row_from, row_to, col_from, col_to))

    for row in xrange(row_from, row_to):
        for col in xrange(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, bounds):
        # 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, bounds)
            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, bounds)
            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, bounds)
            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, BOUNDS)
    if res:
        return res

    res = check_flips(pattern, offset, BOUNDS)
    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, BOUNDS)
    if res:
        return res

    res = check_flips(tpattern, toffset, BOUNDS)
    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 guess_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
            expand_bounds(reduced, row, col)

    expand_bounds(reduced, y, x)
    return True

def try_to_fill(grid, reduced):
    res = False
    for y in xrange(reduced.nrows):
        for x in xrange(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 = guess_mine_at(reduced, cy, cx) or res

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


    return res


TOTAL_MINES_LEFT = 0

STEP = 0

def guess_empty_at(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
    expand_bounds(reduced, row, col)

# row_start, row_end, col_start, col_end
BOUNDS=[None, None, None, None]

def reset_bounds():
    BOUNDS[0]=BOUNDS[1]=BOUNDS[2]=BOUNDS[3] = None

def expand_bounds(reduced, row, col):
    DELTA = 4
    if BOUNDS[0] == None:
        BOUNDS[0] = row - DELTA
        BOUNDS[1] = row + DELTA
        BOUNDS[2] = col - DELTA
        BOUNDS[3] = col + DELTA
    else:
        BOUNDS[0] = min(row - DELTA, BOUNDS[0])
        BOUNDS[1] = max(row + DELTA, BOUNDS[1])
        BOUNDS[2] = min(col - DELTA, BOUNDS[2])
        BOUNDS[3] = max(col + DELTA, BOUNDS[3])

global LAST_R

def exampleSolveGame(grid):
    global STEP
    global LAST_R
    global TOTAL_MINES_LEFT
    STEP += 1
    TOTAL_MINES_LEFT = grid.nMines()
    reduced = Array2D(grid.nRows(), grid.nCols(), ".")
    LAST_R = reduced

    reset_bounds()
    guess_empty_at(grid, reduced, 4, 4)


    several_mines_patterns = PATTERNS
    single_mine_patterns = PATTERNS + SINGLE_MINE_PATTERNS

    probabilities = Array2D(grid.nRows(), grid.nCols(), 0.0)

    while not grid.isSolved():
        old=True

        l = several_mines_patterns
        if TOTAL_MINES_LEFT == 1:
            l = single_mine_patterns

        for p in l:
            res = check_match(grid, reduced, p)
            if res:
                reset_bounds()
                do_print("Found pattern, cleared %d" % len(res))
                for row, col, is_empty in res:
                    if is_empty:
                        guess_empty_at(grid, reduced, row, col)
                    else:
                        guess_mine_at(reduced, row, col)
                    old = False
                break
        if not old:
            continue

        if BOUNDS[0] != None:
            do_print("Nothing found in %s, resetting" % BOUNDS)
            reset_bounds()
            continue

        do_print("Nothing found in whole field. Filling")
        res = try_to_fill(grid, reduced)

        if res:
            do_print("Filled: OK")
            continue

        do_print("Filled: nothing filled")

        #for y in xrange(0, reduced.nrows):
        #    for x in xrange(0, reduced.ncols):
        #        probabilities[y, x] = 0.0
        probabilities = Array2D(reduced.nrows, reduced.ncols, 0.0)

        for y in xrange(0, reduced.nrows):
            for x in xrange(0, reduced.ncols):
                r = reduced[y,x]
                if type(r) != int or r == 0:
                    continue

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

                probabilty = float(r) / float(unknowns)

                for cy, cx in iter_neigbours(reduced, y, x):
                    probabilities[cy, cx] = max(probabilities[cy, cx], probabilty)


        cy, cx, best_probability = 0, 0, 1.0
        for y in xrange(0, reduced.nrows):
            for x in xrange(0, reduced.ncols):
                if probabilities[y,x] != 0.0 and probabilities[y, x] < best_probability and reduced[y, x] == '.':
                    best_probability = probabilities[y, x]
                    cy, cx = y, x

        if best_probability < 1.0:
            do_print("Educational guess at %d %d with prob %.4f%%" % (cy, cx, 100.0 * best_probability))
            guess_empty_at(grid, reduced, cy, cx)
            continue




        while True:
            cy = random.randint(0, reduced.nrows-1)
            cx = random.randint(0, reduced.ncols-1)
            if reduced[cy,cx] == '.':
                do_print("Non-educational guess at %d %d" % (cy, cx))
                guess_empty_at(grid, reduced, cy, cx)
                break
    #print_grid(reduced)

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)
        return
        try:
            mf = Minefield(16, 30, 99)
            exampleSolveGame(mf)
            print(mf.isSolved())
        except LostGameError:
            print ("lost")
            pass
        print_grid(LAST_R)

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