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

   Select Run


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

   Select Run


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

   Select


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)

   Select

---