game.py

#!/usr/bin/env python
import random
import re
import sys

from collections import defaultdict, namedtuple
from itertools import chain, count
from operator import add
from random import choice
from string import uppercase


########################################################################
# LOOKUP TABLES
########################################################################

#===================================================
# Shift Table
#===================================================
def shift_table():
    ''' List of tuples to add with a cell to find neighbors '''
    x_vals = [-1, -1, -1, 0, 0, 1, 1, 1]
    y_vals = [-1, 0, 1, -1, 1, -1, 0, 1]
    return zip(x_vals, y_vals)

shifts = shift_table()

#===================================================
# Valid Cells Table
#===================================================
def valid_cell_table(height=15, width=15):
    ''' A set of tuples where each tuple is a valid cell coordinate pair '''
    return set([(i, j) for i in range(width) for j in range(height)])

valid_cells = valid_cell_table()

#===================================================
# User Cell Choice Table
#===================================================
def letter_table(height=15, width=15):
    ''' A dict for looking up the tuple equivalent to A1-Z26.

        Range: A1: (0, 0) to "%s%s" % (letters[width], height+1) '''
    keys = ['%s%s' % (c, n) for c in uppercase[:width]
            for n in range(1, height + 1)]
    values = [cell for cell in sorted(valid_cells)]
    return {k: v for k, v in zip(keys, values)}

letters = letter_table()

#===================================================
# Neighbors lookup table
#===================================================

# Helper functions
def shift_cell(cell, shift):
    ''' Add cell + shift, and return the result '''
    x1, x2, y1, y2 = cell + shift
    candidate = (x1 + y1, x2 + y2) 
    return candidate

def valid_neighbors(cell):
    ''' Return a list of valid neighbors for `cell` '''
    neighbors = []
    for shift in shifts:
        candidate = shift_cell(cell, shift)
        if candidate in valid_cells:
            neighbors.append(candidate)
    return neighbors
        
# Table Creation
def neighbors_table():
    ''' Each key is a tuple (0, 0) and the value is a list of valid neighors.
        neighbors[(0, 0)] == [(0, 1), (1, 0), (1, 1)] '''
    return {cell: valid_neighbors(cell) for cell in valid_cells}

neighbors = neighbors_table()
nums = [str(n) for n in range(1, 9)]

#===================================================
# Cell value/symbol tables
#===================================================

cell_values = {'null': ' ',
               'mine': 'X',
               'safe': '9',
               'flag': nums}

cell_symbols = {'mark': '!',
                'poss': '?',
                'hide': '#'}


########################################################################
# CLASSES / DATA STRUCTURES
########################################################################

def cells(width=15, height=15):
    '''
    cells returns a dict that holds all the Cell instances.

    The keys are coordinate tuples, and the values are Cell instances.
    A Grid instance holds a list of lists, and the list items are tuples
    corresponding to the keys from cells. Cell instances are updated and
    displayed by accessing values of this dictionary. Creating this 
    dictionary separates map generation from map updating, which should
    simplify things.
    '''
    return {pair: Cell(*pair) for pair in valid_cells}

class Cell(object):
    '''
    A class representing a minesweeper cell.

    ARGUMENTS:
        x, y - positive cartesian coordinates, starting at 0, 0
        
    '''
    def __init__(self, x, y, value=cell_values['null'],
                 symbol=cell_symbols['hide'], hidden=True):
        self.x = x
        self.y = y
        self.value = value
        self.symbol = symbol
        self.hidden = hidden

    def __str__(self):
        return "(%s, %s)" % (self.x, self.y)

    def coords(self):
        ''' Return an (x, y) tuple for lookups '''
        return (self.x, self.y)

    def protect(self):
        ''' Guard cells during mine placement to prevent the
            player from losing on turn one. This swaps from
            null to safe, or safe to null '''
        if self.value == cell_values['null']:
            self.value = cell_values['safe']
        else:
            self.value = cell_values['null']

    def reveal(self):
        ''' Reveal a cell '''
        self.hidden = False
        self.symbol = self.value

    def mark(self):
        ''' Change the mark a user has made on a cell. The cycle is
            hide -> flag -> possible -> hide -> flag ... '''
        if self.symbol == cell_symbols['hide']:
            self.symbol = cell_symbols['flag']
        elif self.symbol == cell_symbols['flag']:
            self.symbol = cell_symbols['poss']
        elif self.symbol == cell_symbols['poss']:
            self.symbol = cell_symbols['hide']
        else:
            raise ValueError('Invalid symbol')

    def check_type(self, cell_type):
        ''' Determine a cell's type based on its value '''
        assert cell_type in cell_values.keys()
        return self.value in cell_values[cell_type]


class Grid(object):
    ''' This class holds and updates the cell grid, counter values,
        and handles output. '''
    def __init__(self, cells, mines, flags, height=15, width=15):
        # these don't get modified by the class instance at all
        self.height = height
        self.width = width
        self.mines = mines
        self.flags = flags
        self.pairs = letters.keys()
        # these are modified by the class instance
        self.cells = cells
        self.stack= set()

    # Counter methods
    def increment(self, counter):
        self.counter += 1

    def decrement(self, counter):
        self.counter -= 1

    def reveal(self, origin):
        # depth-first search flood fill
        #
        # thanks to reid barton for helping me fix this

        # get current cell
        cell = self.cells[origin]
        # if it is a mine, declare a game over
        if cell.value == cell_values['mine']:
            self.game_over = True
            return False
        if origin in self.stack:
           return True
        # if it is a number, reveal it an return
        elif cell.value in cell_values['flag']:
            self.unhide(origin)
            return True
        # if it is an empty cell, reveal it, reveal adjacent numbers,
        # then recurse onto adjacent empty spaces
        elif cell.value == cell_values['null']:
            self.unhide(origin)
            cell_neighbors = neighbors[origin]
            for neighbor in cell_neighbors:
                    self.reveal(neighbor)
        else:
            raise ValueError('Unknown cell value.')

    def reset_stack(self):
        while self.stack:
            cell = self.stack.pop()
            self.cells[cell].reveal()
    
    def unhide(self, origin):
        self.stack.add(origin)

class Game(object):

    def __init__(self, cells, mines, flags):
        
        self.grid = Grid(cells, mines, flags)
        self.marks = []

        self.turn_count = 0
        self.mark_count = len(self.marks)
        self.mine_count = len(self.grid.mines)

        self.won = False
        self.game_over = False

    def won(self):
        ''' Determine if we've won '''
        marked = sorted(self.grid.marks) == sorted(self.grid.mines)
        uncovered = all([self.grid.cells[cell].hidden
                         for cell in valid_cells if not cell in self.grid.mines])
        return marked and uncovered

    def output(self):
        grid = symbol_grid(self.grid.cells)
        status_bar = self._status_bar()
        header = self._header()
        display = self._display(grid)
        prompt = self._prompt()
        return status_bar + '\n' + header + display +'\n' + prompt

    def update(self, cell, choice):
        if choice == 'R':
            self.grid.reveal(cell)
        elif choice == 'M':
            self.grid.cells[cell].mark()
        elif choice == 'Q':
            # we either quit or exit the function
            self._quit()
        else:
            sys.exit("Prevent this shit")

    # private methods for handling input
    #===================================

    # handle guess
    def _guess(self):
        while True:
            user_guess = raw_input("Enter your guess > ")
            user_guess = user_guess.capitalize()
            if user_guess in self.pairs:
                return user_guess
            else:
                print "%s is not a valid cell." % user_guess
                continue

    # handle quit
    def _quit(self):
        while True:
            ans = raw_input("Really quit? Y/n>")
            if ans == 'Y':
                sys.exit('See you soon')
            elif ans == 'n':
                return
            else:
                continue

    # private methods for creating the output grid

    # make alphabetic header
    def _header(self, head=0):
        '''
        Returns column headers from A-width
        '''
        header = [uppercase[i] for i in range(self.grid.width)]
        header.insert(head, '   ')
        header.append(' \n')
        return '|'.join(header)
    
    # create the grid the player sees.
    # format: '<padding>
    def _display(self, grid, head=0):
        for idx, row in enumerate(grid):
            i = idx + 1
            if len(str(i)) == 1:
                row.insert(head, '  %s' % i)
            else:
                row.insert(head, ' %s' % i)
            row.append(' \n')
        return ''.join(['|'.join(row) for row in grid])

    def _prompt(self):
        ''' Prompt that prints each turn '''
        return "(R)eveal, (M)ark, (Q)uit"

    def _status_bar(self):
        stats = (self.mine_count, self.mark_count, self.turn_count)
        return "Mines: %s | Marks: %s | Turns: %s\n" % (stats)



#===================================================
# Grid initialization functions
#===================================================

def protect_area(origin):
    '''
    This function is called twice. The first time, it changes the value
    of each cell to '9', an otherwise impossible value. This prevents 
    the user from dying on turn 1. After mine placement is finished, 
    this function is called again, which changes all '9' valued cells
    back to ' ' cells.
    '''
    for cell in neighbors[origin]:
        cells[cell].protect()
    cells[origin].protect()

def random_cell(height=15, width=15):
    ''' Return a tuple of valid cell coordinates '''
    random_cell = (random.choice(range(width)), random.choice(range(height)))
    assert random_cell in valid_cells
    return random_cell

def place_mines(mines, initial_pick=(7, 7), height=15, width=15):
    ''' Place mines on the grid by setting a cell's value to 'X'
        Return a list of mine (x, y) tuples. '''
    protect_area(initial_pick)
    mine_list = []
    while mines:
        mine = random_cell(height, width)
        if cells[mine].check_type('null'):
            cells[mine].value = cell_values['mine']
            mine_list.append(mine)
            mines -= 1
    protect_area(initial_pick)
    return mine_list

def place_flags(mines):
    ''' Place numeric flags adjacent to all mines.
        Return a list of flag cells. '''
    flag_cells = defaultdict(int)
    for mine in mines:
        neighbor_list = neighbors[mine]       
        for neighbor in neighbor_list:
            if neighbor not in mines:
                flag_cells[neighbor] += 1
    for cell, value in flag_cells.iteritems():
        cells[cell].value = str(value)
    return flag_cells.keys()

def value_grid(cells, height=15, width=15):
    return [[cells[(i, j)].value for i in range(width)] for j in range(height)]

def symbol_grid(cells, height=15, width=15):
    return [[cells[(i, j)].symbol for i in range(width)] for j in range(height)]

def valjoined(grid):
    rows = ['|'.join(row) for row in grid]
    return '\n'.join([r for r in rows])

if __name__ == '__main__':
    # TESTING enables automatic first cell
    # DEBUG enables TESTING and some additional debugging info
    # VERBOSE enables the previous ones plus it prints all the lookup tables
    TESTING = True
    DEBUG = False
    VERBOSE = False
    EITHER = DEBUG or TESTING
    ANY = EITHER or VERBOSE

    if EITHER:
        from pprint import pprint

    if VERBOSE:
        # print lookup tables
        print 'shifts'
        pprint(shifts)
        print 'valid cells'
        pprint(valid_cells)
        print 'letters'
        pprint(letters)
        print 'neighbors'
        pprint(neighbors)

    n_mines = 20
    if ANY:
        initial_pick = (7, 7)
    cells = cells()
    mines = place_mines(n_mines, initial_pick)
    flags = place_flags(mines)
    if DEBUG:
        print "#" * 40
        print "SYMBOLS"
        print(valjoined(symbol_grid(cells)))
        print "#" * 40
        print "VALUES"
        print(valjoined(value_grid(cells)))
        print
    minesweeper = Game(cells, mines, flags)
    minesweeper.grid.reveal(initial_pick)
    minesweeper.grid.reset_stack()
    print minesweeper.output()