'''
Mine Sweeper
Written by Kaz Yoshikawa
Date: Feb 12, 2018

MIT License

Copyright (c) 2018

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
'''

import random

def board_width():
    return 10

def board_height():
    return 10

def char_mine():
    return "*"

def char_flag():
    return "?"

def char_none_revealed():
    return "+"

def char_no_mine():
    return "."

def surrounding_vectors():
    return [[-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1]]

def is_debugging():
    return False

def display_mine_sweeper():
    print "  __  __ _               _____                                  "
    print " |  \/  (_)             / ____|                                 "
    print " | \  / |_ _ __   ___  | (_____      _____  ___ _ __   ___ _ __ "
    print " | |\/| | | '_ \ / _ \  \___ \ \ /\ / / _ \/ _ \ '_ \ / _ \ '__|"
    print " | |  | | | | | |  __/  ____) \ V  V /  __/  __/ |_) |  __/ |   "
    print " |_|  |_|_|_| |_|\___| |_____/ \_/\_/ \___|\___| .__/ \___|_|   "
    print "                                               | |              "

def display_gameover():
    print " __  _   ____  ____    ___    ___   ____  "
    print "|  |/ ] /    ||    \  /   \  /   \ |    \ "
    print "|  ' / |  o  ||  o  )|     ||     ||  _  |"
    print "|    \ |     ||     ||  O  ||  O  ||  |  |"
    print "|     ||  _  ||  O  ||     ||     ||  |  |"
    print "|  .  ||  |  ||     ||     ||     ||  |  |"
    print "|__|\_||__|__||_____| \___/  \___/ |__|__|"
    print "                                          "
    print "             G A M E   O V E R            "

def display_congratulations():
    print "    __   ___   ____    ____  ____    ____  ______  __ __  _       ____  ______  ____  ___   ____   _____"
    print "   /  ] /   \ |    \  /    ||    \  /    ||      ||  |  || |     /    ||      ||    |/   \ |    \ / ___/"
    print "  /  / |     ||  _  ||   __||  D  )|  o  ||      ||  |  || |    |  o  ||      | |  ||     ||  _  (   \_ "
    print " /  /  |  O  ||  |  ||  |  ||    / |     ||_|  |_||  |  || |___ |     ||_|  |_| |  ||  O  ||  |  |\__  |"
    print "/   \_ |     ||  |  ||  |_ ||    \ |  _  |  |  |  |  :  ||     ||  _  |  |  |   |  ||     ||  |  |/  \ |"
    print "\     ||     ||  |  ||     ||  .  \|  |  |  |  |  |     ||     ||  |  |  |  |   |  ||     ||  |  |\    |"
    print " \____| \___/ |__|__||___,_||__|\_||__|__|  |__|   \__,_||_____||__|__|  |__|  |____|\___/ |__|__| \___|"
    print "                                                                                                        "
    print " You sweeped the all bombs!!"


def display_welcome():
    display_mine_sweeper()
    print
    print "Instruction:"
    print
    print "The purpose of the game is to open all the cells of the board"
    print "which do not contain a bomb. You lose if you set off a bomb cell."
    print
    print "bluh, bluh bluh...."

def input_integer(message):
    while True:
        try:
            userInput = int(raw_input(message))
        except ValueError:
            print("Not an integer! Try again.")
            continue
        else:
            return userInput
        break


def display_board(board):
    assert(len(board) == board_height())
    debug = is_debugging()
    print
    cols = board_width()
    rows = board_height()
    header = "   "
    for ch in range(ord('a'), ord('a')+cols):
        header += (str(chr(ch)) + " ")
    if debug:
        header = header + "  " + header
    print header


    for row in range(rows):
        string = "%1d:|" % row
        for col in range(rows):
            cell = board[row][col]
            string += (board[row][col][1] + "|")
        if debug:
            string += "  %1d:|" % row
            for col in range(rows):
                cell = board[row][col]
                string += (board[row][col][0] + "|")
        print string


def count_mines_in_neighbor(board, row, col):
    width = board_width()
    height = board_height()
    count = 0
    if board[row][col][0] == char_mine():
        return -1 # mine
    for vector in surrounding_vectors():
        dy = vector[0]
        dx = vector[1]
        y = row + dy
        x = col + dx
        if dx != 0 or dy != 0:
            if y >= 0 and y < height and x >= 0 and x < width:
                if board[y][x][0] == char_mine():
                    count += 1
    return count

def cell_char(mine_count):
    if mine_count < 0:
        return "*"
    if mine_count >= 0 and mine_count <= 9:
        return chr(ord('0') + mine_count)
    assert(False)


def make_board(mines):
    # each cell requires two states, concealed state that player cannot see,
    # and in-play state that player can see.  In order to achieve this,
    # board[x][y] keeps two characters [0] for the concealed, [1] for in-play
    # [Concealed State]
    #    '0'-'8': cell that whose neighbor
    #    '*': mine
    # [In-Play State]
    #    '0'-'8': cell that whose neighbor
    #    '*': mine, '?": flagged, ".": no mine, '+': unknown
    # examples:
    #    "*?" - mine with flagged
    #    "*+" - hidden mine
    #    "2 " - unvealed but there are two mines in neighbor cells
    #    "11" - there is a mine in in neighbor cells, and disclosed

    # create the board
    board = []
    for row in range(board_height()):
        cells = []
        for col in range(board_width()):
            cells.append("0 ")
        board.append(cells)
    count = mines

    # set some mines
    while count > 0:
        x = random.randint(0, board_width() - 1)
        y = random.randint(0, board_height() - 1)
        if board[y][x][0] == "0":
            board[y][x] = char_mine() + char_none_revealed()
            count -= 1

    # set hints
    for row in range(board_height()):
        for col in range(board_width()):
            count = count_mines_in_neighbor(board, row, col)
            board[row][col] = cell_char(count) + char_none_revealed()
    return board

def input_position():
    position = [] # expect [row, col]
    row_chars = []
    col_chars = []
    for row in range(board_height()):
        row_chars += chr(ord('0') + row)
    for col in range(board_width()):
        col_chars += chr(ord('a') + col)
    prompt = "Please enter a position to open or to flag: "
    while True:
        string = raw_input(prompt).lower()
        if len(string) != 2 :
            print "Not a valid position, please try again"
            continue
        if string[0] in col_chars and string[1] in row_chars:
            col = ord(string[0]) - ord('a')
            row = ord(string[1]) - ord('0')
            position = [row, col]
            break
        # may not be necessary, but make it easy for player to input
        if string[0] in row_chars and string[1] in col_chars:
            col = ord(string[1]) - ord('a')
            row = ord(string[0]) - ord('0')
            position = [row, col]
            break
    return position

def reveal_position(board, row, col):

    # to avoid process the same call more than once, provide flags
    flags = []
    for y in range(board_height()):
        rowflags = []
        for x in range(board_width()):
            rowflags.append(False)
        flags.append(rowflags)

    # '0': enqueue the position to process, other digits: reveal it
    queue = []
    cell = board[row][col]
    if cell[0] == "0":
        queue.append([row, col])
    elif cell[0].isdigit():
        board[row][col] = board[row][col][0] + board[row][col][0]
    flags[row][col] = True

    width = board_width()
    height = board_height()
    count = 0

    # keep processing untill queue is empty
    while len(queue) > 0:
        count += 1
        row_col = queue.pop()
        row = row_col[0]
        col = row_col[1]
        cell = board[row][col]
        assert(cell[0] == "0")
        board[row][col] = cell[0] + char_no_mine()

        # look for neighboring cell for eight directions
        for vector in surrounding_vectors():
            y = row + vector[0]
            x = col + vector[1]
            # ignore if out of range or has been processed
            if x in range(width) and y in range(height) and not flags[y][x]:
                flags[y][x] = True # mark it off
                cell = board[y][x]
                if cell[0] == "0":
                    queue.append([y, x]) # enqueue
                elif cell[0].isdigit():
                    board[y][x] = cell[0] + board[y][x][0] # reveal the number


def count_mines(board):
    count = 0
    for row in range(board_height()):
        for col in range(board_width()):
            if board[row][col][0] == char_mine():
                count += 1
    return count

def count_flags(board):
    count = 0
    for row in range(board_height()):
        for col in range(board_width()):
            if board[row][col][1] == char_flag():
                count += 1
    return count

def toggle_flag(board, row, col):
    if board[row][col][1] == char_flag():
        board[row][col] = board[row][col][0] + char_none_revealed()
    else:
        board[row][col] = board[row][col][0] + char_flag()

def reveal_board(board):
    for row in range(board_height()):
        for col in range(board_width()):
            cell = board[row][col]
            if cell[0] == "0":
                board[row][col] = cell[0] + char_no_mine()
            else:
                board[row][col] = cell[0] + cell[0]

def main():
    display_welcome()
    number_of_mines = input_integer("Please input a number of mines in a map: ")
    board = make_board(number_of_mines)
    display_board(board)
    while True:

        # check if all mines are sweeped
        mines_left = count_mines(board) - count_flags(board)
        if mines_left == 0:
            display_congratulations()
            break

        # input a position of borad [row, col]
        print "Thre are ", mines_left, "mines left out of ", number_of_mines, "."
        pos = input_position()
        row = pos[0]
        col = pos[1]

        # when the cell is flagged, then ask to turn off
        if board[row][col][1] == char_flag():
            answer = raw_input("Would you like to turn the flag off?").lower()
            if answer == "y":
                toggle_flag(board, row, col)

        # when the cell is not yet unvealed, then aks either to open or to flag
        elif board[row][col][1] == char_none_revealed():
            answer = raw_input("Would you like to open(o) or flag(f): ").lower()
            if answer == "o": # open
                if board[row][col][0] == char_mine():
                    reveal_board(board)
                    display_board(board)
                    display_gameover()
                    break
                elif board[row][col][0].isdigit():
                    reveal_position(board, row, col)
            elif answer == "f": #flag
                toggle_flag(board, row, col)
        display_board(board)


main()