15-112 - Summer 1

Content

2d lists worked examples

Word Search
Word Search Redux
Connect 4
Othello (optional)

Intro to Efficiency

Big-Oh
Common Function Families
Efficiency
The Big Idea
Sequences, Nesting, and Composition

2d lists worked examples

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 dir in range(8):
        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()

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):
    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. Connect 4

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

4. Othello (optional)

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

Into to efficiency

1. Big-Oh

Describes asymptotic behavior of a function
Informally (for 15112): ignore all lower-order terms and constants
Formally (after 15112): see here
A few examples:
- 3n² - 2n + 25 is O(n²)
- 30000n² + 2n - 25 is O(n²)
- 0.00000000001n² + 123456789n is O(n²)
- 10nlog₁₇n + 25n - 17 is O(nlogn)

2. Common Function Families

Constant O(1)
Logarithmic O(logn)
Square-Root O(n^0.5)
Linear O(n)
Linearithmic, Loglinear, or quasilinear O(nlogn)
Quadratic O(n²)
Exponential O(kⁿ)

Graphically (Images borrowed from here):

3. Efficiency

When we say the program runs in O(f(N)), we mean...

N is the size of our input
- For a string s, N = len(s)
- For a list L, N = len(L) (also true for sets, dictionaries, and other collections)
- For an integer n, N = numberOfDigits(n) = log_b(n), so n = b^N (where b is the base, and you can use any base b >= 2).
- In the literature, N is often written in lowercase n, but we use that often to represent an integer n, which is different from the size of that integer. So in 112, we use uppercase N for the size of the input.
f(N) = resource consumption of our program
- Resource can be time, space, bandwidth, ...
- For 15112, we mainly care about time
For time, we usually measure algorithmic steps rather than elapsed time (These share the same big-oh, but algorithmic steps are easier to precisely describe and reason over)
Note that you can measure worst-case or average case, or even other cases such as best case (which often is trivial to compute and not very useful in practice). For 15-112, we often omit this term (which is a notable simplification that you will not see in future courses), and we nearly always mean worst-case, which is quite useful and generally easier to compute than average-case.
- Count steps in a written algorithm, or comparisons and swaps in a list, etc
- Can verify by timing your code's execution with: time.time()

4. The Big Idea

Each function family grows much faster than the one before it!
And: on modern computers, any function family is usually efficient enough on small n, so we only care about large n
So... Constants do not matter nearly as much as function families
Practically...
- Do not prematurely or overly optimize your code
- Instead: think algorithmically!!!

5. Sequences, Nesting, and Composition

Sequences

# what is the total cost here?
a = [ 52, 83, 78, 9, 12, 4 ]   # assume L is an arbitrary list of length N 
L = copy.copy(a)               # This is O(N)
L[0] -= 5                      # This is O(1)
print(b.count(b[0]) + sum(L))  # This is O(N) + O(N)

Nesting

# what is the total cost here?
L = [ 52, 83, 78, 9, 12, 4 ]   # assume L is an arbitrary list of length N
maxSum = 0
for c in L:                    # This loop's body is executed O(N) times
    L[0] += c                  # This is O(1)
    maxSum += max(L)           # This is O(N) (why?)
print(maxSum)                  # This is O(1)

Composition

# what is the total cost here?
def f(L):             # assume L is an arbitrary list of length N
    return max(L)     # This is O(N)

def g(L):             # assume L is an arbitrary list of length N
    L1 = L * len(L)   # This is O(N**2) (why?)
    return L1         # This is O(1)

L = [ 52, 83, 78, 9, 12, 4 ]   # assume L is an arbitrary list of length N
result = f(g(L))               # What is the big-oh of this?

15-112 Fundamentals of Programming

Notes - Lecture 3.2

Content

2d lists worked examples

1. Word Search

2. Word Search Redux

3. Connect 4

4. Othello (optional)

Into to efficiency

1. Big-Oh

2. Common Function Families

3. Efficiency

4. The Big Idea

5. Sequences, Nesting, and Composition

Sequences

Nesting

Composition