How would you represent a MineSweeper grid in Python?
What datastructure would you use in Python to represent the internal state of a MineSweeper grid?
Each x,y position will hold a numerical value which represents its current cell state (unexplored, mine, flag, ?).
Should I use nested lists? This seems like the closest thing to a 2D array and it is what I would probably use in any other language (2d array that is).
I'm not that experienced with Python so could someone give me a sug开发者_开发百科gestion?
Use a nested list. It's easy to set up:
field = [([None] * height) for x in range(width)]
field[x][y] = "*"
The clearest thing would probably be a new class:
class MineField(object):
class _SingleField(object):
mine = False
flagged = False
covered = True
width = None
height = None
def __init__(self, width, height):
super(MineField, self).__init__()
self.width = width
self.height = height
self._field = [[self._SingleField() for y in range(height)]
for x in range(width)]
self.init_field(10)
def init_field(self, minecount):
pass
def __getitem__(self, index):
x, y = index
return self._field[x][y]
To be used like this:
> m = MineField(10,10) > m[4,9].mine False
you could use a 2 dimensional array, holding objects for the state of each field:
class FieldState(object):
def __init__(self):
self.unexplored = True
self.mine = Random()
self.flag = Random()
...
for x in range(12):
for y in range(24):
list[x][y] = FieldState()
Just to throw another option in the mix, you could use dicts indexed by tuples
board = {}
board[1, 2] = 9
If you use an instance of Board
class you can always change the internal representation later.
class Board(object):
def __init__(self, width, height):
self.__width, self.__height = width, height
self._board = [[FieldState() for y in xrange(height)]
for x in xrange(width)]
@property
def width(self):
return self.__width
def mark(self, x, y):
self._board[x][y].mark()
def __getitem__(self, coord):
"""
>>> board = Board(3, 4)
>>> field = board[1,2] # 2nd column, 3rd row
"""
x, y = coord
return self._board[x][y]
...
Where FieldState
is similar to the one from @zlack's answer.
I think there are basically two layers of data: 1) map data: does square have a bomb (e.g represented by -1) or how many bombs are around it, 2) display data, what is shown on the square: bomb count, bomb, flag, question mark, empty, unopened.
So two nested lists (or one nested list of tuples) might be enough.
You could mark locations with a single int showing exactly what sits there, easing your coding considerably. You wouldnt need two data layers.
00 nothing, noflag
10 bomb, noflag
01 nothing,flagged
11 bomb, flagged
Now since the first bit of that int shows whether there is a bomb or not, we can actually give it a few more bits and indicate neighbour count as well.
000 no-neighbor
001 one neighbor
010 two...
and so on. Storing this only takes a single byte and even leaves room for expansion.
A map of 'tile' or 'cell' objects, keyed to the coordinates as a pair.
current = (1,1)
if grid[current].isFlagged():
do_whatever;
Of course, map takes a little more space than array, and the tile class will have a tiny bit more footprint than a primitive bitmap or number, but I assume your board isn't 1024x1024 and you're not in a highly constrainted RAM situation.
If you do more than look up the tiles in the grid, then do consider JF's Board object to wrap the array.
Python is an OO language, and often the simplest and clearest thing that works is to use classes and objects wisely.
Note: you might also look at the named_tuple class for situations that seem too simple for a proper class.
精彩评论