Week 15

More Review

Author:Christopher Haynes
Email:chaynes@indiana.edu
Affiliation:Indiana University
Course:BL CSCI A201
Date:2008-04-24
Copyright © 2008, Christopher Haynes—all rights reserved.

Practical Exam

Final Exam

Office hours

General loop design guidelines

return statement (from week 5)

Sharing Demo

>>> lst1 = [3]
>>> lst2 = lst1
>>> lst2
[3]
>>> lst1.append(5)
>>> lst1
[3, 5]
>>> lst2
[3, 5]
>>> lst3 = [0] * 3
>>> lst3
[0, 0, 0]
>>> lst3[1] += 1
>>> lst3
[0, 1, 0]
>>> lst4 = [[]] * 3
>>> lst4
[[], [], []]
>>> lst4[1].append(3)
>>> lst4
[[3], [3], [3]]

Sharing Concept

Example: bad_swap

def bad_swap(var1, var2):
    """Swap the contents of var1 and var2.
    >>> x = 1
    >>> y = 2
    >>> bad_swap(x, y)
    >>> x # NOT 2 as intended
    1
    >>> y # NOT 1 as intended
    2
    >>>
    """
    temp = var1
    var1 = var2
    var2 = temp

Exercise: swap

def swap(lst, index1, index2):
    """Modify lst by swapping the contents of the elements with the
    given indices.
    >>> lst = [1, 2, 3]
    >>> swap(lst, 0, 2)
    >>> lst
    [3, 2, 1]
    >>>
    """
    #.
    #.
    #.

Solution: swap

def swap(lst, index1, index2):
    """Modify lst by swapping the contents of the elements with the
    given indices.
    >>> lst = [1, 2, 3]
    >>> swap(lst, 0, 2)
    >>> lst
    [3, 2, 1]
    >>>
    """
    temp = lst[index1]
    lst[index1] = lst[index2]
    lst[index2] = temp

Exercise: swap_rows

def swap_rows(table, row_index1, row_index2):
    """Return a new table that is similar to the given table, but
    with the rows indicated by the two given indices exchanged.
    >>> table = [[1], [2], [3]]
    >>> swap_rows(table, 0, 2)
    [[3], [2], [1]]
    >>> table
    [[1], [2], [3]]
    >>>
    """
    #.
    #.
    #.
    #.
    #.

Solution: swap_rows

def swap_rows(table, row_index1, row_index2):
    """Return a new table that is similar to the given table, but
    with the rows indicated by the two given indices exchanged.
    >>> table = [[1], [2], [3]]
    >>> swap_rows(table, 0, 2)
    [[3], [2], [1]]
    >>> table
    [[1], [2], [3]]
    >>>
    """
    table = table[:]
    row1 = table[row_index1]
    table[row_index1] = table[row_index2]
    table[row_index2] = row1
    return table

Example: swap_rows2

def swap_rows2(table, row_index1, row_index2):
    """Return a new table that is similar to the given table, but
    with the rows indicated by the two given indices exchanged.
    >>> table = [[1], [2], [3]]
    >>> swap_rows2(table, 0, 2)
    [[3], [2], [1]]
    >>> table
    [[1], [2], [3]]
    >>>
    """
    table = table[:]
    swap(table, row_index1, row_index2)
    return table

Exercise: swap_columns

def swap_columns(table, column_index1, column_index2):
    """Return a new table that is similar to the given table, but
    with the columns indicated by the two given indices exchanged.
    >>> table = [[1,2,3], [3,4,5]]
    >>> swap_columns(table, 0, 2)
    [[3, 2, 1], [5, 4, 3]]
    >>> table
    [[1, 2, 3], [3, 4, 5]]
    >>>
    """
    #.
    #.
    #.
    #.
    #.
    #.

Solution: swap_columns

def swap_columns(table, column_index1, column_index2):
    """Return a new table that is similar to the given table, but
    with the columns indicated by the two given indices exchanged.
    >>> table = [[1,2,3], [3,4,5]]
    >>> swap_columns(table, 0, 2)
    [[3, 2, 1], [5, 4, 3]]
    >>> table
    [[1, 2, 3], [3, 4, 5]]
    >>>
    """
    answer = table[:]
    for row_index in range(len(table)):
        row = answer[row_index][:]
        swap(row, column_index1, column_index2)
        answer[row_index] = row
    return answer

clicker What does mystery1() return?

def mystery1():
    answer = 0
    for n in range(3):
        if n == 0:
           return answer
        else:
           answer = answer + n
    return answer
  1. 0
  2. 1
  3. 2
  4. 3
  5. None
  6. Nothing, an error is raised

Answer: A

clicker What does mystery2() return?

def mystery2():
    answer = 0
    for n in range(3):
        answer = answer + n
  1. 0
  2. 1
  3. 2
  4. 3
  5. None
  6. Nothing, an error is raised

Answer: E

clicker What does mystery3([1, 2]) return?

def mystery3(lst):
    for index in range(len(lst)):
        answer.append(lst[index] + 1)
    return answer
  1. []
  2. [1, 2]
  3. [2, 3]
  4. 3
  5. None
  6. Nothing, an error is raised

Answer: F

clicker What numbers does mystery4([1, 2]) print?

def mystery4(lst):
    answer = 0
    print answer
    for index in range(len(lst)):
        print answer
        answer = answer + 1
    return answer
  1. 0 1
  2. 0 0 1
  3. 0 1 2
  4. 0 0 1 3
  5. 0 None
  6. Nothing, an error is raised

Answer: B

Exercise: lookup

def lookup(alst, key):
    """alst is an "association list" of two-element lists of the form
    [key, value]. Returns the first value associated (in the same pair)
    with the given key. Returns None if there is no such value.
    >>> lookup([['John', 3], ['Jim', 4]], 'Jim')
    4
    >>> lookup([['John', 3], ['Jim', 4]], 'Jane')
    >>> # None returned
    """
    #.
    #.
    #.
    #.
    #.

Solution: lookup

def lookup(alst, key):
    """alst is an "association list" of two-element lists of the form
    [key, value]. Returns the first value associated (in the same pair)
    with the given key. Returns None if there is no such value.
    >>> lookup([['John', 3], ['Jim', 4]], 'Jim')
    4
    >>> lookup([['John', 3], ['Jim', 4]], 'Jane')
    >>> # None returned
    """
    for index in range(len(alst)):
        pair = alst[index]
        if pair[0] == key:
            return pair[1]
    return None

Exercise: split

def split(s1, s2):
    """Return a list of strings that are the slices of s1 separated by the
    string s2. Same as s1.split(s2).

    >>> split('space separated words', ' ')
    ['space', 'separated', 'words']
    >>>
    >>> split('long-dash--separated--words', '--')
    ['long-dash', 'separated', 'words']
    >>>
    """
    #.
    #.
    #.
    #.
    #.
    #.
    #.
    #.
    #.

Solution: split

def split(s1, s2):
    """Return a list of strings that are the slices of s1 separated by the
    string s2. Same as s1.split(s2).

    >>> split('space separated words', ' ')
    ['space', 'separated', 'words']
    >>>
    >>> split('long-dash--separated--words', '--')
    ['long-dash', 'separated', 'words']
    >>>
    """
    index = 0
    answer = []
    while index < len(s1):
        next_index = s1.find(s2, index)
        if next_index == -1:
            next_index = len(s1)
        answer.append(s1[index : next_index])
        index = next_index + len(s2)
    return answer

clicker Which of the following is a method call?

  1. append(lst, value)
  2. lst.append(value)
  3. math.sqrt(value)
  4. A and B

Answer: B

clicker What is a true value in Python?

  1. True
  2. True or False
  3. any value at all
  4. any value except False, None, numeric zeros, empty data sequences, and empty dictionaries

Answer: D

clicker Which of the following prints [1, 1, 1] ?

  1. print [1] * 3
  2. print [(1)] * 3
  3. print (1) * 3
  4. print '[1]' * 3
  5. A or B
  6. B or C

Answer: E

Watch your types!

Types

Types exercise

Answer: differences types

Types in a parse tree

len(lst) - 1
FUN LIST  INT
--INT---
-----INT-----

is a compact way to display the type information (upper case) to expressions in the parse tree:

expression -> expression binary_operation expression
    expression -> function_call INT
       function_call -> function_expression ( argument_expression,...,argument_expression )
                     -> function_expression ( argument_expression ) INT
           function_expression -> variable_name FUN
               variable_name -> len FUN
           argument_expression -> variable_name LIST
               variable_name -> lst LIST
   binary_operation -> -
   expression -> literal INT
        literal -> integer INT
             integer -> 1 INT

dot_product types exercise

Answer: dot_product types

answer = 0
NUMBER   INT
for index in range(len(vector1)):
    INT            FUN LIST
                   ---INT------
    answer = answer + vector1[index] * vector2[index]
    NUMBER   NUMBER    LIST    INT      LIST     INT
                      ---NUMBER-----   ----NUMBER----
                      -------------NUMBER------------
             ------------NUMBER----------------------
return answer
       NUMBER

Example of for loop translation to while loop

Consider:

def flatten(matrix):
    """Return a flat (non-nested) list of the values in matrix in row order.

    >>> flatten([[1,2], [3,4]])
    [1, 2, 3, 4]
    >>>
    """
    answer = []
    for index in range(len(matrix)):
        row = matrix[index]
        answer = answer + row
    return answer

The for loop above is equivalent (except for the value of index after the loop) to:

index = 0
while index < len(matrix): # in place of for loop
    row = matrix[index]
    answer = answer + row
    index = index + 1 # hidden

Exercise: csv_reader

def csv_reader(infile):
    """Reads a comma separated file using the file object infile and
    returns the file contents represented as a table (a list of row lists).

    It is assumed that all commas in the file are column separators, in which
    case csv_reader(infile) is the same as list(csv.reader(infile)).

    >>> print file('addresses.csv', 'r').read()
    First Name,Last Name,Street,City,State,Zip
    Sally,Porter,4324 Hedrick Ln,Jersy City,NJ,23403
    Sam,Proxmire,125 Hampton Cr,Jefferson,NY,32084
    Sue,Pinter,32 Hawthorn Dr,Jackson,MS,13034
    <BLANKLINE>
    >>> infile = file('addresses.csv', 'r')
    >>> pprint.pprint(csv_reader(infile))
    [['First Name', 'Last Name', 'Street', 'City', 'State', 'Zip'],
     ['Sally', 'Porter', '4324 Hedrick Ln', 'Jersy City', 'NJ', '23403'],
     ['Sam', 'Proxmire', '125 Hampton Cr', 'Jefferson', 'NY', '32084'],
     ['Sue', 'Pinter', '32 Hawthorn Dr', 'Jackson', 'MS', '13034']]
    >>>
    """
    #.
    #.
    #.
    #.
    #.
    #.
    #.

Solution: csv_reader

def csv_reader(infile):
    """Reads a comma separated file using the file object infile and
    returns the file contents represented as a table (a list of row lists).

    It is assumed that all commas in the file are column separators, in which
    case csv_reader(infile) is the same as list(csv.reader(infile)).

    >>> print file('addresses.csv', 'r').read()
    First Name,Last Name,Street,City,State,Zip
    Sally,Porter,4324 Hedrick Ln,Jersy City,NJ,23403
    Sam,Proxmire,125 Hampton Cr,Jefferson,NY,32084
    Sue,Pinter,32 Hawthorn Dr,Jackson,MS,13034
    <BLANKLINE>
    >>> infile = file('addresses.csv', 'r')
    >>> pprint.pprint(csv_reader(infile))
    [['First Name', 'Last Name', 'Street', 'City', 'State', 'Zip'],
     ['Sally', 'Porter', '4324 Hedrick Ln', 'Jersy City', 'NJ', '23403'],
     ['Sam', 'Proxmire', '125 Hampton Cr', 'Jefferson', 'NY', '32084'],
     ['Sue', 'Pinter', '32 Hawthorn Dr', 'Jackson', 'MS', '13034']]
    >>>
    """
    answer = []
    while True:
        line = infile.readline()
        if line == '':
            return answer
        line = line[0 : len(line) - 1] # remove newline at end of line
        answer.append(line.split(','))

Programming language semantics

Exercise: syntax and semantics of selected elements of Python

Being as precise as you can, write the general syntax (look it up on the syntax summary if you need to) of the following elements of Python, along with a complete description of the associated semantics (what it does).

  1. expression involving a binary operator (excluding and and or)
  2. if/else statement (assume else clause is there, and no elif clauses)
  3. while statement
  4. for loop

Craps

Craps is a game played by 1 or more players. Players take turns rolling two dice. The player rolling the dice is called the shooter. The game is played in rounds, with the first roll of a new round called the come-out roll.

On the come-out roll, if the total of the two dice is 7, 11, 2, 3 or 12, the round ends immediately and the shooter must roll another come-out roll. A result of 2, 3 or 12 is called craps while a result of 7 or 11 is called a win (or a "natural"). When any other number (4, 5, 6, 8, 9, or 10) is rolled on the come-out roll, this number becomes what is called the point. If a point is established then the shooter will re-roll the dice continuously until either a 7 is rolled, or the point is rolled again. If the shooter rolls the point again, the round ends and the game starts over with the same shooter rolling another come-out roll. If the shooter rolls a 7 instead of the point, this is called a seven-out, the round ends, and the dice pass to the next player to the left, who becomes the new shooter.

-- The first two paragraphs in "The rules of play" section of the Wikipedia Craps article.

Exercise: throw

def throw():
    """Simulates the random throw of two dice and returns their sum.
    """
    # Hint: use random.randrange(n), which returns an integer
    # from 0 through n-1.
    #.

Solution: throw

def throw():
    """Simulates the random throw of two dice and returns their sum.
    """
    # Hint: use random.randrange(n), which returns an integer
    # from 0 through n-1.
    return random.randrange(6) + random.randrange(6) + 2

Exercise: craps_turn

def craps_turn():
    """Simulates a players turn in a craps game, returning a list that starts with
    the string 'craps', 'win', or 'seven-out', indicating the outcome of the turn.
    The rest of the list values are numbers indicating, in temporal order, the
    value of each throw in the turn.
    >>> craps_turn()
    ['seven-out', 9, 10, 5, 11, 6, 10, 4, 7]
    >>>
    """
    #.
    #.
    #.
    #.
    #.
    #.
    #.
    #.
    #.
    #.
    #.
    #.
    #.
    #.

Solution: craps_turn

def craps_turn():
    """Simulates a players turn in a craps game, returning a list that starts with
    the string 'craps', 'win', or 'seven-out', indicating the outcome of the turn.
    The rest of the list values are numbers indicating, in temporal order, the
    value of each throw in the turn.
    >>> craps_turn()
    ['seven-out', 9, 10, 5, 11, 6, 10, 4, 7]
    >>>
    """
    throws = []
    while True:
        point = throw()
        throws.append(point)
        if point in [2, 3, 12]:
            return ['craps'] + throws
        elif point in [7, 11]:
            return ['win'] + throws
        while True:
            throws.append(throw())
            if throws[-1] == 7:
                return ['seven-out'] + throws
            elif throws[-1] == point:
                break

Exercise: play_craps

def play_craps():
    """Repeatedly call turn() and print the result it returns.
    Quit after all three possible round outcomes have occurred.

    >>> play_craps()
    ['craps', 8, 8, 3]
    ['seven-out', 6, 9, 3, 5, 7]
    ['seven-out', 9, 6, 6, 3, 4, 4, 9, 4, 4, 9, 4, 7]
    ['craps', 3]
    ['seven-out', 10, 7]
    ['win', 6, 6, 9, 6, 5, 8, 6, 5, 9, 11]
    >>>
    """
    #.
    #.
    #.
    #.
    #.
    #.
    #.

Solution: play_craps

def play_craps():
    """Repeatedly call turn() and print the result it returns.
    Quit after all three possible round outcomes have occurred.

    >>> play_craps()
    ['craps', 8, 8, 3]
    ['seven-out', 6, 9, 3, 5, 7]
    ['seven-out', 9, 6, 6, 3, 4, 4, 9, 4, 4, 9, 4, 7]
    ['craps', 3]
    ['seven-out', 10, 7]
    ['win', 6, 6, 9, 6, 5, 8, 6, 5, 9, 11]
    >>>
    """
    outcomes = []
    while len(outcomes) < 3:
        result = craps_turn()
        print result
        outcome = result[0]
        if not outcome in outcomes:
            outcomes.append(outcome)

The rest is for your information only

The rest of these notes demonstrate how image processing may be done in Python. You may learn better how to do matrix manipulation by studying this, but you are not responsible in this course for the specifics of images processing.

Tuples

Digital images

Pixel Colors

Python image processing

image.py module

>>> import image
>>> help(image)
Help on module image:

NAME
    image - image.py, by chaynes@indiana.edu

FILE
    c:\home\201\c\12\image.py

DESCRIPTION
    A PIL.Image module wrapper for CSCI A201.

FUNCTIONS
    new(matrix)
        Return an image object made from the (r,g,b) pixel tuples in matrix.
        Two image object methods:
            show() displays the image in a window
            save(str) saves the image in a jpeg file named by the string

    read(file_name)
        Read an image from the named file and return it as a matrix of (r,g,b)
        pixel tuples, or raise 'Bad image type' if it is not a suitable image type.
        JPEG is a suitable type, while GIF and PNG are not.

Color patch: color_patch.py

""" #..d
>>> from color_patch import *
>>>
"""

import image, pprint

def color_patch(pixel, width, height):
    """Returns an image matrix of the indicated width and height in which all
    pixels are of the same color, indicated by the given rgb pixel.
    >>> m = color_patch((0, 255, 0), 2, 3)
    >>> pprint.pprint(m)
    [[(0, 255, 0), (0, 255, 0)],
     [(0, 255, 0), (0, 255, 0)],
     [(0, 255, 0), (0, 255, 0)]]
    >>>
    """
    matrix = []
    for y in range(height):
        row = []
        for x in range(width):
            row.append(pixel)
        matrix.append(row)
    return matrix

def main():
    dark_blue = (0, 0, 100)
    m = color_patch(dark_blue, 200, 100)
    im = image.new(m)
    im.show()

if __name__ == '__main__':
    main()

Red color spectrum: red_color_spectrum.py

import image
import sys

sys.argv = ['_', '100']

def red_color_spectrum(red):
    """Returns a 256 by 256 image matrix with pixels representing all possible
    24-bit rgb colors (8 bits each for r, g, and b) with the indicated amount of
    red (0 to 255).
    """
    matrix = []
    for y in range(256):
        row = []
        for x in range(256):
            pixel = (red, x, y)
            row.append(pixel)
        matrix.append(row)
    return matrix

def main():
    red = int(sys.argv[1])
    m = red_color_spectrum(red)
    im = image.new(m)
    im.show()

if __name__ == '__main__':
    main()

Negative images: negative.py

# negative.py, by chaynes@indiana.edu

import image

def negative_image(matrix):
    """Return a new matrix that is the negative image of the given matrix."""
    answer = []
    for i in range(len(matrix)):
        row = []
        answer.append(row)
        for j in range(len(matrix[0])):
            pixel = matrix[i][j]
            new_pixel = negative_pixel(pixel)
            row.append(new_pixel)
    return answer

def negative_pixel(pixel):
    red = pixel[0]
    green = pixel[1]
    blue = pixel[2]
    return (255 - red, 255 - green, 255 - blue)

def main():
    """Show a negative image of the  bonsai picture."""
    m = image.read('bonsai.jpg')
    image.new(m).show()
    im = image.new(negative_image(m))
    im.show()

if __name__ == '__main__':
    main()

Mirror images: mirror.py

# mirror.py, by chaynes@indiana.edu

import image

def mirror(lst):
    """Copy the values in elements in the first half of lst into elements in the
    second half of lst, in reverse order.
    """
    for i in range(len(lst) / 2):
        lst[len(lst) - 1 - i] = lst[i]

def mirror_matrix(matrix):
    """Call the mirror function on each row of matrix."""
    for index in range(len(matrix)):
        row = matrix[index]
        mirror(row)

def main():
    """Show bonsai.jpg, and then show and save its mirror image."""
    m = image.read('bonsai.jpg')
    mirror_matrix(m)
    im = image.new(m)
    im.show()
    im.save('mirror.jpg')

if __name__ == '__main__':
    main()

Scalling images: scale.py

# scale.py, by chaynes@indiana.edu

import image
    
def scale_length(lst, length):
    """Return a horizontally-scaled version of a list,
    stretched or compressed to be of the given length.

    >>> scaleLength([0, 1, 2], 6)
    [0, 0, 1, 1, 2, 2]
    >>> scaleLength([0, 1, 2, 3, 4, 5], 3)
    [0, 2, 4]
    >>>
    """
    answer = []
    for i in range(length):
        answer.append(lst[i * len(lst) / length])
    return answer

def scale_matrix_width(matrix, width):
    """Return matrix obtained from the given matrix by scaling each row
    to the given width.
    """
    answer = []
    for index in range(len(matrix)):
        row = matrix[index]
        answer.append(scale_length(row, width))
    return answer

def main():
    """Show bonsai.jpg with normal, expanded and compressed width."""
    m = image.read('bonsai.jpg')
    width = len(m[0])
    narrow = scale_matrix_width(m, width / 2)
    image.new(narrow).show()
    wide = scale_matrix_width(narrow, width * 2)
    image.new(wide).show()
    
if __name__ == '__main__':
    main()

clicker If m is an image matrix, which of the following returns the pixel at coordinate (x,y)?

Assume m was returned by the get method of the image.py module used in the current assignment.

  1. m[x,y]
  2. m[y,x]
  3. m[x][y]
  4. m[y][x]
  5. m.get_pixel(x,y)
  6. m.get_pixel((x,y))

Answer: D