import random

GRID_SIZE = 10
SHIPS = {"Carrier": 5, "Battleship": 4, "Cruiser": 3, "Submarine": 3, "Destroyer": 2}


def is_valid_placement(board, row, col, size, horizontal):
    if horizontal:
        if col + size > GRID_SIZE:
            return False
        return all(board[row][c] == 0 for c in range(col, col + size))
    else:
        if row + size > GRID_SIZE:
            return False
        return all(board[r][col] == 0 for r in range(row, row + size))


def place_ships():
    board = [[0 for _ in range(GRID_SIZE)] for _ in range(GRID_SIZE)]
    ship_locations = {}

    for ship, size in SHIPS.items():
        while True:
            row = random.randint(0, GRID_SIZE - 1)
            col = random.randint(0, GRID_SIZE - 1)
            horizontal = random.choice([True, False])

            if is_valid_placement(board, row, col, size, horizontal):
                if horizontal:
                    for c in range(col, col + size):
                        board[row][c] = 1
                    ship_locations[ship] = [(row, c) for c in range(col, col + size)]
                else:
                    for r in range(row, row + size):
                        board[r][col] = 1
                    ship_locations[ship] = [(r, col) for r in range(row, row + size)]
                break

    return ship_locations, board


def verify_ship_placement(ship_locations, board):
    if set(ship_locations.keys()) != set(SHIPS.keys()):
        return False

    if sum(len(locations) for locations in ship_locations.values()) != sum(
        SHIPS.values()
    ):
        return False

    for ship, locations in ship_locations.items():
        for row, col in locations:
            if board[row][col] != 1:
                return False

    if sum(sum(row) for row in board) != sum(SHIPS.values()):
        return False

    return True


def update_probability_grid(grid, prob_grid, remaining_ships, last_hit_sunk):
    for row in range(GRID_SIZE):
        for col in range(GRID_SIZE):
            if grid[row][col] == 1:
                prob_grid[row][col] = 0
            else:
                prob_grid[row][col] = -1

    for ship, size in remaining_ships.items():
        for row in range(GRID_SIZE):
            for col in range(GRID_SIZE):
                if col + size <= GRID_SIZE:
                    if all(grid[row][c] in [0, 1] for c in range(col, col + size)):
                        for c in range(col, col + size):
                            if grid[row][c] == 1:
                                prob_grid[row][c] += 1
                if row + size <= GRID_SIZE:
                    if all(grid[r][col] in [0, 1] for r in range(row, row + size)):
                        for r in range(row, row + size):
                            if grid[r][col] == 1:
                                prob_grid[r][col] += 1

    if not last_hit_sunk:
        for row in range(GRID_SIZE):
            for col in range(GRID_SIZE):
                if grid[row][col] == 0:
                    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                        r, c = row + dr, col + dc
                        if (
                            0 <= r < GRID_SIZE
                            and 0 <= c < GRID_SIZE
                            and grid[r][c] == 1
                        ):
                            prob_grid[r][c] *= 6

    max_prob = max(max(row) for row in prob_grid)
    min_prob = min(min(row) for row in prob_grid if row != [-1])
    if max_prob > min_prob:
        for row in range(GRID_SIZE):
            for col in range(GRID_SIZE):
                if prob_grid[row][col] > 0:
                    prob_grid[row][col] = int(
                        ((prob_grid[row][col] - min_prob) / (max_prob - min_prob))
                        * 1000
                    )
                else:
                    prob_grid[row][col] = 0


def get_highest_probability_cell(prob_grid):
    max_prob = max(max(row) for row in prob_grid)
    if max_prob == 0:
        return None
    targets = [
        (row, col)
        for row in range(GRID_SIZE)
        for col in range(GRID_SIZE)
        if prob_grid[row][col] == max_prob
    ]
    return random.choice(targets)


def update_grid(grid, row, col, result):
    if result == "hit" or result == "sunk":
        grid[row][col] = 0
    elif result == "miss":
        grid[row][col] = -1


def simulate_game():
    ship_locations, true_board = place_ships()

    if not verify_ship_placement(ship_locations, true_board):
        return None

    turns = 0
    hits = set()
    grid = [[1 for _ in range(GRID_SIZE)] for _ in range(GRID_SIZE)]
    prob_grid = [[0 for _ in range(GRID_SIZE)] for _ in range(GRID_SIZE)]
    remaining_ships = SHIPS.copy()
    last_hit_sunk = False

    while remaining_ships:
        turns += 1
        update_probability_grid(grid, prob_grid, remaining_ships, last_hit_sunk)
        move = get_highest_probability_cell(prob_grid)
        if move is None:
            break
        row, col = move

        hit = False
        sunk = False
        sunk_ship_size = 0

        if true_board[row][col] == 1:
            hit = True
            hits.add((row, col))
            for ship, locations in ship_locations.items():
                if (row, col) in locations:
                    if all((r, c) in hits for r, c in locations):
                        sunk = True
                        sunk_ship_size = len(locations)
                        del remaining_ships[ship]
                    break

        if sunk:
            result = "sunk"
            last_hit_sunk = True
        elif hit:
            result = "hit"
            last_hit_sunk = False
        else:
            result = "miss"
            last_hit_sunk = False

        update_grid(grid, row, col, result)

    return turns


if __name__ == "__main__":
    result = simulate_game()
    if result is not None:
        print(result)
    else:
        print("Error: Invalid ship placement")
