Lab 15: Review

Table of Contents

Deadline

This lab is due by 10:59am on 8/14/2014.

NOTE WELL: THE ONLY THINGS THAT ARE WORTH CREDIT ON THIS LAB ARE QUESTIONS 1 AND 2. QUESTION 2 HAS A DIFFERENT DEADLINE.

We have provided the following starter files: lab15.py, lab15.scm, lab15.logic

Recursive Art Contest

Question 1

Vote for your favorite submissions in the recursive art contest.

Final Survey

Question 2

Take the final survey. This is a long survey, so take it when you have some free time. This part of the lab will be due Friday August 15 at 11:59pm.

Today's Lab

The rest of today's lab consists of a bunch of practice problems for the final. Do whichever ones you want - we will not be grading you on them.

Reverse Everything

Question 3

Write a function reverse that takes a list and returns the reverse. Write both an iterative and a recursive version. You may use slicing notation, but don't use list[::-1].

def reverse_iter(lst):
    """Returns the reverse of the given list.

    >>> reverse_iter([1, 2, 3, 4])
    [4, 3, 2, 1]
    """
    "*** YOUR CODE HERE ***"

def reverse_recursive(lst):
    """Returns the reverse of the given list.

    >>> reverse_recursive([1, 2, 3, 4])
    [4, 3, 2, 1]
    """
    "*** YOUR CODE HERE ***"
def reverse_iter(lst):
    new, i = (), 0
    while i < len(lst):
        new = (lst[i],) + new
        i += 1
    return new

def reverse_recursive(lst):
    if not lst:
        return []
    return reverse_recursive(lst[1:]) + (lst[0],)

Question 4

Write reverse in Scheme. Do this recursively without writing a helper function.
(define (reverse lst)
  'YOUR-CODE-HERE)
(define (reverse lst)
  (if (null? lst)
      lst
      (append (reverse (cdr lst)) (list (car lst)))))

Question 5

Write a tail-recursive function reverse-iter that takes in a Scheme list and returns a reversed copy. Hint: use a helper function!

(define (reverse-iter lst)
  'YOUR-CODE-HERE)
(define (reverse-iter lst)
  (define (reverse-iter sofar rest)
    (if (null? rest)
	sofar
	(reverse-iter (cons (car rest) sofar) (cdr rest))))
  (reverse-iter nil lst))

Question 6

Now write a fact for reverse in Logic:

; YOUR CODE HERE

(query (reverse (1 2 3) ?what))
; expect Success! ; what: (3 2 1)

Object Oriented Programming

Question 7

Figure out what Python would output before trying it in the interpreter. If it will error, name the type of error.

class Horse:
    breathes = "air"
    def __init__(self, color):
        self.color = color
        self.cry = "neigh"
    def call(self):
        return self.call

class Seahorse(Horse):
    def __init__(self, color):
        Horse.__init__(self, 'purple')
        self.breathes = "water"
        self.cry = "glub"
    def change_color(self, who):
        who.color, self.color = self.color, who.color
>>> marvin = Horse('brown')
>>> marvin.cry = "I'm Marvin the tap-dancing horse."
>>> applejack = Horse('orange')
>>> applejack.cry
______
>>> seahorse = Seahorse('teal')
>>> seahorse.color
______
>>> seahorse.change_color(self)
______
>>> Seahorse.change_color(seahorse, marvin)
>>> marvin.color+seahorse.call
______
>>> Seahorse.breathes
______

Iterators and Generators

Question 8

Write an iterator that generates perfect squares up to the greatest integer less than or equal to n.
class SquaresIterator:
    """
    >>> for ps in SquaresIterator(7.3):
    ...     print(ps)
    ...
    1
    4
    9
    16
    25
    36
    49
    """
    def __init__(self, n):
        "*** YOUR CODE HERE ***"

    def __next__(self):
        "*** YOUR CODE HERE ***"

    def __iter__(self):
        "*** YOUR CODE HERE ***"
    def __init__(self, n):
        self.start = 1
        self.stop = n//1

    def __next__(self):
        if self.start > self.stop:
            raise StopIteration
        self.start += 1
        return (self.start - 1)**2

    def __iter__(self):
        return self

Question 9

Write a generator that outputs each character of a string.

def char_gen(str):
    """
    >>> for char in char_gen("hello"):
    ...     print(char)
    ...
    h
    e
    l
    l
    o
    """
    i = 0
    while i &lt len(str):
        yield str[i]
        i += 1