#v1.2

OBSTACLE = "+"
EMPTY = "."
MINE = "M"
BEACON = "B"

raw_board="""\
++++++++++++++++++++
+++++++..+++++++++++
+++++++...++++.+++++
++++++.+..+++.....++
++++++.....+......++
+++++++..++.......++
++....+..+++.+.+..++
++........+........+
++........+.++.+++++
++..........++.+++++
++..........++.+++++
+++++..+..........++
++++++++++++...++.++
++++++++++++......++
+.++++...+++......++
+..+++...+++++++++++
++++++...+++++++++++
++++++++++++++++++++"""

#all functions assume that: a board's outermost rows/columns are entirely obstacles

def copy(board):
    #could just use deepcopy, but meh
    return [row[:] for row in board]

def iter_neighbors(board, x,y):
    """yield the tile type of every adjacent tile"""

    #todo: make this work for border tiles
    assert 0 < y < len(board) - 1
    assert 0 < x < len(board[0]) - 1

    for dx in (-1,0,1):
        for dy in (-1, 0, 1):
            if dx == dy == 0: continue
            yield board[dy+y][dx+x]

def calculate_score(board):
    """Returns the total score of the board."""
    def _score(x,y):
        """the score of this one tile."""
        if board[y][x] == MINE:
            return 100 + sum(40 for tile in iter_neighbors(board, x, y) if tile == BEACON)
        else:
            return 0
    return sum(_score(x,y) for y, row in enumerate(board) for x, _ in enumerate(row))

def display(board):
    """print the board."""
    print("\n".join("".join(row) for row in board))


#example optimizers. Each one may mutate board in-place in an attempt to improve its score.
def literally_nothing(board):
    pass

def fill_empty_with_mines(board):
    for y, row in enumerate(board):
        for x, tile in enumerate(row):
            if board[y][x] == EMPTY:
                board[y][x] = MINE

def optimize_with_hill_climb(board):
    """Make only simple strict improvements. Very likely to get stuck in local optima."""

    #pass 1: fill up empty tiles
    fill_empty_with_mines(board)

    #pass 2: replace a mine with a beacon iff doing so increases score
    cur_score = calculate_score(board)
    for y, row in enumerate(board):
        for x, tile in enumerate(row):
            if board[y][x] == MINE:
                board[y][x] = BEACON
                new_score = calculate_score(board)
                if new_score > cur_score:
                    #keep change
                    cur_score = new_score
                else:
                    #revert
                    board[y][x] = MINE

def sample_showcase():
    """showcase the performance of the sample optimizers."""
    starting_board = [list(row) for row in raw_board.strip().split("\n")]
    optimizers = [literally_nothing, fill_empty_with_mines, optimize_with_hill_climb]
    print("Starting board:")
    display(starting_board)
    print("\n")

    for i, optimize_func in enumerate(optimizers, 1):
        board = copy(starting_board)
        print(f"Candidate #{i}: {optimize_func.__name__}")
        optimize_func(board)
        display(board)
        print("Score:", calculate_score(board))
        print(f"End of report for candidate #{i}.\n\n")

if __name__ == "__main__":
    sample_showcase()