CS61A casual notes

Welcome&Function

loop for in python, do not forget to add range .

for i in range(a,b): #a included, b excluded (actually [a,b+1])

reverse string:

[::-1]

Control&Higher order function

to check a function’s docstring:

help(func)

and type q to exit.

lambda expression:

[expression name]=lambda [parameters]:[value] 

In python, functions can also be parameters of other functions.

Hog

example of assert checkers:

assert type(num_rolls) == int, 'num_rolls must be an integer.'
assert num_rolls > 0, 'Must roll at least once.'

*args syntax is used for the function that has arbitrary numbers of args.

Ex: in problem 8:

def make_averaged(original_function, times_called=1000):
    """Return a function that returns the average value of ORIGINAL_FUNCTION
    called TIMES_CALLED times.

    To implement this function, you will have to use *args syntax.

    >>> dice = make_test_dice(4, 2, 5, 1)
    >>> averaged_dice = make_averaged(roll_dice, 40)
    >>> averaged_dice(1, dice)  # The avg of 10 4's, 10 2's, 10 5's, and 10 1's
    3.0
    """
    # BEGIN PROBLEM 8
   
    def func(*args):
        sum = 0

        for i in range(times_called):
            sum += original_function(*args)
        
        return sum/times_called
    
    return func

We don’t precisely know how many parameters the original_function needs, so we use *args.

Environment

The expression is calculated from left to right. If the logical value of the left side of or is true, all expressions after or (whether it is followed by and or, etc.) are short-circuited, and the expression on the left side of or is directly output; if the logical value of the expression on the left side of or is false, the expression after or is output, regardless of whether the following expression is true or false.
The expression is calculated from left to right. If the logical value of the left side of and is false, all expressions after and are short-circuited until or appears, and the expression on the left side of and is output to the left side of or to participate in the next logical operation.
If the left side of or is false, or the left side of and is true, short-circuit logic cannot be used.

The types that can be considered False are: None, 0 of any numeric type, empty string ‘ ‘, empty tuple (), empty list [], empty dictionary {}

Recursion

The source code of hw03 shows a way to check or ban specific key words/structures:

>>> from construct_check import check
>>> # ban all assignment statements
>>> check(HW_SOURCE_FILE, 'num_eights',
...       ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr', 'For', 'While'])
True

Cats

decorator in python (@):
Q: What is a decorator in Python?
Choose the number of the correct choice:
0) A way to loop through an iterable

1. A type of design pattern
2. A method for declaring class properties
3. A function that takes another function as an input and returns a new function that extends or modifies the behavior of the original function
   ? 3

Ex:

'''
>>> def my_decorator(func):
...   def wrapper():
...       print("Say Hello")
...       func()
...       print("Say Goodbye")
...   return wrapper
>>> @my_decorator
... def say_hello():
...     print("Hello World")
>>> say_hello()
(line 1)? Say Hello
(line 2)? Hello World
(line 3)? Say Goodbye
'''

'''
>>> def magic_decorator(func):
...   def wrapper(x):
...     return func(x * 2)
...   return wrapper
>>> @magic_decorator
... def myfunc(x):
...   return x * 3
>>> print(myfunc(4))
? 24
'''

to check whether a function is recursive:

'''
>>> from cats import furry_fixes, autocorrect
>>> import tests.construct_check as test
>>> # Check that the recursion stops when the limit is reached
>>> import trace, io
>>> from contextlib import redirect_stdout
>>> with io.StringIO() as buf, redirect_stdout(buf):
...     trace.Trace(trace=True).runfunc(furry_fixes, "someaweqwertyuio", "awesomeasdfghjkl", 3)     
...     output = buf.getvalue()
>>> len([line for line in output.split('\n') if 'funcname' in line]) < 12
'''

str slice:

sequence[start:stop:step]

question 07: Levenshtein distance

https://zhuanlan.zhihu.com/p/507830576

https://www.youtube.com/watch?v=MiqoA-yF-0M

The dp relation:

def minimum_mewtations(typed, source, limit):
    """A diff function for autocorrect that computes the edit distance from TYPED to SOURCE.
    This function takes in a string TYPED, a string SOURCE, and a number LIMIT.

    Arguments:
        typed: a starting word
        source: a string representing a desired goal word
        limit: a number representing an upper bound on the number of edits

    >>> big_limit = 10
    >>> minimum_mewtations("cats", "scat", big_limit)       # cats -> scats -> scat
    2
    >>> minimum_mewtations("purng", "purring", big_limit)   # purng -> purrng -> purring
    2
    >>> minimum_mewtations("ckiteus", "kittens", big_limit) # ckiteus -> kiteus -> kitteus -> kittens
    3
    """
    if limit < 0:
        return 1
    if typed == "":
        return len(source)
    if source == "":
        return len(typed)
    
    if typed[len(typed)-1] == source[len(source)-1]:
        return minimum_mewtations(typed[:-1], source[:-1], limit )
    else:
        return 1 + min(minimum_mewtations(typed[:-1], source[:-1], limit - 1), minimum_mewtations(typed[:-1], source, limit - 1), minimum_mewtations(typed, source[:-1], limit - 1))

Sequence/List&Data Abstract (Tree)

To show a dictionary’s keys and values:

dic.keys()
dic.value()

To check a variable’s type:isinstance(<varname>, <vartype>) or type(<varname>) == <vartype>

tree:

def tree(label, branches=[]):
    """Construct a tree with the given label value and a list of branches."""
    for branch in branches:
        assert is_tree(branch), 'branches must be trees'
    return [label] + list(branches)

Iterator, Generator, Mutability

use it = iter(x) to declare an iterator for an iterable (x)
use next(it) to iterate

generator and yield statement:

>>> def letters_generator():
        current = 'a'
        while current <= 'd':
            yield current
            current = chr(ord(current)+1)
>>> for letter in letters_generator():
        print(letter)

a
b
c
d

>>> letters = letters_generator()
>>> type(letters)
<class 'generator'>
>>> letters.__next__()
'a'
>>> letters.__next__()
'b'
>>> letters.__next__()
'c'
>>> letters.__next__()
'd'

The first time next is called, the program executes statements from the body of the letters_generator function until it encounters the yield statement. Then, it pauses and returns the value of current. yield statements do not destroy the newly created environment, they preserve it for later. When next is called again, execution resumes where it left off. The values of current and of any other bound names in the scope of letters_generator are preserved across subsequent calls to next.

The map function, for example, takes a function and an iterable. It returns an iterator over the result of applying the function argument to each element in the iterable argument.

>>> caps = map(lambda x: x.upper(), b_to_k)
>>> next(caps)
'B'
>>> next(caps)
'C'

zip:

>>> [x + y for x, y in zip([1, 2, 3], [4, 5, 6])]
>>> [5, 7, 9]

yield from in a recursive situation
example 1:

def stair_ways(n):
    """
    Yield all the ways to climb a set of n stairs taking
    1 or 2 steps at a time.

    >>> list(stair_ways(0))
    [[]]
    >>> s_w = stair_ways(4)
    >>> sorted([next(s_w) for _ in range(5)])
    [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]]
    >>> list(s_w) # Ensure you're not yielding extra
    []
    """
    def recursive_stair_way(m, way):
        if m == 0:
            yield way
        elif m > 0:
            for i in (1, 2):
             
              yield from recursive_stair_way(m-i, way+[i])

    return recursive_stair_way(n, [])

example 2:

def yield_paths(t, value):
    """
    Yields all possible paths from the root of t to a node with the label
    value as a list.

    >>> t1 = tree(1, [tree(2, [tree(3), tree(4, [tree(6)]), tree(5)]), tree(5)])
    >>> print_tree(t1)
    1
      2
        3
        4
          6
        5
      5
    >>> next(yield_paths(t1, 6))
    [1, 2, 4, 6]
    >>> path_to_5 = yield_paths(t1, 5)
    >>> sorted(list(path_to_5))
    [[1, 2, 5], [1, 5]]

    >>> t2 = tree(0, [tree(2, [t1])])
    >>> print_tree(t2)
    0
      2
        1
          2
            3
            4
              6
            5
          5
    >>> path_to_2 = yield_paths(t2, 2)
    >>> sorted(list(path_to_2))
    [[0, 2], [0, 2, 1, 2]]
    """

    if label(t) == value:
        yield [value]
    for b in branches(t):
        for k in yield_paths(b, value):
            yield [label(t)] + k

OOP

Ants

If a variable is defined outside all of the methods in a class, then it’s called a “class attribute” of this class.
Like the variable next_id and damage in the following example:

class Insect:
    """An Insect, the base class of Ant and Bee, has health and a Place."""

    next_id = 0  # Every insect gets a unique id number
    damage = 0
    # ADD CLASS ATTRIBUTES HERE

    def __init__(self, health, place=None):
        """Create an Insect with a health amount and a starting PLACE."""
        self.health = health
        self.place = place

        # assign a unique ID to every insect
        self.id = Insect.next_id
        Insect.next_id += 1

Inheritance: class B(A) means that class B is derived from class A.

To call a parent method, use super().

magic method __str__ is for user, __repr__ is for python interpreter

about the method max and key:

max-key

Scheme(Functional Programming)

Try to code in Scheme manually is just the hell of indentation and parentheses matching...

Concept:Our object of study, a subset of the Scheme language, employs a very similar model of computation to Python’s, but uses only expressions (no statements), specializes in symbolic computation, and employs only immutable values.

some special forms in scheme:
if:(if <predicate> <consequent> <alternative>)
cond:

(cond
    (<p1> <e1>)
    (<p2> <e2>)
    ...
    (<pn> <en>)
    (else <else-expression>))

define:(define (<name> <formal parameters>) <body>)
lambda:(lambda (<formal-parameters>) <body>)

compound values(use built-in function cons):

(define x (cons 1 2))
x
(1 . 2)

(car x)
1
(cdr x)
2

key words cons and list can be used to create link table.
Whether a list is empty can be determined using the primitive null? predicate.

(define (length items)
  (if (null? items)
      0
      (+ 1 (length (cdr items)))))
(define (getitem items n)
  (if (= n 0)
      (car items)
      (getitem (cdr items) (- n 1))))
(define squares (list 1 4 9 16 25))

symbolic data:

(define a 1)
(define b 2)
(list a b)
(1 2)
(list 'a 'b)
(a b)
(list 'a b)
(a 2)

In Scheme, any expression that is not evaluated(with the prefix operator ') is said to be quoted.

no-repeats in hw08:

(define (no-repeats s) 
(if (null? s)
nil
(cons (car s) (no-repeats (filter (lambda (x) (not (= x (car s))) ) (cdr s) ) ))
)
)

Scheme Interpreter

给我吓出母语了，美国人怎么这么坏。
这proj红豆泥抽象，先把PROBLEM的空填了，有空再详细研究吧，不然CS61A拖太长了。

Higher-order abstract(Scheme)

use ` to create literal expression which can be unquoted by ,
use define-macro to define macro like #define in c

examples in lab11:

(define (if-program condition if-true if-false)
`(if ,condition ,if-true ,if-false)
)

(define (square n) (* n n))

(define (pow-expr base exp) 
(cond ((= 0 exp) 1)
(else (if (even? exp)
`(square ,(pow-expr base (/ exp 2)))
`(* ,base ,(pow-expr base (- exp 1)))
))
)
)

(define-macro (repeat n expr)
  `(repeated-call ,n (lambda() ,expr)))

; Call zero-argument procedure f n times and return the final result.
(define (repeated-call n f)
  (if (= n 1)
      (f)
      (begin (f) (repeated-call (- n 1) f) )))

SQL

difference between “declarative(sql)” and “imperative(Python & Scheme)”: SQL focuses on the result, while Python and Scheme focus on the process

SQL syntax:

SELECT includes a comma-separated list of column description.

SELECT [expression] AS [name], [expression] AS [name] --SELECT [columns] 
SELECT [columns] FROM [table] WHERE [condition] ORDER BY [order];

Selecting literals creates new tables.

Arithmetic example:

JOIN or comma is used to join two tables.

what happens when JOIN:

Combos of rows.
Implicit syntax: comma or JOIN
Explicit syntax:

FROM [table] JOIN/comma(,) [table] ON [conditions] 

What if the tables share some column names?
Use Aliases or Dot Expressions to distinguish them
example from lab12:

CREATE TABLE sharing AS
  SELECT a.course, count(distinct a.hall) from finals as a, finals as b where a.hall=b.hall and a.course <> b.course group by a.course;

String expressions: use || to combine the strings

Aggregate function and group-by example from hw10:
We want to create a table that contains the height range (defined as the difference between maximum and minimum height) of all dogs that share a fur type. However, we’ll only consider fur types where each dog with that fur type is within 30% of the average height of all dogs with that fur type; we call this the low variance criterion.

select fur, max(height)-min(height) from dogs group by fur having min(height)>=0.7*avg(height) and max(height)<=1.3*avg(height);