minesweeper.py

__all__ = [
    "Array2D",
    "LostGameError",
    "Minefield",
    "loadMinefieldsFromFile",
    "saveRandomMinefieldsToFile",
    "testSolver",
    "playGame",
]

import math
import random


class Array2D(object):
    """
    Represents a 2D rectangular array of objects.  In addition to methods
    to access elements, Array2Ds also have a copy() method which creates
    a shallow copy of the array.

    Example:
        arr = Array2D(3,5, ".")
        arr[0,0] = "x"
        arr[1,3] = "o"
        print "\n".join(
            "".join(
                    arr[r,c] for c in xrange(arr.ncols))
            for r in xrange(arr.nrows))

    Output:
        x....
        ...o.
        .....
    """

    def __init__(self, nrows, ncols, value=None):
        self.nrows, self.ncols = nrows, ncols
        self.__data = [value]*(nrows*ncols)

    def __getitem__(self, key):
        if isinstance(key, int):
            return self.__data[key]
        else:
            assert len(key) == 2
            index = self.__rc2ind(key[0], key[1])
            return self.__data[index]

    def __setitem__(self, key, value):
        if isinstance(key, int):
            self.__data[key] = value
        else:
            assert len(key) == 2
            index = self.__rc2ind(key[0], key[1])
            self.__data[index] = value
        return self

    def copy(self):
        arr = Array2D(self.nrows, self.ncols)
        arr.__data = self.__data[:]
        return arr

    def __rc2ind(self, r, c):
        assert r >= 0 and r < self.nrows
        assert c >= 0 and c < self.ncols
        return r + c*self.nrows


class LostGameError(RuntimeError):
    """
    This is the type of exception thrown when a mine is triggered.
    """
    pass


class Minefield(object):
    """
    Represents the state of a game of Minesweeper.  The game takes place on a
    rectangular grid of squares with some number of mines randomly distributed
    at unknown locations.  The size of the grid and the total number of mines
    can be retrieved with the methods nRows(), nCols() and nMines().

    Each square may be visible or hidden.  Visible squares are squares where
    the user has made a guess and confirmed not to contain a mine.  Hidden
    squares may or may not contain a mine.  To switch a square from hidden
    to vissible, call the method guess(r,c) with the row and column of the
    square.  If the square contains a mine a LostGameError will be thrown,
    otherwise it will be set to visible.  It is guaranteed that the very
    first guess of the game will not be on a mine, and the all of the
    squares orthogonally or diagonally adjacent to this first guess will also
    not contain mines.  Other than this, the mines are distributed randomly.

    If a square is visible, the total number of mines in the squares
    orthogonally or diagonally adjacent to it can be retreived with the
    method nMinesAround(r,c), which takes as input the row and column
    of a visible square and returns an int indicating the total number
    of mines surrounding it.

    There are a number of utility methods provided to help you in writing
    an AI to play the game.  Info about these methods can be found in
    the a comment within each such method.
    """

    def __init__(self, nrows, ncols, nmines, rand=None):
        assert nrows > 1 and ncols > 1
        self.__nrows, self.__ncols = nrows, ncols
        self.__nmines = nmines
        self.__rand = rand
        self.__mines = None
        self.__visible = Array2D(nrows, ncols, False)

    def nRows(self):
        """
        Returns the number of rows in the grid of mines for this game.
        """
        return self.__nrows

    def nCols(self):
        """
        Returns the number of columns in the grid of mines for this game.
        """
        return self.__ncols

    def nMines(self):
        """
        Returns the total number of mines in this game.
        """
        return self.__nmines

    def guess(self, r, c):
        """
        Call this to make a guess that the square at r,c does not contain a
        mine.  If the guess is correct and there is no mine in the square,
        the square is set to visible.  If there is a mine there then a
        LostGameError is thrown.
        """
        if (self.__mines is not None) and self.__mines[r,c]:
            raise LostGameError, "you exploded!!!"
        else:
            self.__visible[r,c] = True
            if self.__mines is None:
                self.__initMines()

    def isVisible(self, r, c):
        """
        Returns True if the given square in visible, and false if it is
        hidden.
        """
        return self.__visible[r,c]

    def nSquares(self):
        """
        Returns the total number of squares in the grid for this game.
        """
        return self.nRows() * self.nCols()

    def nVisible(self):
        """
        Returns the total number of currently visible squares in the grid
        for this game.
        """
        return sum(1 for r,c in self.iterVisible())

    def nHidden(self):
        """
        Returns the total number of currently hidden squares in the grid for
        this game.
        """
        return sum(1 for r,c in self.iterHidden())

    def isSolved(self):
        """
        Returns True if the game has been successfully solved, and False
        otherwise.
        """
        assert self.nHidden() >= self.nMines()
        return self.nHidden() == self.nMines()

    def nMinesAround(self, r, c):
        """
        Returns the total number of mines in all the squares orthogonally or
        diagonally adjacent to the square at (r,c).  The square at (r,c) must
        be visible, and an exception is thrown if it's not.
        """
        if self.__visible[r,c]:
            return sum(1 for r2,c2 in self.iterNeighbors(r,c) if self.__mines[r2,c2])
        else:
            raise RuntimeError, "you can't see how many mines are around a non-visible square"

    def nSquaresAround(self, r, c):
        """
        Returns the total number of squares orthogonally or diagonally
        adjacent to the square at (r,c).  This will be 8 for an interior
        square, 5 for an edge square, and 3 for a corner square.
        """
        return sum(1 for r2,c2 in self.iterNeighbors(r,c))

    def nVisibleAround(self, r, c):
        """
        Returns the total number of currently visible squares orthogonally or
        diagonally adjacent to the square at (r,c).
        """
        return sum(1 for r2,c2 in self.iterNeighbors(r,c) if self.isVisible(r2,c2))

    def nHiddenAround(self, r, c):
        """
        Returns the total number of currently hidden squares orthogonally or
        diagonally adjacent to the square at (r,c).
        """
        return sum(1 for r2,c2 in self.iterNeighbors(r,c) if not self.isVisible(r2,c2))

    def iterNeighbors(self, r, c):
        """
        Iterates over (row,column) tuples of all the squares orthogonally or
        diagonally adjacent to the square at (r,c).
        """
        if c > 0:
            if r > 0: yield (r-1, c-1)
            yield (r, c-1)
            if r+1 < self.nRows(): yield (r+1, c-1)

        if r > 0: yield (r-1, c)
        if r+1 < self.nRows(): yield (r+1, c)

        if c+1 < self.nCols():
            if r > 0: yield (r-1, c+1)
            yield (r, c+1)
            if r+1 < self.nRows(): yield (r+1, c+1)

    def iterSquares(self):
        """
        Iterates over the (row,column) tuples of all the squares in the grid.
        """
        for r in xrange(self.nRows()):
            for c in xrange(self.nCols()):
                yield (r,c)

    def iterVisible(self):
        """
        Iterates over the (row,column) tuples of all the currently visible
        squares in the grid.
        """
        for r,c in self.iterSquares():
            if self.isVisible(r,c):
                yield (r,c)

    def iterHidden(self):
        """
        Iterates over the (row,column) tuples of all the currently hidden
        squares in the grid.
        """
        for r,c in self.iterSquares():
            if not self.isVisible(r,c):
                yield (r,c)

    def isInterior(self, r, c):
        """
        Iterates over the (row,column) tuples of all the squares in the grid
        which are both currently hidden, and for which all the orthogonally
        and diagonally adjacent neighbors are currently hidden.
        """
        if self.isVisible(r,c): return False
        for r2,c2 in self.iterNeighbors(r,c):
            if self.isVisible(r2,c2): return False
        return True

    def iterInterior(self):
        """
        Iterates over the (row,column) tuples for all the squares in the grid
        for which isInterior(row,column) returns True.
        """
        for r,c in self.iterSquares():
            if self.isInterior(r, c):
                yield (r,c)

    def isInBounds(self, r, c):
        """
        Returns True if the given square is within the game grid, and False
        otherwise.
        """
        return (r >= 0) and (c >= 0) and (r < self.nRows()) and (c < self.nCols())

    def copy(self):
        """
        This is provided purely as a convienence function to help you in
        writing an AI to play the game.  This method returns a copy of the
        complete game state, so any modifications made to the copy with
        leave the original unchanged.
        """
        grid = Minefield(self.nRows(), self.nCols(), self.nMines())
        if self.__mines is not None:
            grid.__mines = self.__mines.copy()
        grid.__visible = self.__visible.copy()
        return grid

    def __str__(self):
        """
        Returns a string showing the state of the Minesweeper game in crude
        ASCII art.  Row and column labels are also included.
        """

        def cellStr(r, c):
            if self.__mines is None:
                return "."
            elif self.isVisible(r,c):
                n = self.nMinesAround(r,c)
                if n == 0:
                    return " "
                else:
                    return str(n)
            else:
                return "."

        nRowDigits = int(math.ceil(math.log(self.nRows(),10)))
        nColDigits = int(math.ceil(math.log(self.nCols(),10)))

        colStrs = [str(c+1).rjust(nColDigits) for c in xrange(self.nCols())]
        colNumbersStr = "\n".join(
            " "*nRowDigits + "  " + " ".join(
                colStrs[c][i] for c in xrange(self.nCols()))
            for i in xrange(nColDigits))

        return "\n".join(
            str(r+1).rjust(nRowDigits) + "  " + " ".join(
                cellStr(r,c)
                for c in xrange(self.nCols()))
            for r in xrange(self.nRows())) + "\n\n" + colNumbersStr

    @staticmethod
    def LoadMinesFromString(gridStr):
        """
        Loads the mine placement from the input string.  The format of the string
        should math that created by saveMinesToString()
        """
        lines = gridStr.split("\n")
        nrows, ncols, nmines = [int(s) for s in lines[0].split(" ")]
        assert len(lines)-1 == nrows

        grid = Minefield(nrows, ncols, nmines)
        grid.__mines = Array2D(nrows, ncols, False)
        for r, line in enumerate(lines[1:]):
            assert len(line) == ncols
            for c, s in enumerate(line):
                if s == "x":
                    grid.__mines[r,c] = True
        return grid

    def saveMinesToString(self):
        """
        Create a string storing the location of the mines in this minefield,
        including any currently hidden mines.  The format of this string is
        such that a new Minefield can be created from it with LoadMinesFromString()
        """
        def cellStr(i,j):
            if self.__mines[i,j]:
                return "x"
            else:
                return "o"

        return str(self.nRows()) + " " + str(self.nCols()) + " " + str(self.nMines()) + "\n" + "\n".join(
            "".join(
                cellStr(r,c)
                    for c in xrange(self.nCols()))
                for r in xrange(self.nRows()))

    def __initMines(self):
        """
        This function is for internal use only, so don't call it.
        """
        self.__mines = Array2D(self.nRows(), self.nCols(), False)
        openCells = list(self.iterInterior())
        if self.__rand is None:
            random.shuffle(openCells)
        else:
            self.__rand.shuffle(openCells)
        for i in xrange(self.nMines()):
            r,c = openCells[i]
            self.__mines[r,c] = True


def loadMinefieldsFromFile(fname):
    """
    Loads a list of Minefield objects from a file.  The format of the file
    is such that it can be created with saveRandomMinefieldsToFile()
    """
    with open(fname, "r") as f:
        fileString = f.read()
    gridStrings = fileString.split("\n-----\n")
    return [Minefield.LoadMinesFromString(s) for s in gridStrings]


def saveRandomMinefieldsToFile(fname, ngrids, nrows, ncols, nmines):
    """
    Generated a bunch of random Minefields and saves them to a file.  The mines
    are distributed assuming that the first guess is at nrows/2, ncols/2.  The
    format of this string is such that the Minefields can be loaded with
    loadMinefieldsFromFile()
    """
    gridStrings = []
    for i in xrange(ngrids):
        grid = Minefield(nrows, ncols, nmines)
        grid.guess(nrows/2, ncols/2)
        gridStrings.append(grid.saveMinesToString())
    with open(fname, "w") as f:
        f.write("\n-----\n".join(gridStrings))


def testSolver(solverFcn, nsamples=100, isControlTest=False, **params):
    """
    Tests a function for solving minesweeper games and reports its win
    percentage on four different difficulties:

    debugging:     9 x 9  grid with  1 mine
    beginner:      9 x 9  grid with 10 mines
    intermediate: 16 x 16 grid with 40 mines
    expert:       16 x 30 grid with 99 mines

    The testSolver function takes a single parameter, which is itself a
    function. This function should take as input a Minefield, and either
    return if successfully solves the game, or throws a LostGameError if it
    hits a mine.
    """

    testCases = [
        ("debugging"    , (9 , 9,  1)),
        ("beginner"     , (9 , 9, 10)),
        ("intermediate" , (16,16, 40)),
        ("expert"       , (16,30, 99)),
    ]

    if isControlTest:
        rand = random.Random(34559)
    else:
        rand = None

    testResults = []
    for testName, (nrows, ncols, nmines) in testCases:
        print "testing '{:s}' difficulty".format(testName)

        if testName in params:
            print "    loading from file {}".format(params[testName])
            grids = loadMinefieldsFromFile(params[testName])
        else:
            grids = None

        nwins = 0
        for i in xrange(nsamples):
            if grids is None:
                grid = Minefield(nrows, ncols, nmines, rand=rand)
            else:
                if i < len(grids):
                    grid = grids[i]
                    assert grid.nRows() == nrows
                    assert grid.nCols() == ncols
                    assert grid.nMines() == nmines
                else:
                    print "    could not test enough samples since the provided file was too short"
                    break
            isWin = False
            try:
                if isControlTest:
                    random.seed(7669)
                solverFcn(grid)
                if grid.isSolved():
                    isWin = True
                    nwins += 1
                else:
                    print "error: the game was not actually solved by the solver function"
                    print "this indicates a bug in the solution method"
                    return

            except LostGameError as e:
                pass
            print "    {:d} / {:d}  ({:s})".format(i+1, nsamples, "win" if isWin else "loss")
        winProbability = nwins / float(nsamples)
        testResults.append((testName, winProbability))

    for testName, winProbability in testResults:
        winPercent = int(100*winProbability)
        print "{:s}: {:d}%".format(testName, winPercent)


def playGame(nrows, ncols, nmines):
    """
    Plays a game of Minesweeper using a basic text interface.  This is
    intended to illustrate how to use the Minefield class, so it's not a
    particularly user friendly interface.
    """

    def intInput(minVal, maxVal):
        while True:
            s = raw_input("> ")
            try:
                i = int(s)
                if minVal <= i <= maxVal:
                    return i
            except:
                pass
            print "please input an integer between {:d} and {:d}".format(minVal, maxVal)

    grid = Minefield(nrows, ncols, nmines)

    while True:
        print "number of mines: {:d}".format(grid.nMines())
        print grid
        print

        print "enter row of square to select:"
        row = intInput(1, nrows)-1
        print "enter column of square to select:"
        col = intInput(1, ncols)-1

        try:
            grid.guess(row,col)
            if grid.isSolved():
                print "you a winner"
                return True
        except LostGameError:
            print "BOOM.  you ded"
            return False