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

1. Word Search
2. Word Search Redux
3. Connect4
4. Othello (optional)

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)