CMU 15-112: Fundamentals of Programming and Computer Science
Week5 Case Studies


Note: except for Othello (which is optional), these Case Studies may appear on midterm1, midterm2, or the final exam.

You should understand their top-down design, and be prepared to explain what each function or method does in general, and also be prepared to write any function or method from scratch.

Do not attempt to memorize this code. That is not practical and in any case not helpful. Instead, try to understand the code. You would be well-served if you wrote these from scratch, referring back to the sample solutions as needed.
  1. 21 (Blackjack)
  2. Word Search
  3. Word Search Redux
  4. Connect4
  5. Othello (optional)

  1. 21 (Blackjack)
    # twentyOne.py import random class Card(object): def __init__(self, rank, suit): self.rank = rank # from 0 to 12 self.suit = suit # from 0 to 3 def getString(self): rankString = 'A23456789TJQK'[self.rank] suitString = 'CDHS'[self.suit] return rankString + suitString class Deck(object): def __init__(self): self.cards = [ ] for suit in range(4): for rank in range(13): self.cards.append(Card(rank, suit)) random.shuffle(self.cards) def cardsLeft(self): return len(self.cards) def dealCard(self): return None if (self.cards == [ ]) else self.cards.pop() class TwentyOne(object): def play(self): self.handsWon = 0 self.handsPlayed = 0 self.deck = Deck() self.printWelcomeMessage() while True: self.playTurn() if (not self.askYesOrNo('Keep playing?')): break self.printGoodbyeMessage() def printWelcomeMessage(self): print(''' Welcome to 21! Get as close as you can to 21 without busting (going over). Aces count as 1 or 11, whichever is better. Face cards count as 10. The dealer must hit (take a card) until 16, and stay on 17 or higher. The dealer wins all ties. Good luck! ''') def printGoodbyeMessage(self): print(f'Final score: {self.handsWon} out of {self.handsPlayed} hands.') print('Goodbye!') def playTurn(self): print(f'You have won {self.handsWon} out of {self.handsPlayed} hands.') self.handsPlayed += 1 if (self.deck.cardsLeft() < 18): print('\n*** New Deck! ***\n') self.deck = Deck() playerScore = self.playPlayersHand() if (playerScore <= 21): dealerScore = self.playDealersHand() if ((dealerScore > 21) or (playerScore > dealerScore)): print('You win!') self.handsWon += 1 else: print('Dealer wins!') def getHandString(self, hand): return ', '.join([card.getString() for card in hand]) def getHandScore(self, hand): score = 0 hasAce = False for card in hand: cardScore = min(card.rank + 1, 10) if (cardScore == 1): hasAce = True score += cardScore if (score <= 11) and hasAce: score += 10 return score def playPlayersHand(self): print('Your turn!') hand = [ self.deck.dealCard() ] while True: hand += [ self.deck.dealCard() ] print(f'Your hand: {self.getHandString(hand)}') score = self.getHandScore(hand) if (score > 21): print(f'Oh no, you busted with {score}!') break if (not self.askYesOrNo('Take another card (hit)?')): break print(f'Your score: {score}') return score def playDealersHand(self): print('Dealer turn!') hand = [ self.deck.dealCard() ] while True: hand += [ self.deck.dealCard() ] print(f'Dealer hand: {self.getHandString(hand)}') score = self.getHandScore(hand) if (score > 21): print(f'Oh no, Dealer busted with {score}!') break if (score >= 17): break print(f'Dealer score: {score}') return score def askYesOrNo(self, prompt): while True: result = input(prompt + ' [y]es or [n]o --> ').lower() if (result == 'y'): return True elif (result == 'n'): return False else: print('Please enter y or n!') game = TwentyOne() game.play()

  2. Word Search
    # wordSearch1.py def wordSearch(board, word): (rows, cols) = (len(board), len(board[0])) for row in range(rows): for col in range(cols): result = wordSearchFromCell(board, word, row, col) if (result != None): return result return None def wordSearchFromCell(board, word, startRow, startCol): for drow in [-1, 0, +1]: for dcol in [-1, 0, +1]: if ((drow != 0) or (dcol != 0)): result = wordSearchFromCellInDirection(board, word, startRow, startCol, drow, dcol) if (result != None): return result return None def wordSearchFromCellInDirection(board, word, startRow, startCol, drow, dcol): (rows, cols) = (len(board), len(board[0])) dirNames = [ ["up-left" , "up", "up-right"], ["left" , "" , "right" ], ["down-left", "down", "down-right" ] ] for i in range(len(word)): row = startRow + i*drow col = startCol + i*dcol if ((row < 0) or (row >= rows) or (col < 0) or (col >= cols) or (board[row][col] != word[i])): return None return (word, (startRow, startCol), dirNames[drow+1][dcol+1]) def testWordSearch(): board = [ [ 'd', 'o', 'g' ], [ 't', 'a', 'c' ], [ 'o', 'a', 't' ], [ 'u', 'r', 'k' ], ] print(wordSearch(board, "dog")) # ('dog', (0, 0), 'right') print(wordSearch(board, "cat")) # ('cat', (1, 2), 'left') print(wordSearch(board, "tad")) # ('tad', (2, 2), 'up-left') print(wordSearch(board, "cow")) # None testWordSearch()

  3. Word Search Redux
    # wordSearch2.py # This time with a slightly different handling of directions def wordSearch(board, word): (rows, cols) = (len(board), len(board[0])) for row in range(rows): for col in range(cols): result = wordSearchFromCell(board, word, row, col) if (result != None): return result return None def wordSearchFromCell(board, word, startRow, startCol): possibleDirections = 8 # 3^2 - 1 for dir in range(possibleDirections): result = wordSearchFromCellInDirection(board, word, startRow, startCol, dir) if (result != None): return result return None def wordSearchFromCellInDirection(board, word, startRow, startCol, dir): (rows, cols) = (len(board), len(board[0])) dirs = [ (-1, -1), (-1, 0), (-1, +1), ( 0, -1), ( 0, +1), (+1, -1), (+1, 0), (+1, +1) ] dirNames = [ "up-left" , "up", "up-right", "left" , "right", "down-left", "down", "down-right" ] (drow,dcol) = dirs[dir] for i in range(len(word)): row = startRow + i*drow col = startCol + i*dcol if ((row < 0) or (row >= rows) or (col < 0) or (col >= cols) or (board[row][col] != word[i])): return None return (word, (startRow, startCol), dirNames[dir]) def testWordSearch(): board = [ [ 'd', 'o', 'g' ], [ 't', 'a', 'c' ], [ 'o', 'a', 't' ], [ 'u', 'r', 'k' ], ] print(wordSearch(board, "dog")) # ('dog', (0, 0), 'right') print(wordSearch(board, "cat")) # ('cat', (1, 2), 'left') print(wordSearch(board, "tad")) # ('tad', (2, 2), 'up-left') print(wordSearch(board, "cow")) # None testWordSearch()

  4. Connect4
    # connect4.py # A simple game of connect4 with a text interface # based on the wordSearch code written in class. def playConnect4(): rows = 6 cols = 7 board = makeBoard(rows, cols) player = "X" moveCount = 0 printBoard(board) while (moveCount < rows*cols): moveCol = getMoveCol(board, player) moveRow = getMoveRow(board, moveCol) board[moveRow][moveCol] = player printBoard(board) if checkForWin(board, player): print("*** Player %s Wins!!! ***" % player) return moveCount += 1 player = "O" if (player == "X") else "X" print("*** Tie Game!!! ***") def makeBoard(rows, cols): return [ (["-"] * cols) for row in range(rows) ] def printBoard(board): rows = len(board) cols = len(board[0]) print() # first print the column headers print(" ", end="") for col in range(cols): print(str(col+1).center(3), " ", end="") print() # now print the board for row in range(rows): print(" ", end="") for col in range(cols): print(board[row][col].center(3), " ", end="") print() def getMoveCol(board, player): cols = len(board[0]) while True: response = input("Enter player %s's move (column number) --> " % (player)) try: moveCol = int(response)-1 # -1 since user sees cols starting at 1 if ((moveCol < 0) or (moveCol >= cols)): print("Columns must be between 1 and %d. " % (cols), end="") elif (board[0][moveCol] != "-"): print("That column is full! ", end="") else: return moveCol except: # they did not even enter an integer! print("Columns must be integer values! ", end="") print("Please try again.") def getMoveRow(board, moveCol): # find first open row from bottom rows = len(board) for moveRow in range(rows-1, -1, -1): if (board[moveRow][moveCol] == "-"): return moveRow # should never get here! assert(False) def checkForWin(board, player): winningWord = player * 4 return (wordSearch(board, winningWord) != None) # that was easy! ############################################## # taken from wordSearch.py ############################################## def wordSearch(board, word): (rows, cols) = (len(board), len(board[0])) for row in range(rows): for col in range(cols): result = wordSearchFromCell(board, word, row, col) if (result != None): return result return None def wordSearchFromCell(board, word, startRow, startCol): for drow in [-1, 0, +1]: for dcol in [-1, 0, +1]: if ((drow != 0) or (dcol != 0)): result = wordSearchFromCellInDirection(board, word, startRow, startCol, drow, dcol) if (result != None): return result return None def wordSearchFromCellInDirection(board, word, startRow, startCol, drow, dcol): (rows, cols) = (len(board), len(board[0])) dirNames = [ ["up-left" , "up", "up-right"], ["left" , "" , "right" ], ["down-left", "down", "down-right" ] ] for i in range(len(word)): row = startRow + i*drow col = startCol + i*dcol if ((row < 0) or (row >= rows) or (col < 0) or (col >= cols) or (board[row][col] != word[i])): return None return (word, (startRow, startCol), dirNames[drow+1][dcol+1]) playConnect4()

  5. Othello
    # othello.py def make2dList(rows, cols): a=[] for row in range(rows): a += [[0]*cols] return a def hasMove(board, player): (rows, cols) = (len(board), len(board[0])) for row in range(rows): for col in range(cols): if (hasMoveFromCell(board, player, row, col)): return True return False def hasMoveFromCell(board, player, startRow, startCol): (rows, cols) = (len(board), len(board[0])) if (board[startRow][startCol] != 0): return False for dir in range(8): if (hasMoveFromCellInDirection(board, player, startRow, startCol, dir)): return True return False def hasMoveFromCellInDirection(board, player, startRow, startCol, dir): (rows, cols) = (len(board), len(board[0])) dirs = [ (-1, -1), (-1, 0), (-1, +1), ( 0, -1), ( 0, +1), (+1, -1), (+1, 0), (+1, +1) ] (drow,dcol) = dirs[dir] i = 1 while True: row = startRow + i*drow col = startCol + i*dcol if ((row < 0) or (row >= rows) or (col < 0) or (col >= cols)): return False elif (board[row][col] == 0): # no blanks allowed in a sandwich! return False elif (board[row][col] == player): # we found the other side of the 'sandwich' break else: # we found more 'meat' in the sandwich i += 1 return (i > 1) def makeMove(board, player, startRow, startCol): # assumes the player has a legal move from this cell (rows, cols) = (len(board), len(board[0])) for dir in range(8): if (hasMoveFromCellInDirection(board, player, startRow, startCol, dir)): makeMoveInDirection(board, player, startRow, startCol, dir) board[startRow][startCol] = player def makeMoveInDirection(board, player, startRow, startCol, dir): (rows, cols) = (len(board), len(board[0])) dirs = [ (-1, -1), (-1, 0), (-1, +1), ( 0, -1), ( 0, +1), (+1, -1), (+1, 0), (+1, +1) ] (drow,dcol) = dirs[dir] i = 1 while True: row = startRow + i*drow col = startCol + i*dcol if (board[row][col] == player): # we found the other side of the 'sandwich' break else: # we found more 'meat' in the sandwich, so flip it! board[row][col] = player i += 1 def getPlayerLabel(player): labels = ["-", "X", "O"] return labels[player] def printColLabels(board): (rows, cols) = (len(board), len(board[0])) print(" ", end="") # skip row label for col in range(cols): print(chr(ord("A")+col)," ", end="") print() def printBoard(board): (rows, cols) = (len(board), len(board[0])) printColLabels(board) for row in range(rows): print("%2d " % (row+1), end="") for col in range(cols): print(getPlayerLabel(board[row][col]), " ", end="") print("%2d " % (row+1)) printColLabels(board) def isLegalMove(board, player, row, col): (rows, cols) = (len(board), len(board[0])) if ((row < 0) or (row >= rows) or (col < 0) or (col >= cols)): return False return hasMoveFromCell(board, player, row, col) def getMove(board, player): print("\n**************************") printBoard(board) while True: prompt = "Enter move for player " + getPlayerLabel(player) + ": " move = input(prompt).upper() # move is something like "A3" if ((len(move) != 2) or (not move[0].isalpha()) or (not move[1].isdigit())): print("Wrong format! Enter something like A3 or D5.") else: col = ord(move[0]) - ord('A') row = int(move[1])-1 if (not isLegalMove(board, player, row, col)): print("That is not a legal move! Try again.") else: return (row, col) def playOthello(rows, cols): # create initial board board = make2dList(rows, cols) board[rows//2][cols//2] = board[rows//2-1][cols//2-1] = 1 board[rows//2-1][cols//2] = board[rows//2][cols//2-1] = 2 (currentPlayer, otherPlayer) = (1, 2) # and play until the game is over while True: if (hasMove(board, currentPlayer) == False): if (hasMove(board, otherPlayer)): print("No legal move! PASS!") (currentPlayer, otherPlayer) = (otherPlayer, currentPlayer) else: print("No more legal moves for either player! Game over!") break (row, col) = getMove(board, currentPlayer) makeMove(board, currentPlayer, row, col) (currentPlayer, otherPlayer) = (otherPlayer, currentPlayer) print("Goodbye!") playOthello(8,8)