ES 26 Class Rules

ES 26 Lecture Slides

Linux terminal

Command line

kevin@kevinsogo:~/foo/bar$

• kevin — user name
• kevinsogo — computer name
• ~/foo/bar — current folder

USERNAME@COMPUTERNAME:CURRENTFOLDER$

Basic commands

• ls — list contents of current directory
• cd FOLDERNAME — change directory to FOLDERNAME
• mkdir FOLDERNAME — make new directory named FOLDERNAME
• touch FILENAME — make new file named FILENAME
• python3 FILENAME — run FILENAME as a Python program
• python3 — run Python in interactive mode
• subl NAME — open NAME in Sublime Text
• subl — open Sublime Text

Some special syntax

• ~ — home folder (/home/USERNAME)
• .. — parent folder
• . — current folder

Recommended Visual Studio Code Settings

• Editor: Render Whitespace: set to all
• Files: Auto Save: set to afterDelay
• Files: Auto Save Delay: set to a value less than 5000

Python

Integers (int)

• ..., -3, -2, -1, 0, 1, 2, 3, ...

Conversion

• int(x)
  • int(5) == 5
  • int('5') == 5
  • int(True) == 1
  • int(False) == 0

Operations

• +, -, * — arithmetic
  • 2 + 3 * 4 - 5 == 9
• / — division (produces floats; be careful!)
  • 15 / 6 == 2.5
  • 12 / 6 == 2.0 # float!
• // — floor division
  • 15 // 6 == 2
  • 12 // 6 == 2
  • -1 // 6 == -1
• % — modulo/remainder
  • 15 % 6 == 3
  • 12 % 6 == 0
  • -1 % 6 == 5
• ** — power
  • 2**3 == 8
• ==, !=, <, >, <=, >= — comparison (see below)
• Division Theorem — the following is always true if b != 0
  • a == (a // b) * b + (a % b)

Strings (str)

• delimited by single quotes or double quotes
  • 'hi' == "hi"
• escape with \
  • "a\\b\"c"

Conversion

• almost anything can be converted to str via str()
  • str(5) == "5"
  • str(('1', 2)) == "('1', 2)"

Operations

• + — concatenate strings
  • "abc" + "def" == "abcdef"
• * — replicate string
  • "hi" * 4 == "hihihihi"
• s in t — substring check
  • "nan" in "banana"
• t.index(s) — substring location (leftmost)
  • "banana".index("na") == 2
• s.strip() — leading and trailing whitespace (spaces, tabs, newlines) all removed
  • " a b c ".strip() == "a b c"
• s[i] — indexing
  • get element at index i
  • s[0] is the first element
  • s[-1] is the last element
  • indexing starts at 0
  • negative indices start at the back
  • "banana"[2] == "banana"[-2] == "n"
• s[i:j] — slicing
  • substring from index i inclusive to index j exclusive
  • "banana"[1:4] == "ana"
  • "banana"[-4:] == "nana"
  • "banana"[2:2] == "banana"[3:2] == ""
• s[i:j:k] — slicing with step size k
  • "banana"[2:4:2] == "n"
  • "banana"[2:5:2] == "nn"
  • "banana"[1::2] == "aaa"
  • "banana"[::-1] == "ananab"
• len() — length
  • len("banana") == 6
• ==, !=, <, >, <=, >= — comparison (see below)
• .join — join to single string
  • '--'.join(("ab", "cd", "efg")) == "ab--cd--efg"
• .split — split string to list by whitespace
  • " Let It Be ".split() == ['Let', 'It', 'Be']

Booleans (bool)

• Only two values: True and False

Conversion

• bool(x) converts x to True if x is, in some sense, "nonempty" or "nontrivial"
  • for ints and floats, bool(x) is True iff x is nonzero
  • for strs and tuples, bool(x) is True iff x is nonempty
  • bool("") is False
  • bool(0) is False
  • bool(None) is False
  • bool(()) is False
  • bool(1) is True
  • bool(5) is True
  • bool(-1) is True
  • bool("hi") is True
  • bool("True") is True
  • bool("False") is True
  • bool((1, 2)) is True
• ==, !=, <, >, <=, >= — comparison (see below)

Operations

• x and y — True iff x and y are both True
  • (True and True) is True
  • (False and True) is False
  • (True and False) is False
  • (False and False) is False
  • (5 and 6) == 6
  • has short-circuiting behavior: If the left side is False, the right side is not evaluated.
• x or y — True iff at least one of x and y is True
  • (True or True) is True
  • (False or True) is True
  • (True or False) is True
  • (False or False) is False
  • (5 or 6) == 5
  • has short-circuiting behavior: If the left side is True, the right side is not evaluated.

• not x — True iff x is False

  • (not True) is False
  • (not False) is True

• Note that and and or are short-circuiting

  • (5 or 1//0) == 5 will run without errors.
  • (0 and 1//0) == 0 will run without errors.

Tuples (tuple)

• create by listing elements or comprehension (via generators):
  • tuple(2*x for x in (3, 1, 4)) == (6, 2, 8)
  • tuple(2*x for x in (3, '1', 4)) == (6, '11', 8)
• if exactly one element, trailing comma required: (1,) and not (1)

Conversion

• tuple() takes in any sequence type
  • tuple(('a', 'b', 'c')) == tuple("abc") == ('a', 'b', 'c')

Operations

• + — concatenate tuples
  • (1, 2) + (3, 4, 5) == (1, 2, 3, 4, 5)
• * — replicate string
  • ("x", "y") * 3 == ("x", "y", 'x', 'y', "x", 'y')
• x in t — element check
  • 4 in (3, 1, 4, 1, 5)
• t.index(x) — element location (leftmost)
  • (3, 1, 4, 1, 5).index(1) == 1
• t[i] — indexing
  • get element at index i
  • t[0] is the first element
  • t[-1] is the last element
  • indexing starts at 0
  • negative indices start at the back
  • (3, 1, 4, 1, 5)[2] == (3, 1, 4, 1, 5)[-3] == 4
• t[i:j] — slicing
  • substring from index i inclusive to index j exclusive
  • (3, 1, 4, 1, 5)[1:4] == (1, 4, 1)
  • (3, 1, 4, 1, 5)[-2:] == (1, 5)
  • (3, 1, 4, 1, 5)[2:2] == (3, 1, 4, 1, 5)[3:2] == ()
• t[i:j:k] — slicing with step size k
  • (3, 1, 4, 1, 5)[2:4:2] == (4,)
  • (3, 1, 4, 1, 5)[2:5:2] == (4, 5)
  • (3, 1, 4, 1, 5)[1::2] == (1, 1)
  • (3, 1, 4, 1, 5)[::-1] == (5, 1, 4, 1, 3)
• len() — length
  • len((3, 1, 4, 1, 5)) == 5
• ==, !=, <, >, <=, >= — comparison (see below)

Lists (list)

• create by listing elements or comprehension (via generators):
  • [2*x for x in (3, 1, 4)] == [6, 2, 8]
  • [2*x for x in (3, '1', 4)] == [6, '11', 8]

Conversion

• list() takes in any sequence type
  • list(('a', 'b', 'c')) == list("abc") == ['a', 'b', 'c']

Operations

• + — concatenate tuples
  • [1, 2] + [3, 4, 5] == [1, 2, 3, 4, 5]
• * — replicate string
  • ["x", "y"] * 3 == ["x", "y", 'x', 'y', "x", 'y']
• x in t — element check
  • 4 in [3, 1, 4, 1, 5]
• t.index(x) — element location (leftmost)
  • [3, 1, 4, 1, 5].index(1) == 1
• t[i] — indexing
  • get element at index i
  • t[0] is the first element
  • t[-1] is the last element
  • indexing starts at 0
  • negative indices start at the back
  • [3, 1, 4, 1, 5][2] == [3, 1, 4, 1, 5][-3] == 4
• t[i:j] — slicing
  • substring from index i inclusive to index j exclusive
  • [3, 1, 4, 1, 5][1:4] == [1, 4, 1]
  • [3, 1, 4, 1, 5][-2:] == [1, 5]
  • [3, 1, 4, 1, 5][2:2] == [3, 1, 4, 1, 5][3:2] == []
• t[i:j:k] — slicing with step size k
  • [3, 1, 4, 1, 5][2:4:2] == [4,]
  • [3, 1, 4, 1, 5][2:5:2] == [4, 5]
  • [3, 1, 4, 1, 5][1::2] == [1, 1]
  • [3, 1, 4, 1, 5][::-1] == [5, 1, 4, 1, 3]
• len() — length
  • len([3, 1, 4, 1, 5]) == 5
• ==, !=, <, >, <=, >= — comparison (see below)

Mutation

• s.append(v) — insert v as the last element
• s.pop() — remove the last element
• s.pop(i) — remove the element at index i
  • can be slow
• s.clear() — clear the whole list
• s.insert(i, v) — insert v at index i (the value v is at index i after insertion)
  • can be slow
• s.remove(v) — remove the leftmost occurrence of value v
  • can be slow
• s.extend(t) — append elements of t at the end
• s.sort() — sort the list in increasing/nondecreasing order
• s[i] = v — replace the value at index i by v
• s[i:j] = seq — replace the given slice by the elements of seq
• s[i:j:k] = seq — replace the given slice by the elements of seq

Floats (float)

• try to minimize usage because of numerical errors!
  • 0.1 + 0.1 == 0.2
  • 0.1 + 0.2 != 0.3
  • (1e20 + 1.0) - (1e20) == 0.0

Frozen Sets (frozenset)

• create via listing elements or comprehension (via generators):
  • frozenset(abs(x) for x in (-1, 0, 1, 0, 4, -3)) == frozenset((0, 1, 3, 4))

Conversion

• frozenset() takes in any sequence type
  • frozenset(('a', 'b', 'c')) == frozenset("abaca")

Operations

• | — union
  • (frozenset((1, 2)) | frozenset((1, 3))) == frozenset((1, 2, 3))
• & — intersection
  • (frozenset((1, 2)) & frozenset((1, 3))) == frozenset((1,))
• - — set difference
  • (frozenset((1, 2)) - frozenset((1, 3))) == frozenset((2,))
• x in t — element check
  • 4 in frozenset((3, 1, 4, 1, 5))
• ==, != — equality
• < — proper subset
  • frozenset((1, 3)) < frozenset((1, 2, 3))
• <= — subset
  • frozenset((1, 3)) <= frozenset((1, 2, 3))
  • frozenset((1, 3)) <= frozenset((1, 3))
• > — proper superset
  • frozenset((1, 2, 3)) > frozenset((1, 3))
• >= — superset
  • frozenset((1, 2, 3)) >= frozenset((1, 3))
  • frozenset((1, 3)) >= frozenset((1, 3))
• len() — length
  • len(frozenset((3, 6, 3))) == 2

Sets (set)

• create via listing elements or comprehension:
  • {abs(x) for x in (-1, 0, 1, 0, 4, -3)} == {0, 1, 3, 4}
• empty set: set() (not {}!)

Conversion

• set() takes in any sequence type
  • set(('a', 'b', 'c')) == set("abaca") == {'a', 'b', 'c'}

Operations

• | — union
  • ({1, 2} | {1, 3}) == {1, 2, 3}
• & — intersection
  • ({1, 2} & {1, 3}) == {1}
• - — set difference
  • ({1, 2} - {1, 3}) == {2}
• x in t — element check
  • 4 in {3, 1, 4, 1, 5}
• ==, != — equality
• < — proper subset
  • {1, 3} < {1, 2, 3}
• <= — subset
  • {1, 3} <= {1, 2, 3}
  • {1, 3} <= {1, 3}
• > — proper superset
  • {1, 2, 3} > {1, 3}
• >= — superset
  • {1, 2, 3} >= {1, 3}
  • {1, 3} >= {1, 3}
• len() — length
  • len({3, 6, 3}) == 2

Mutation

• s.add(v) — add v as an element of the set
• s.remove(v) — remove v as the last element
• s.pop(i) — remove the element at index i
  • can be slow
• s.clear() — clear the whole set

Dictionaries (dict)

• maps keys to values
• fast lookup from keys to values
• keys are unique
• keys must be immutable
• create via listing key-value pairs or comprehension:
  • {x: x**2 for x in (3, 0, -3)} == {0: 0, -3: 9, 3: 9}
• empty dict: {}

Conversion

• dict() takes in any sequence of pairs
  • dict((('a', 1), ('b', 2))) == {'a': 1, 'b': 2}

Operations

• d[k] — get value corresponding to key k
  • {1: 2, 3: 4}[3] == 4
• k in d — key check
  • 1 in {1: 2, 3: 4}
  • 2 not in {1: 2, 3: 4}
• ==, != — equality
• len() — length (number of key-value pairs)
  • len({1: 4, 2: 5, 1: 6}) == 2
• d.keys() — go through keys
  • {k for k in {1: 2, 3: 4}.keys()} == {1, 3}
• d.values() — go through values
  • {v for v in {1: 2, 3: 4}.values()} == {2, 4}
• d.items() — go through key-value pairs
  • {kv for kv in {1: 2, 3: 4}.items()} == {(1, 2), (3, 4)}

Mutation

• d[k] = v — set value corresponding to key k to v
• del d[k] — remove key k
• d.pop(k) — remove key k and return corresponding value
• d.clear() — clear the whole dict
• d.update(d2) — add key-value pairs of the given dict

Variables

• name must not start with digit
• binding/assignment
  • x = y means "make the name x point to the value y"
  • is not mathematical equality! (Use ==)

    val = 5
    num = val
    

• destructuring bind

  (x, y) = (1, 2)
  ((a, b), (c, d)) = ((1, 2), (3, 4))
  

Syntax

Indentation

HEADER:
    STATEMENT1
    STATEMENT2
    STATEMENT3

• block: collection of statements at same level
  • line before them have lower indentation level and always ends with :

If-elif-else

if condition1:
    ... # do if condition1 true
elif condition2:
    ... # do if condition1 false and condition2 true
elif condition3:
    ... # do if condition1, condition2 both false and condition3 true
else:
    ... # do if all three conditions false

• Can have any number of elif (including zero)
• else is optional

Function definition

def has_real_root(a, b, c):
    d = b**2 - 4*a*c
    return d >= 0

• exits as soon as it reaches a return; the first one it encounters
• variables inside are "local"—can't be accessed outside
• returns None if exited without reaching a return statement

Pass

pass

• does nothing. Useful when the syntax requires a block, but you want it empty

Comments

# Comments are ignored

LEGENDRES_CONSTANT = 1  # Legendre's constant up to 420 correct decimal places

Chaining

• chaining is allowed
  • 1 < 3 > 2 == 2 <= 2

Splat (aka. unpacking)

• can splat to pass args

x = (1, 2, 3)
y = 4
z = (5, 6)
print(*x, y, *z)

• can splat to make tuples, lists, sets
  • (*x, y, *z) == (1, 2, 3, 4, 5, 6)
  • [*x, y, *z] == [1, 2, 3, 4, 5, 6]
  • {*x, y, *z, *x} == {1, 2, 3, 4, 5, 6}

Dictionary Splat

w1 = {1: 2, 3: 4}
w2 = {5: 6}

print({4: 5, **w1, **w2})

Variadic functions

def print_lol(*args):
    print(*args, 'haha')

print_lol("kumusta")


def f(a, b, c, *rest):
    # function with at least three arguments
    ...

• function with any number of arguments

Comprehension

def get_evens(seq):
    return tuple(x for x in seq if x % 2 == 0)

def cartesian_product(s, t):
    return frozenset((x, y) for x in s for y in t)

def even_sum_pairs(seq1, seq2):
    # all pairs whose sum is even
    return [(v1, v2)
        for v1 in seq1
        for v2 in seq2
        if (v1 + v2) % 2 == 0
    ]

• similar to set-builder notation in math, e.g., \(\{(x, y) \mid x \in S, y \in T \}\)

Assertion

assert is_even(6)
assert not is_even(5)

• raises error if condition is false
• used to as sanity check throughout code
• do not use this for input validation
• intended to always pass; a failing assertion is a bug

Ternary Operator

def f(x):
    a = ('positive' if x > 0 else 'nonpositive')
    b = ('even' if x % 2 == 0 else 'odd')
    return f"{a} {b} integer"

print(f(5))   # positive odd integer
print(f(-4))  # nonpositive even integer

• a conditional expression

f-strings

msg = f"The age of {name} is {age}."

• convenient way to build strings`

Raising an Exception

raise ValueError(f"The number {n} is invalid")

• raise an exception

Handling/Catching an Exception

try:
    some_operation_that_might_fail()
except TypeError:
    print("A TypeError was raised!")
except ValueError:
    print("A ValueError was raised!")
except Exception:
    print("It raised an exception that's not TypeError or ValueError!")
else:
    print("No exception occurred, yay!")

• except: to catch an exception of a given type
• except Exception: as a catch-all. put it last
• else: for the case where no exception occurred

For Loops

for digit in (3, 1, 4, 1, 5):
    print(digit)

sm = 0
for d in [3, 1, 4]:
    sm += d
    print(d)
print(sm)

• perform block of code for each element of the given sequence

While Loops

x = 10**9
while x > 0:
    print(x)
    x //= 2

• repeats block of code while the condition is true

Break

def collatz_seq(n):
    while True:
        yield n
        if n == 1:
            break
        n = collatz(n)

• exits a for or while loop
• try to use sparingly

Generators

def all_evens(seq):
    for v in seq:
        if v % 2 == 0:
            yield v

for v in all_evens([3, 1, 4, 1, 5, 9, 2]):
    print(v)

# generator expression
s = (v**2 for v in range(5))
print(list(s))  # [0, 1, 4, 9, 16]
print(list(s))  # []

• one-time-use sequence
• next(g) to get the next element
• for loops and comprehensions can naturally deal with them
• iter(seq) to make a generator from any sequence type
• lazily evaluates—only executes when next element is needed, and then pauses once it yields or exits

def nonempty_substrings(s):
    for i in range(len(s)):
        yield from substrings_starting_from(s, i)

• yield from to yield every element of another sequence/generator

Starred assignment

(a, b, *c, d, e) = 'bananaman'
print(a) # b
print(b) # a
print(c) # ['n', 'a', 'n', 'a', 'm']
print(d) # a
print(e) # n

• can only have one star (*) on the left

Import

from math import cos, pi

print("The cosine of", pi, "is", cos(pi))

import math

print("The cosine of", math.pi, "is", math.cos(math.pi))

• loads variables and functions from modules

Miscellaneous

Special Values

• None — generic value representing "don't care" or nothingness
  • returned by functions that exited without reaching a return statement

Special Functions

• chr(code) — the character with ASCII code code
  • chr(97) == 'a'
• ord(ch) — the ASCII code of character ch
  • ord('a') == 97
• repr(x) — python representation of value x
• print(...) — display as output
• input() — take a line of input (probably won't be used in OJ)
• type(x) — the "type" of x
• range(n) — goes from 0 to n-1
  • tuple(i**2 for i in range(4)) == (0, 1, 4, 9)
• range(i, j) — goes from i to j-1
  • tuple(range(1, 5)) == (1, 2, 3, 4)
• range(i, j, k) — goes from i to j-1 with step size k
  • tuple(range(1, 5, 2)) == (1, 3)
  • tuple(range(5, 1, -2)) == (5, 3)
  • range(5, 0, -2)[::-1] == range(1, 7, 2)
• isinstance(some_value, some_type) — check that a value is of a given type
  • isinstance(5, int)
  • not isinstance(5.0, int)
• sorted(seq) — return a sorted version of seq
  • sorted(v**2 for v in range(-2, 3)) == [0, 1, 1, 4, 4]
• sum(seq) — the sum of the elements of seq
  • sum(v**2 for v in range(-2, 3)) == 10
• min(seq) — the minimum of the elements of seq
  • min(v**2 for v in range(-2, 3)) == 0
• max(seq) — the maximum of the elements of seq
  • max(v**2 for v in range(-2, 3)) == 4
• min(x, y), min(x, y, z), etc. — the minimum of the arguments
  • min(3, 1, 4) == 1
• max(x, y), max(x, y, z), etc. — the maximum of the arguments
  • max(3, 1, 4) == 4
• abs(num) — the absolute value of the number num
  • abs(5) == abs(-5) == 5
  • abs(0) == 0
• any(seq) — True iff at least one element of seq is true
  • any((0, 2, 1)) is True
  • any((0, False, "")) is False
  • any(v > 2 for v in range(5)) is True
• all(seq) — False iff at least one element of seq is false
  • all((2, 0, 1)) is False
  • all((-1, 'abc', [3])) is True
  • all(v > 2 for v in range(5)) is False
• enumerate(seq) — same sequence but with indices in front
  • [*enumerate('abc')] == [(0, 'a'), (1, 'b'), (2, 'c')]
  • [*enumerate('abc', 3)] == [(3, 'a'), (4, 'b'), (5, 'c')]
• zip(seq1, seq2) — generates pairs of corresponding elements
  • [*zip((1, 2, 3), 'abc')] == [(1, 'a'), (2, 'b'), (3, 'c')]
  • can receive any number of sequences
• reversed(seq) — generates the elements of sequence seq in reverse
  • [*reversed((1, 2, 3))] == [3, 2, 1]
  • does not support pure generators
• iter(seq) — make a generator from the sequence seq
• next(g) — get the next element of generator g
  • raises StopIteration when there are no more

Comparison: Equality

• == — equals
• != — does not equal

works for most types

Comparison: Ordering

• < — less than
• > — greater than
• <= — less than or equal
• >= — greater than or equal

works for: numeric types, tuples, lists, bools

for frozensets, interpreted as subset and superset operations

Exceptions

• IndexError — index out of bounds
  • "HAL"[9000]
• TypeError — operand doesn't have correct type
  • 123 + "456"
• NameError — name not found
  • print(a_nonexistent_variable)
• SyntaxError — invalid Python program
  • x = 1 /// 2
• AttributeError — attribute access fails
  • "half life 3".develop()
• ValueError — operand type okay, but value is illegal
  • int("six")
• AssertionError — an assertion fails
  • assert 2 + 2 == 5
• IOError — I/O system reports failure (e.g., file not found)
  • with open("a_nonexistent_file.txt") as file:
• KeyError — when something is not found in sets or dictionaries
  • {'1': '2'}['2']
• StopIteration — when taking the next element of a fully-consumed generator
  • next(iter([]))
• Exception — catch-all

Augmented Assignment

• x += y — increase x by y
• x -= y — decrease x by y
• x *= y — multiply x by y

other binary operators have similar "assignment" versions:

• +=
• -=
• *=
• %=
• //=
• /=
• **=
• |=
• &=

Modules

itertools:

• count(), count(start), count(start, step) — counts up every step (default 1), starting from start (default 0)
  • [*islice(count(15, 2), 3)] == [15, 17, 19]

Strategy and Tactics

• DRY — Don't Repeat Yourself
  • copy-pasting is often bad
  • make functions (abstraction)
• KISS — Keep It Simple, S*****
  • functions should have one simple well-defined job
  • if function is getting too long, split to multiple functions
• convert tabs to 4 spaces
  • Preferences → Settings
  • make sure "translate_tabs_to_spaces": true is on the right
  • separate different options with commas
• add current working folder in Sublime sidebar
  • Sublime Text → Add Folder to Project → (select your folder)
• bottom-up programming
• top-down programming, a.k.a., "wishful thinking", to know what tools you'll probably need
• use asserts for sanity check
• unit testing
  • add asserts for the given examples, as well as more examples you can come up with
  • dedicate a section of code for the unit tests
  • think of typical and atypical cases, edge cases, extreme cases
  • tester wants to break the program
• test-driven development—try to add tests to each function even before implementing them
• separate I/O part from main logic part
• EAFP — it is Easier to Ask for Forgiveness than Permission
  • don't check conditions before doing something; just do it, and then handle the case when it doesn't work
• avoid mutable global variables if possible