main.py

from typing import Optional, Tuple, List

import random
import sys


class UnionFind:
    """
    Initialises a UnionFind collection with `size` items.
    """

    def __init__(self, size: int) -> None:
        self.values = [-1] * size

    def find(self, node: int) -> int:
        """
        Finds the representative for the set containing node.
        """

        if self.values[node] < 0:
            return node

        self.values[node] = self.find(self.values[node])
        return self.values[node]

    def unite(self, x: int, y: int) -> Optional[Tuple[int, int]]:
        """
        Unites the sets containing x and y. Returns `None` if the elements are
        already in the same set, otherwise `(new_rep, old_rep)` where `new_rep`
        is the new tree root and `old_rep` is the root of the tree which has
        been subsumed.
        """

        x_rep = self.find(x)
        y_rep = self.find(y)

        if x_rep == y_rep:
            return None
        else:
            if -self.values[x_rep] < -self.values[y_rep]:
                x_rep, y_rep = y_rep, x_rep

            self.values[x_rep] += self.values[y_rep]
            self.values[y_rep] = x_rep

            return (x_rep, y_rep)

    def cardinality(self, node: int) -> int:
        """
        Returns the cardinality of the set containing `node`.
        """

        return -self.values[self.find(node)]


icons = [
    ":bomb:",
    ":white_large_square:",
    ":one:",
    ":two:",
    ":three:",
    ":four:",
    ":five:",
    ":six:",
    ":seven:",
    ":eight:",
]


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


def generate_board_message(width, height, bombs):
    def index(x, y):
        return x + y*width

    def neighbours(x, y):
        return (
            (i, j)
            for i in range(x - 1, x + 2)
            for j in range(y - 1, y + 2)
            if 0 <= i < width and 0 <= j < height
            and (i, j) != (x, y)
        )

    # Generate board
    board: List[List[int]] = [[0]*width for _ in range(height)]

    all_indices = [(i, j) for i in range(width) for j in range(height)]
    for x, y in random.sample(all_indices, bombs):
        board[y][x] = -1
        for i, j in neighbours(x, y):
            if board[j][i] >= 0:
                board[j][i] += 1

    # Find largest region
    dsu = UnionFind(width*height)

    largest_region_size = 0
    largest_region = 0

    for y in range(height):
        for x in range(width):
            if board[y][x] == 0:
                here = index(x, y)
                for i, j in neighbours(x, y):
                    if board[j][i] == 0:
                        there = index(i, j)
                        dsu.unite(here, there)

                        this_region_size = dsu.cardinality(here)
                        if this_region_size > largest_region_size:
                            largest_region = here
                            largest_region_size = this_region_size

    # Normalise largest_region
    largest_region = dsu.find(largest_region)

    if largest_region_size == 0:
        largest_region = -1

    eprint(f"Largest region has size {largest_region_size}")
    eprint()

    def is_uncovered(x, y):
        return dsu.find(index(x, y)) == largest_region or any(
            dsu.find(index(i, j)) == largest_region
            for (i, j) in neighbours(x, y)
        )

    # Print board
    lines = []
    for y in range(height):
        line = ""
        for x in range(width):
            here = index(x, y)
            icon = icons[board[y][x] + 1]
            if is_uncovered(x, y):
                line += icon
            else:
                line += f"||{icon}||"
        line += "\n"
        lines.append(line)

    acc = ""
    for y in range(height):
        if len(acc) + len(lines[y]) > 2000:
            print(acc)
            print()
            acc = ""
        acc += lines[y]
    if acc != "":
        print(acc)


if __name__ == "__main__":
    if len(sys.argv) < 2:
        width = 10
        height = 10
        bombs = 15
    elif len(sys.argv) == 2:
        width = int(sys.argv[1])
        height = width
        bombs = width * 3/2
    elif len(sys.argv) == 3:
        width = int(sys.argv[1])
        height = width
        bombs = int(sys.argv[2])
    elif len(sys.argv) == 4:
        width = int(sys.argv[1])
        height = int(sys.argv[2])
        bombs = int(sys.argv[3])
    else:
        print("Usage: python3 ./main.py [width [[height] bombs]")
        exit()

    generate_board_message(width, height, bombs)