Scratch and Python 2018 Summer - Python Lecture 3
===

### Iterator and Iterables

+ Iterables: bags of items
+ `list`
+ `tuple`
+ `str`
+ `generator`
+ `range`
+ `range(n)` sample code

            for i in range(10):
                print(i)

+ `range(L,U)` sample code

            for i in range(3,9):
                print(i)

+ `range(L,U,step)` sample code

            for i in range(3,9,2):
                print(i)

+ Iterator: an access to a certain item and the iterator to its next item
+ `it = iter(iterables)`
+ Next element: `next(it)` or `it.__next__()`
+ `StopIteration` will be raised if no more elements.
+ `next(it,default)` gives `default` if no more elements, otherwise the next element will be given.
+ Sample code 1

        lst = [1,3,7,9]
        it = iter(lst)
        print(next(it))
        print(next(it))
        print(next(it))
        print(next(it))
        print(next(it))

+ Sample code 2

        lst = [1,3,7,9]
        it = iter(lst)
        print('outside for-loop:',next(it))
        for i in it:
            print('inside for-loop:',i)

+ Sample code 3

        lst = [1,3,7,9]
        it = iter(lst)
        print('outside while-loop:',next(it))
        while True:
            try:
                i = next(it)
            except StopIteration:
                break
            print('inside while-loop:',i)

+ Use `except Type:` to catch certain kind of error or exception`Type`
+ Sample code 4

    def merge(a, b):
        it_a, it_b = iter(a), iter(b)
        item_a = next(it_a,None)
        item_b = next(it_b,None)
        while item_a != None and item_b != None:
            if item_a <= item_b:
                yield item_a
                item_a = next(it_a,None)
            else:
                yield item_b
                item_b = next(it_b,None)
        if item_a != None: yield item_a
        if item_b != None: yield item_b
        for item in it_a: yield item
        for item in it_b: yield item

    def mergesort(a):
        L = len(a)
        if L<=1:
            for x in a:
                yield x
            return
        for x in merge(mergesort(a[:L//2]),mergesort(a[L//2:])):
            yield x

    print('merge',[1,3,5,6],'and',[2,4,7,8])
    for item in merge([1,3,5,6],[2,4,7,8]):
        print(item)

    print()
    print('mergesort',[1,5,2,4,3,8,7,6])
    for item in mergesort([1,5,2,4,3,8,7,6]):
        print(item)

+ Use `pass` to do nothing.
+ `in` operator
+ Sample code

        def gen():
            i = 0
            while True:
                yield i
                i = i + 1
        
        if 5 in gen():
            print('5 is in gen()')
        if 5000 in gen():
            print('5000 is in gen()')
        if 5000000 in gen():
            print('5000000 is in gen()')
        if 0.5 in gen():
            print('0.5 is in gen()')
        
        print('This is the last line')

+ Some useful tools
+ [`zip`](https://docs.python.org/3/library/functions.html#zip)

        lst_a = [1,3,5,7,9]
        lst_b = ['a','b','C','D']
        for item in zip(lst_a,lst_b):
            print(item)
        for a, b in zip(lst_a,lst_b):
            print('a:',a,'b:',b)

+ [`enumerate`](https://docs.python.org/3/library/functions.html#enumerate)

        lst = [1,3,5,7,9]
        for item in enumerate(lst):
            print(item)

+ [`map`](https://docs.python.org/3/library/functions.html#map)

        scores = (40,50,60,70,80,90,100)
        for new_score in map(lambda x: int(10*x**0.5), scores):
            print(new_score)

+ `lambda x: int(10*x**0.5)` is a shorter and anonymous definition of the following function.

        def noname(x):
            return int(10*x**0.5)

+ [`sum`](https://docs.python.org/3/library/functions.html#sum)

        scores = (40,50,60,70,80,90,100)
        print(sum(scores)/len(scores))

+ `str`: use `.join()`

            characters = ('a','b','c','d','e','f','g')
            print(sum(characters))

+ [`min`](https://docs.python.org/3/library/functions.html#min)
+ [`max`](https://docs.python.org/3/library/functions.html#max)
+ [`filter`](https://docs.python.org/3/library/functions.html#filter)

        print(*filter(lambda x: x % 2 == 0, range(20)))

+ `lambda x: x % 2 == 0` is `True` if `x` is even.
+ [`all`](https://docs.python.org/3/library/functions.html#all)
+ [`any`](https://docs.python.org/3/library/functions.html#any)

+ List comprehension
+ `type(int(10*x**0.5) for x in range(0,100,5) if x % 2 == 0)`
+ `[int(10*x**0.5) for x in range(0,100,5) if x % 2 == 0]`
+ More tools
+ [`itertools`](https://docs.python.org/3/library/itertools.html)
+ `import itertools`
+ `itertools.combinations`
+ [`functools`](https://docs.python.org/3/library/functools.html)
+ `import functools`
+ `functools.reduce`

### String processing

+ Escape Characters: [Table](https://automatetheboringstuff.com/chapter6/#calibre_link-40)
+ Multiline Strings: triple quotes `'''`
+ Integers, characters and strings
+ `chr`
+ try `chr(65)`
+ `ord`
+ try `ord('A')`
+ Python uses `str`'s of length 1 to represent characters.
+ Indexing:
+ `print('123'[0])`
+ `print('123'[-1])`
+ `index()`
+ `print('123123123'.index('312'))`
+ Slicing:
+ `print('abcde'[2:])`
+ `print('abcde'[:2])`
+ `print('abcde'[1:3])`
+ `in` and `not in`
+ `print('abc' in 'zabcy')`
+ `print('gg' not in 'zabcy')`
+ `upper()` and `lower()`
+ `isupper()`, `islower()`, `isdecimal()`, `isalpha()`, `isalnum()`
+ try `'123.0'.isdecimal()`
+ `join(list_str)`
+ try `', '.join([str(i) for i in range(10)])`
+ `split(string)`
+ try `'<a href="https://automatetheboringstuff.com/">'.split('"')`
+ `startswith(string)` and `endswith(string)`
+ Many URLs start with `http` and end with `html`
+ `strip()`, `rstrip()`, `lstrip()`
+ `.format()`: Replace placeholder `{}` with corresponding variables.
+ Ex: `'Case {}: {}, {}'.format(1,68.7,'passed')`
+ URL
+ Almost everything is specified: `https://en.wikipedia.org/w/api.php?action=rsd`
+ Same protocol: `//en.wikipedia.org/w/api.php?action=rsd`
+ Same address: `/w/api.php?action=rsd`
+ Relative path: `api.php?action=rsd`

### Random

+ [`import random`](https://docs.python.org/3/library/random.html)
+ Random integer from `a` to `b`: `random.randint(a,b)`
+ Random floating point number in `[0.0,1.0)`: `random.random()`
+ Randomly shuffle a list `lst`: `random.shuffle(lst)`
+ Random choice from a sequence: `random.choice(seq)`
+ Random `k` samples from a population: `random.sample(population,k)`

### Game: Guess a secret number

+ Guess a secret number from `0` to `9`
+ Sample code

    # Read an integer which is in {0,...,9}
    def read_a_digit():
        ret = -1
        while True:
            try:
                ret = int(input('Input a digit: '))
            except ValueError:
                print('Not an integer')
                continue
            if ret >= 0 and ret <= 9:
                return ret
            print(ret,'is not in {0,...,9}.')

    from random import randint

    ans = randint(0,9)

    guess = read_a_digit()
    while guess != ans:
        print(guess,'is not the answer')
        guess = read_a_digit()

    print('Congrats! The answer is',ans)

+ Guess a secret number from `0` to `9` with hints
+ Sample code

    # Read an integer which is in {0,...,9}
    def read_a_digit():
        ret = -1
        while True:
            try:
                ret = int(input('Input a digit: '))
            except ValueError:
                print('Not an integer')
                continue
            if ret >= 0 and ret <= 9:
                return ret
            print(ret,'is not in {0,...,9}.')

    from random import randint

    ans = randint(0,9)

    guess = read_a_digit()
    while guess != ans:
        if ans < guess:
            print(guess,'is greater than the answer.')
        else:
            print(guess,'is less than the answer.')
        guess = read_a_digit()

    print('Congrats! The answer is',ans)

+ [Bulls and Cows](https://en.wikipedia.org/wiki/Bulls_and_Cows)
+ Sample code

    from random import sample
    from itertools import combinations

    # Check whether a input is valid
    def valid(s):
        if len(s)!=4:
            return False
        if any(x not in '0123456789' for x in s):
            return False
        if any(x==y for x, y in combinations(s,2)):
            return False
        return True

    # Read string which has four distinct digits
    def read_four_distinct_digits():
        while True:
            ret = input('Input four distinct digits: ')
            if valid(ret):
                return ret
            print(ret,'is not valid.')

    ans = ''.join(sample('0123456789',4))

    guess = read_four_distinct_digits()
    while guess != ans:
        A = sum(1 for x,y in zip(guess,ans) if x==y)
        B = sum(1 for x in guess if x in ans)-A
        print(guess,'is {}A{}B.'.format(A,B))
        guess = read_four_distinct_digits()

    print('Congrats! The answer is',ans)

#### Task: Assistant
Write a program to helps you play Bulls and Cows.

There are many approaches to help you to play the game. But the following strategy will help you to guess the number within 10 steps.
1. Maintain a list of candidates.
2. Randomly pick a candidate from the list, and guess it.
3. If the answer is what you guess, then you win. Otherwise, you would know how many bulls and cows.
4. Remove the candidates which do not match the result from the list. Go to step 2.

5. Unfinished sample code

    import itertools
    import random

    # return guess and ans is ?A?B
    def check( guess, ans ):
        A = #?
        B = #?
        return '{}A{}B'.format(A,B)

    # S = [0123, 0124, 0125, ... , 9876] (4 distinct digit)
    S = #?

    while True:
        if len(S) == 0:
            print("No solution!")
            break

        # ans = random pick one element from S
        ans = #?
        print(ans)

        # read ?A?B
        cmd = input()

        if cmd == '4A0B' :
            break
        else:
            # update S: remove all element x in S such that check(x,ans) ≠ cmd
            S = #?

### More on `list` and `tuple`

+ List
+ Empty list: `[]`
+ May have elements of different types
+ `[12, 3.4, None, True, 'string', print]`
+ Access (zero-based) `i`-th element of `list x`: `x[i]`
+ try `[123,456][1]`
+ try `[12, 3.4, None, True, 'string', print][5]('hello world')`
+ try `[123,456][1.0]`
+ Lists are mutable: you may change the contents!
+ Tuple
+ Empty tuple: `()`
+ Single element tuple: `(element,)`
+ Try `type(('str'))` and `type(('str',))`
+ Comprehension
+ Try `type((x for x in range(5)))`
+ Use `tuple(x for x in range(5))` to generate `(0,1,2,3,4)`
+ `(12, 3.4, None, True, 'string', print)`
+ The elements are immutable: you may not change the contests!
+ `list()` and `tuple()`
+ Try `list(('a','b','c'))`
+ Try `tuple(['d','e','f'])`
+ Try `list('hello')`
+ Try `tuple('hello')`
+ Negative index: `a_list_or_tuple[-1]`
+ Slice
+ `print(['a','b','c','d','4'][1:3])`
+ `print(['a','b','c','d','4'][2:])`
+ `print(['a','b','c','d','4'][:4])`
+ `print(['a','b','c','d','4'][-3:])`
+ `print(['a','b','c','d','4'][:-3])`
+ `print(['a','b','c','d','4'][3:1])`
+ Inclusive, exclusive
+ `print(['a','b','c','d','4'][1:5:3])`
+ `in`
+ `not in`
+ Concatenation `+`
+ Replication `*`
+ `index()`
+ try `print([0,1,2,0].index(0))`
+ Auto boxing & auto unboxing
+ [code](lec10-1.py)

### Lists are Mutable

+ `insert(pos,val)`: insert `val` to position `pos`
+ Let `a = [0,1,2]`. What will happen if we perform `a.insert(1,3)`?
+ `append(val)`
+ `pop()`: remove the last element and return its value
+ `pop(pos)`: remove the element of position `pos`
+ `remove(val)`: remove an element of value `val`
+ Let `a = [1,0,0,1]`. What will happen if we perform `a.remove(1)`?
+ `sort()`: sort the list ascendingly
+ `type(value)` and `id(name)`
+ [Concept](https://automatetheboringstuff.com/chapter4/#calibre_link-130)
+ If you modify an object, then all references will be changed.
+ Copy and Deepcopy
+ `import copy`
+ `copy.copy()`: Shallow copy
+ `copy.deepcopy()`: Deep copy

### Higher Dimension

+ How to define a $5$-by-$5$ matrix with all entries set to zero?
+ Correct: `[[0]*5,[0]*5,[0]*5,[0]*5,[0]*5]`
+ Incorrect: `[[0]*5] * 5`
+ Correct: `[[0]*5 for _ in range(5)]`

### More on `dict`

+ `list` is indexed by `int`
+ From `0` to `len()-1`
+ Dictionary is indexed by keys (words).
+ Word: key
+ Definition: value
+ A set of key-value pairs
+ `instructor = {'Name': 'MZ', 'Height': 178, 'Weight': 108}`
+ try `print(instructor['Name'])`
+ try `print(instructor['age'])`
+ Empty dictionary: `{}`
+ `dict` is mutable
+ Add a new item via assignment
+ `a_dict[key]=val`
+ Modify an item via assignment
+ `a_dict[key]=val`
+ Remove an item via `del`
+ `del a_dict[key]`
+ `del` can also undefine a variable.
+ Iterate a dictionary
+ `keys()`
+ `values()`
+ `items()`
+ `in`
+ try `print('MZ' in instructor)`
+ try `print('Name' in instructor)`
+ try `print(('Name','MZ') in instructor)`
+ `get(key,val)`: If `key` is missing, then return `val`
+ Example code: keyword arguments
+ Try to use an undefined item to compute.
+ `setdefault(key,val)`: if there is no such `key`, initialize the key-value pair to `(key,val)` and return `val`. Otherwise return the value corresponding `key`.
+ Example: word count

        some_list = [0,3,5,7,1,2,1,2,1]
        counter = {}
        for x in some_list:
            if x in counter.keys():
                counter[x] += 1
            else:
                counter[x] = 1
        print(counter)

can be simplified into

        some_list = [0,3,5,7,1,2,1,2,1]
        counter = {}
        for x in some_list:
            counter.setdefault(x,0)
            counter[x] += 1
        print(counter)