"""CR11 End-of-semester Examination 2010/11. An implementation of a game similar to Boggle (tm Parker Bros). The game consists of 16 cubes, with each face of a cube showing a letter (A-Z). The cubes are arranged in a 4x4 grid. At the start of each round, the board containing the cubes is shaken to randomise the letters shown in the grid. Each player then has to try and construct words by starting from one letter in the grid, and moving to adjacent (horizontal, vertical or diagonal) letters to spell out the word. The same cube cannot be used more than once within a given word. Play alternates between players for an agreed number of rounds. Players are awarded points depending on the number of letters in each word. The legality of each word proposed is checked, firstly against the board (can the word be formed by moving between the letters shown on the cubes), and secondly against an agreed dictionary (it it a legal English word). The game, as implemented here, has some differences between the commercial version, principally (a) the lack of a timer, and (b) different rules for scoring words. """ import random class Cube: """This class represents one of the cubes used in the game, which has one letter on each face. One letter corresponds to the "top" face. The method 'shake' represents the cube being thrown about to change the top face.""" def __init__(self, letters): self.faces = letters self.top = letters[0] def __str__(self): return self.top def shake(self): """Simulate throwing the cube, changing the face shown on top.""" offset = random.randint(0,5) self.top = self.faces[offset] class Board: """Simulate the baord used in the game of Boggle, consisting of 16 cubes arranged in a 4x4 grid, each cube carrying a letter on each of its faces. The class supports methods to randomize the grid, and to check a word against the letters on the grid.""" # Class variable, representing the offsets of neighbouring # cubes, used in tracing a path through the board to check # a word. neighbours = [ (-1,-1), (0,-1), (1,-1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1) ] # Each cube has 6 letters (one per face); the distribution # of letters over cubes reflects distribution of letters # in English words. faces = [ "AAEEGN", "ABBJOO", "ACHOPS", "AFFKPS" , "AOOTTW", "CIMOTU", "DEILRX", "DELRVY" , "DISTTY", "EEGHNW", "EEINSU", "EHRTVW" , "EIOSST", "ELRTTY", "HIMNQU", "HLNNRZ" ] def __init__(self): self.cubes = {} self.letters = {} for i in range(1,5): for j in range(1,5): self.cubes[(i,j)] = Cube(Board.faces[(i-1)*4 + j - 1]) self.letters[(i,j)] = str(self.cubes[(i,j)]) self.used = [] def shake(self): """Simulate shaking the board, by (a) shaking each cube, and (b) randomly rearranging the cubes within the board.""" # First of all shuffle cubes around. Implemented by doing # 16 exchanges of randomly selected pairs of cubes. for i in range(0,16): srci = random.randint(1,4) srcj = random.randint(1,4) dsti = random.randint(1,4) dstj = random.randint(1,4) temp = self.cubes[(dsti,dstj)] self.cubes[(dsti,dstj)] = self.cubes[(srci,srcj)] self.cubes[(srci,srcj)] = temp # Second, shake each cube, and record the letter on top. for i in range(1,5): for j in range(1,5): self.cubes[(i,j)].shake() self.letters[(i,j)] = str(self.cubes[(i,j)]) def display(self): """Display the 4x4 grid of letters defined by the tops of the cubes.""" for i in range(1,5): for j in range(1,5): print( self.letters[(i,j)], ' ', end='' ) print('') print('') def onBoard(self, i, j): """Test whether an arbitrary (i,j) pair represents the position of a cube on the Boggle board.""" return i > 0 and i < 5 and j > 0 and j < 5 def getLetters(self): """Return a string containing the letters that appear on the board, in alphabetical order.""" chars = [] for i in range(1,5): for j in range(1,5): chars.append(self.letters[(i,j)]) chars.sort() str = '' for char in chars: str += char return str def checkWord(self, word): """Determine whether a given word can be constructed from the letters displayed on this board. We do an exhaustive search, trying to match the word from the 16 possible starting positions on the grid.""" self.used = [] for si in range(1,5): for sj in range(1,5): if self.tryAt(word.upper(), si, sj): return True return False def tryAt(self, word, i, j): """Determine if 'word' can be constructed on the board by starting at position (i,j). If the word is empty, the answer is trivially yes. One cube on the board cannot be used for more than one letter of the word, so if the current cube has been used, the answer is trivially no. Likewise, if the letter at position (i,j) doesn't match the first letter of the word. Otherwise, if we have a partial match, we then have to try to match the remainder of the word, looking at each of the possible neighbours of the current square for the continuation. We first mark the current square as used, then explore neighbours. If the partial match cannot be completed, we unmark the current square and return, effectively back-tracking the search.""" if word == '': return True elif (i,j) in self.used: return False elif self.letters[(i,j)] != word[0]: return False else: self.used.append((i,j)) for di,dj in Board.neighbours: iNew = i + di jNew = j + dj if self.onBoard(iNew, jNew): if self.tryAt( word[1:], iNew, jNew): return True self.used.remove((i,j)) return False class Dictionary: """The Dictionary class is a container for a list of words read from a file, which specify the allowed words for the game. The name of the file containing the words is given as the single argument to the class constructor. The class exports one method for checking whether a given word is in the dictionary. In addition to a list of words, the dictionary class also provides an inverted dictionary, a list of pairs of words of a given length, where each pair consists of the string of characters in the word ordered alphabetically, and the word itself, for example ("act", "cat") and ("dgo", "dog") would be in the list of pairs of length 3. These inverse lists can be accessed via the 'inverseWords' method.""" def __init__(self, wordFile): # Initialise instance variables for the list of # words and the inverse dictionary. self.words = [] self.inverse = {} for size in range(1,17): self.inverse[size] = [] # Read the words from the external file. file = open(wordFile, 'r') for line in file: word = line[:-1] length = len(word) if length <= 16: self.words.append(word) chars = list(word) chars.sort() inverted = '' for c in chars: inverted += c self.inverse[length].append((inverted, word)) file.close() def contains(self,word): return word.lower() in self.words def inverseWords(self, size): return self.inverse[size] class Player: """A class representing Boggle players. Each player holds their number (order of play), name, and current score. In addition, player objects require reference to the board so that legitimacy of words can be checked. Access to a word dictionary is provided via a class variable.""" dictionary = Dictionary('english.0') def __init__(self, pnr, theBoard): self.nr = pnr self.board = theBoard self.name = self.getName() self.score = 0 def getName(self): return input("Player number {:d}'s name? ".format(self.nr)) def __str__(self): return '{:s}, score {:d}'.format(self.name, self.score) def gain(self, points): """The player earns a number of points.""" self.score += points def scoreTurn(self, words): """Check through the list of words, incrementing the player's score for words that are allowed.""" for wd in words: print(wd, ' ... ', end='') if not self.board.checkWord(wd): print('could not be made from the board.') elif not Player.dictionary.contains(wd): print('is not a legal word.') else: points = len(wd) print('scores', points, 'points') self.gain(points) print('') def takeTurn(self): """Allow a player to have a turn. The player is shown the state of the board, then invited to enter a list of words that they can form from the board. Once the list has been entered, the object checks each word against the board and the dictionary, and calculates a score for this turn.""" print("Player {:d}'s turn.".format(self.nr)) print(self) print('') self.board.display() print('Enter your words [blank line to end turn]') words = [] wordnr = 1 while True: word = input('{:d} > '.format(wordnr)) if word == '': break else: words.append(word) wordnr += 1 print('') self.scoreTurn(words) class Computer(Player): """An implementation of a (hopeless) computer as player.""" def __init__(self, pnr, theBoard): super().__init__(pnr, theBoard) def getName(self): return 'Computer' # Question 3(B) def takeTurn(self): print('Computer is thinking ...\n') self.board.display() print('') print("I couldn't find any words!") class Game: """The Boggle Game. An instance of the game involves a number of players and an agreed number of rounds. The players share a common board. At the start of each round, the board is shaken to randomize the letters shown.""" def __init__(self, nrPlayers, nrRounds, robot): self.nrPlayers = nrPlayers self.nrRounds = nrRounds self.board = Board() self.players = [] for i in range(1, self.nrPlayers+1): self.players.append(Player(i, self.board)) if robot: self.players.append(Computer(nrPlayers+1, self.board)) self.nrPlayers += 1 def oneRound(self): self.board.shake() for p in self.players: p.takeTurn() def play(self): self.board.shake() for r in range(1, self.nrRounds+1): print('Starting round {:d} ...\n'.format(r)) self.oneRound() print('\nGame over - final results are as follows:') for p in self.players: print(p) # Auxilliary functions and top-level code. def get_number(prompt, lo, hi): """Auxiliary function. prompt the user for a whole number in the range lo-hi inclusive, and return it.""" while True: try: value = int(input('{:s} ({:d}-{:d})? '.format(prompt,lo,hi))) if value < lo or value > hi: print('Number must be between {:d} and {:d}.'.format(lo,hi)) else: break except ValueError: print('Not a valid number, please try again.') return value def get_boolean(prompt): """Prompt the user for a yes/no response, and return the result as a boolean value.""" while True: resp = input(prompt) if resp.lower() in ['yes','y']: return True elif resp.lower() in ['no', 'n']: return False else: print('Unrecognised response, please try again.') # Code to start the game, when run as a Python main program. if __name__ == '__main__': players = get_number('How many human players', 1, 4) rounds = get_number('How many rounds ', 1, 8) robot = get_boolean('Add the computer as player? ' ) theGame = Game(players, rounds, robot) theGame.play()