Initial solution for https://web.archive.org/save/https://techdevguide.withgoogle.com/resources/coding-question-minesweeper

minefield.py

#!/usr/bin/env python3
# DATE: 2020.08.08
# Initial attempt at solving https://web.archive.org/save/https://techdevguide.withgoogle.com/resources/coding-question-minesweeper
# NOTE: Untested
"""
# Initial impressions
*Task:*
- Construct the playing field given the size [of the field] and a number of mines.

*Questions:*
- Do I randomly place the mines whilst constructing the grid or are they expected to be at fixed coordinates?
- Why did the question tell me about hidden nodes?  Am I supposed to write something to solve minesweeper puzzles?
- What should happen on a resize?
    - Do we need to verify that the new size can contain all the mines?
    - If the new size is smaller (in any given dimension), do we regenerate the full grid or do we move some mines?
    - If the new size is bigger (in all directions), can we keep all the mines in the same place?
- Do we need to optimize storage for spares matrices (i.e., not a lot of mines or not a lot of non-mines)?

*Assumptions:*
    - Cols length and row length are not necessarily equal.
    - Cols length and row length are positive integers.
    - Number of mines do not exceed matrix size.
    - Number of mines is non-negative.

*Approach:*
- Flatten the matrix into a single array. O(n*m) storage.
    - If rows, cols are the the number of rows and the number of columns, then (x, y) is found using [x * cols + y * rows]
    - Upper-Left is (0, 0). Lower-right is (cols, rows)
    - Edges at:
        - top (x, 0)
        - left (0, y)
        - right (cols, y)
        - bottom (x, rows)
    - adjacents of (x, y) excluding edges
        - (x-1, y-1), (x+0, y-1), (x+1, y-1)
        - (x-1, y+0), (x+0, y+0), (x+1, y+0)
        - (x-1, y+1), (x+0, y-1), (x+1, y+1)
- Initial grid generation algorithm. O(2*n*m)
    - PRNG to generate (x, y).  Store into a set until we have required number of mines in the set.
    - One pass to place non-mines.  Each non-mine checks 8-adjacents (except at edges)
- Resize
    - Re-generate entire grid (for simplicity).  Could get fancy by looking at affected area and moving mines... but code complexity.
"""
import array
from enum import Enum
from random import randint
from typing import Any
class Matrix:
    def __init__(self, rows: int, cols: int, intval: int = 0) -> None:
        # NOTE: Did not know how to reserve memory for a list.  Lets just make a Zero matrix
        # NOTE: My initial thought was to use a list of lists, but it seems like array.array() might be better.  I didn't know about the array class.
        #  https://docs.python.org/3.6/library/array.html
        self.rows, self.cols = rows, cols
        self.grid = array.array("b", [initval] * self.cols * self.rows)

    def resize(self, rows: int, cols: int) -> bool:
        if self.rows == rows and self.cols == cols:
            return False
        self.rows, self.cols = rows, cols
        self.grid = array.array("b", [0] * self.cols * self.rows)
        return True

    def at(self, x: int, y: int) -> Any:
        return self.grid(x * self.cols + y * self.rows)

    def put(self, x: int, y:int, val: int) -> None:
        self.grid[x * self.cols + y * self.rows] = val

class GridNotation(Enum):
    GRID_HIDE = -1
    GRID_ADJ0 = 0
    GRID_ADJ1 = 1
    GRID_ADJ2 = 2
    GRID_ADJ3 = 3
    GRID_ADJ4 = 4
    GRID_ADJ5 = 5
    GRID_ADJ6 = 6
    GRID_ADJ7 = 7
    GRID_ADJ8 = 8
    GRID_MINE = 9

class Minefield(Matrix):    
    def __init__(rows: int, cols: int, mines: int) -> None:
        super(Matrix, self).__init__(rows, cols)
        self.num_mines = mines
        self._generate_minefield()
        # NOTE: Could have been fancy and used a bit in our minefield matrix to indicate revealed state
        self.player = Matrix(rows, cols, GridNotation.GRID_HIDE)

    def resize(rows: int, cols: int) -> bool:
        if super().resize(rows, cols):
            self._generate_minefield()
            self.player = Matrix(rows, cols, GridNotation.GRID_HIDE)
            return True
        return False
    
    def click(x: int, y: int) -> None:
        # EDIT: Added this after peeking and noticing that Google's referenced solution at
        #  https://gist.github.com/dgossow/d28083522608771e1c65f49822820ba9 had a player mode.

        # Recursion base case
        if x < 0 or x > self.col:
            return
        if y < 0 or y > self.row:
            return
        # Check if already processed
        if self.player.at(x, y) != GridNotation.GRID_HIDE:
            return

        point_data = self.at(x, y)
        self.player.put(x, y, point_data)
        
        if point_data == GridNotation.GRID_MINE:
            print("You touched a mine!")
            sys.exit(0)

        if point_data == GridNotation.GRID_ADJ0:
            # NOTE:  There's probably a fancier way to iterate through these permutations (maybe with itertools?)
            click(x - 1, y - 1)
            click(x    , y - 1)
            click(x + 1, y - 1)

            click(x - 1, y)
            click(x + 1, y)
            
            click(x - 1, y + 1)
            click(x    , y + 1)
            click(x + 1, y + 1)
            
        if self.player.count(GrindNotation.GRID_HIDE) == self.num_mines:
            print("Winner!")
            sys.exit(0)

    def _generate_minefield(self):
        # Generate mine (x, y) coordinates
        mine_coords = set()
        while len(mine_coords) < self.num_mines:
            mine_coords.add(randint(0, self.cols * self.rows))
        for coord in mine_coords:
            self.grid[coord] = GridNotation.GRID_MINE

        # Update mine adjacent blocks.  Adds 1 to each adjacent block.
        # Had considered the alternative of updating adjacents all in one go, but that seemed like more work
        #   because I would need to find the adjacents of the mine's adjacents.
        for coord in mine_coords:
            # Only incur lookup cost once per coord
            isTopEdge = self._isTopEdge(coord)
            isLeftEdge = self._isLeftEdge(coord)
            isRightEdge = self._isRightEdge(coord)
            isBottomEdge = self._isBottomEdge(coord)

            if not isTopEdge:
                upper_mid = coord - self.col
                self._update_adjacency(upper_mid)
                if not isLeftEdge:
                    self._update_adjacency(upper_mid - 1)
                if not isRightEdge:
                    self._update_adjacency(upper_mid + 1)
            if not isLeftEdge:
                self._update_adjacency(coor - 1)
            if not isRightEdge:
                self._update_adjacency(coor + 1)
            if not isBottomEdge:
                lower_mid = coord + self.col
                self._update_adjacency(lower_mid)
                if not isLeftEdge:
                    self._update_adjacency(lower_mid - 1)
                if not isRightEdge:
                    self._update_adjacency(lower_mid + 1)

    def _update_adjacency(coord: int) -> None:
        if 0 <= coord <= self.row * self.col:
            # Can have from 0..8 adjacents with mines
            if 0 <= self.grid[coord] < 8:
              self.grid[coord] += 1

    def _isTopEdge(coord: int) -> Bool:
        return coord < self.cols

    def _isLeftEdge(coord: int) -> Bool:
        if coord == 0:
            return True
        if coord > self.cols:
            return coord % self.cols == 1
        return False
        
    def _isRightEdge(coord: int) -> Bool:
        if coord >= self.cols:
            return coord % self.cols == 0
        return False

    def _isBottomEdge(coord: int) -> Bool:
        return (self.row - 1) * self.col <= coord <= self.row * self.col

I probably have several off-by-one errors above because of zero-indexing.