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)

---

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

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

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

Othello

# 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

---