# CMU 15-112: Fundamentals of Programming and Computer Science 2d List Case Studies

Note: except for Othello (which is optional), these Case Studies may appear on quizzes, midterms, 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. 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, dcol) != (0, 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()

2. 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()

3. 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(f'*** Player {player} Wins!!! ***') 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(f"Enter player {player}'s move (column number) --> ") try: moveCol = int(response)-1 # -1 since user sees cols starting at 1 if ((moveCol < 0) or (moveCol >= cols)): print(f'Columns must be between 1 and {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, dcol) != (0, 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()

4. Othello (optional)
# othello.py # this is optional but interesting! 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(f'{row+1:2} ', end='') for col in range(cols): print(getPlayerLabel(board[row][col]), ' ', end='') print(f'{row+1:2}') 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)