"""Lecture 12 examples""" from __future__ import annotations from typing import Any class _Vertex: """A vertex in a graph. Instance Attributes: - item: The data stored in this vertex. - neighbours: The vertices that are adjacent to this vertex. Representation Invariants: - self not in self.neighbours - all(self in u.neighbours for u in self.neighbours) """ item: Any neighbours: set[_Vertex] def __init__(self, item: Any, neighbours: set[_Vertex]) -> None: """Initialize a new vertex with the given item and neighbours.""" self.item = item self.neighbours = neighbours def check_connected(self, target_item: Any, visited: set[_Vertex]) -> bool: """Return whether this vertex is connected to a vertex corresponding to target_item, WITHOUT using any of the vertices in visited. """ if self.item == target_item: return True else: # Does there exist a neighbour u of self such that # u and target_item are connected? # Note: the mutating and non-mutating versions are both logically correct for # this method (see Course Notes for details). But, it's good to understand why, # because there may be cases (in other functions) where you need to use just one. visited.add(self) # new_visited = set.union(visited, {self}) for u in self.neighbours: if u not in visited: if u.check_connected(target_item, visited): return True return False # Alternate, using a comprehension # return any(u.check_connected(target_item, visited) for u in self.neighbours) class Graph: """A graph. Representation Invariants: - all(item == self._vertices[item].item for item in self._vertices) """ # Private Instance Attributes: # - _vertices: # A collection of the vertices contained in this graph. # Maps item to _Vertex object. _vertices: dict[Any, _Vertex] def __init__(self) -> None: """Initialize an empty graph (no vertices or edges).""" self._vertices = {} def add_vertex(self, item: Any) -> None: """Add a vertex with the given item to this graph. The new vertex is not adjacent to any other vertices. Preconditions: - item not in self._vertices """ # 1. Create a new _Vertex new_vertex = _Vertex(item, set()) # 2. Add the _Vertex to self._vertices self._vertices[item] = new_vertex def add_edge(self, item1: Any, item2: Any) -> None: """Add an edge between the two vertices with the given items in this graph. Raise a ValueError if item1 or item2 do not appear as vertices in this graph. Preconditions: - item1 != item2 """ if item1 in self._vertices and item2 in self._vertices: # Add the edge between the two vertices v1 = self._vertices[item1] v2 = self._vertices[item2] v1.neighbours.add(v2) v2.neighbours.add(v1) else: raise ValueError def adjacent(self, item1: Any, item2: Any) -> bool: """Return whether item1 and item2 are adjacent vertices in this graph. Return False if item1 or item2 do not appear as vertices in this graph. """ # This is version given in the Course Notes, Section 17.3 # But it is possible to write a simpler version! if item1 in self._vertices and item2 in self._vertices: v1 = self._vertices[item1] return any(v2.item == item2 for v2 in v1.neighbours) else: return False def get_neighbours(self, item: Any) -> set: """Return a set of the neighbours of the given item. Note that the *items* are returned, not the _Vertex objects themselves. Raise a ValueError if item does not appear as a vertex in this graph. """ if item in self._vertices: v = self._vertices[item] return {neighbour.item for neighbour in v.neighbours} else: raise ValueError def num_edges(self) -> int: """Return the number of edges in this graph.""" # Calculate the sum of the vertex degrees sum_so_far = 0 # for vertex in self._vertices.values(): for item in self._vertices: vertex = self._vertices[item] sum_so_far += len(vertex.neighbours) return sum_so_far // 2 # Or, using a comprehension # sum_degrees = sum(len(self._vertices[item].neighbours) # for item in self._vertices) def connected(self, item1: Any, item2: Any) -> bool: """Return whether item1 and item2 are connected vertices in this graph. Return False if item1 or item2 do not appear as vertices in this graph. """ if item1 in self._vertices and item2 in self._vertices: v1 = self._vertices[item1] return v1.check_connected(item2, set()) else: return False def complete_graph(n: int) -> Graph: graph_so_far = Graph() for i in range(0, n): # Add new vertex for i graph_so_far.add_vertex(i) # Add edges to all previous vertices (0 <= j < i) for j in range(0, i): graph_so_far.add_edge(i, j) # Alternate (adding vertices and edges separately) # Add all vertices first for i in range(0, n): # Add new vertex for i graph_so_far.add_vertex(i) # Add all edges for i in range(0, n): # Add edges to all previous vertices (0 <= j < i) for j in range(0, i): graph_so_far.add_edge(i, j) return graph_so_far if __name__ == '__main__': # NOTE: In PyCharm, the RecursionError will only appear if you "Run file", # but NOT if you do "Run File in Python Console". g = Graph() g.add_vertex(1) g.add_vertex(2) g.add_vertex(3) g.add_edge(1, 2) print(g.connected(1, 3)) """CSC111 Lecture 14 Examples""" from __future__ import annotations from typing import Any class _Vertex: """A vertex in a graph. Instance Attributes: - item: The data stored in this vertex. - neighbours: The vertices that are adjacent to this vertex. Representation Invariants: - self not in self.neighbours - all(self in u.neighbours for u in self.neighbours) """ item: Any neighbours: set[_Vertex] def __init__(self, item: Any, neighbours: set[_Vertex]) -> None: """Initialize a new vertex with the given item and neighbours.""" self.item = item self.neighbours = neighbours def check_connected(self, target_item: Any, visited: set[_Vertex]) -> bool: """Return whether this vertex is connected to a vertex corresponding to target_item, by a path that DOES NOT use any vertex in visited. Preconditions: - self not in visited """ if self.item == target_item: return True else: visited.add(self) # (for loop version) for u in self.neighbours: if u not in visited: if u.check_connected(target_item, visited): return True return False def get_spanning_tree(self, visited: set[_Vertex]) -> list[set]: """Return a spanning tree for all items this vertex is connected to, WITHOUT using any of the vertices in visited. Preconditions: - self not in visited """ visited.add(self) # NOTE: the "make a copy version" does *not* work in this method, # as we need to ensure each vertex is recursed on just once # new_visited = visited.union({self}) edges_so_far = [] for u in self.neighbours: if u not in visited: edges_so_far.append({self.item, u.item}) edges_so_far.extend(u.get_spanning_tree(visited)) return edges_so_far class Graph: """A graph. >>> graph = Graph() >>> graph.add_vertex(4) >>> graph.add_vertex(5) >>> graph.add_vertex(2) >>> graph.add_vertex(6) >>> graph.add_edge(4, 5) >>> graph.add_edge(4, 2) >>> graph.add_edge(2, 6) Representation Invariants: (COMPLETE FOR HOMEWORK) - for each key in self._vertices, the corresponding vertex's item attribute equals that key """ # Private Instance Attributes: # - _vertices: # A collection of the vertices contained in this graph. # Maps item to _Vertex object. _vertices: dict[Any, _Vertex] def __init__(self) -> None: """Initialize an empty graph (no vertices or edges).""" self._vertices = {} def add_vertex(self, item: Any) -> None: """Add a vertex with the given item to this graph. The new vertex is not adjacent to any other vertices. Preconditions: - item not in self._vertices """ # 1. Create a new _Vertex new_vertex = _Vertex(item, set()) # 2. Add the _Vertex to self._vertices self._vertices[item] = new_vertex def add_edge(self, item1: Any, item2: Any) -> None: """Add an edge between the two vertices with the given items in this graph. Raise a ValueError if item1 or item2 do not appear as vertices in this graph. Preconditions: - item1 != item2 """ if item1 in self._vertices and item2 in self._vertices: # Add the edge between the two vertices v1 = self._vertices[item1] v2 = self._vertices[item2] v1.neighbours.add(v2) v2.neighbours.add(v1) else: raise ValueError def adjacent(self, item1: Any, item2: Any) -> bool: """Return whether item1 and item2 are adjacent vertices in this graph. Return False if item1 or item2 do not appear as vertices in this graph. """ # This is version given in the Course Notes, Section 15.3 # But it is possible to write a simpler version! if item1 in self._vertices and item2 in self._vertices: v1 = self._vertices[item1] return any(v2.item == item2 for v2 in v1.neighbours) else: return False def num_edges(self) -> int: """Return the number of edges in this graph.""" # Calculate the sum of the vertex degrees total_degree = sum(len(self._vertices[item].neighbours) # This is the degree of one vertex for item in self._vertices) return total_degree // 2 def connected(self, item1: Any, item2: Any) -> bool: """Return whether item1 and item2 are connected vertices in this graph. Return False if item1 or item2 do not appear as vertices in this graph. """ if item1 in self._vertices and item2 in self._vertices: v1 = self._vertices[item1] # v2 = self._vertices[item2] return v1.check_connected(item2, set()) else: return False def spanning_tree(self) -> list[set]: """Return a subset of the edges of this graph that form a spanning tree. The edges are returned as a list of sets, where each set contains the two ITEMS corresponding to an edge. Each returned edge is in this graph (i.e., this function doesn't create new edges!). Preconditions: - this graph is connected """ # How do we choose the starting vertex? all_vertices = list(self._vertices.values()) start_vertex = all_vertices[0] # Could also use random.choice(all_vertices) return start_vertex.get_spanning_tree(set()) if __name__ == '__main__': # Sample graph g = Graph() for i in range(0, 5): g.add_vertex(i) g.add_edge(0, 1) g.add_edge(0, 3) g.add_edge(1, 2) g.add_edge(1, 4) g.add_edge(2, 4) """CSC111 Lecture 16 Examples""" # Version that returns a new list (bad because it mutates # the input list!!!!) def selection_sort_simple(lst: list) -> list: """Return a sorted version of lst. >>> selection_sort_simple([5, 3, 10, 7]) [3, 5, 7, 10] """ sorted_so_far = [] while lst != []: smallest = min(lst) lst.remove(smallest) sorted_so_far.append(smallest) return sorted_so_far ############################################################################### # Selection Sort ############################################################################### def selection_sort(lst: list) -> None: """Sort the given list using the selection sort algorithm. Note that this is a *mutating* function. >>> my_list = [3, 7, 2, 5] >>> selection_sort(my_list) >>> my_list [2, 3, 5, 7] """ for i in range(0, len(lst)): # Loop invariants # - lst[:i] is sorted # - if i > 0, lst[i - 1] is less than or equal to all items in lst[i:len(lst)] # 1. Find the smallest item in the unsorted section # - actually, find the INDEX of the smallest item index_of_smallest = _min_index(lst, i) # 2. Swap the smallest item with the item at index i lst[i], lst[index_of_smallest] = lst[index_of_smallest], lst[i] def _min_index(lst: list, i: int) -> int: """Return the index of the smallest item in lst[i:]. In the case of ties, return the smaller index (i.e., the index that appears first). Preconditions: - 0 <= i <= len(lst) - 1 >>> _min_index([2, 7, 3, 5], 1) 2 >>> _min_index([2, -9999, 7, 3, 5, 100, 200, 300, 400], 1) 1 """ min_index_so_far = i for j in range(i + 1, len(lst)): if lst[j] < lst[min_index_so_far]: min_index_so_far = j return min_index_so_far ################################################################################ # Insertion sort ################################################################################ def insertion_sort(lst: list) -> None: """Sort the given list using the selection sort algorithm. Note that this is a *mutating* function. >>> my_list = [7, 3, 5, 2] >>> insertion_sort(my_list) >>> my_list [2, 3, 5, 7] """ for i in range(0, len(lst)): # Loop invariant # - lst[:i] is sorted _insert(lst, i) def _insert(lst: list, i: int) -> None: """Move lst[i] so that lst[:i + 1] is sorted. Preconditions: - 0 <= i < len(lst) - is_sorted(lst[:i]) >>> lst = [7, 3, 5, 2] >>> _insert(lst, 1) >>> lst [3, 7, 5, 2] """ # Version 1, using an early return for j in range(i, 0, -1): # This goes from i down to 1 if lst[j - 1] <= lst[j]: # The element has been inserted into the correct position! return else: # Swap lst[j - 1] and lst[j] lst[j - 1], lst[j] = lst[j], lst[j - 1] # Version 2, using a compound loop condition # j = i # while not (j == 0 or lst[j - 1] <= lst[j]): # stopping condition version # while j > 0 and lst[j - 1] > lst[j]: # continue condition version # # # Swap lst[j - 1] and lst[j] # lst[j - 1], lst[j] = lst[j], lst[j - 1] # # j = j - 1 # Version 3: Use binary search to find the right index to insert lst[i] into # (Problem: but still need to do the swapping!) # Version 4: Use cycle (from the prep) if __name__ == '__main__': import doctest doctest.testmod(verbose=True) """CSC111 Lecture 17 Examples""" from typing import Callable, Optional ################################################################################ # Insertion sort ################################################################################ def insertion_sort(lst: list) -> None: """Sort the given list using the insertion sort algorithm. Note that this is a *mutating* function. >>> my_list = [7, 3, 5, 2] >>> insertion_sort(my_list) >>> my_list [2, 3, 5, 7] """ for i in range(0, len(lst)): # Loop invariant # - lst[:i] is sorted _insert(lst, i) def _insert(lst: list, i: int) -> None: """Move lst[i] so that lst[:i + 1] is sorted. Preconditions: - 0 <= i < len(lst) - is_sorted(lst[:i]) >>> lst = [7, 3, 5, 2] >>> _insert(lst, 1) >>> lst [3, 7, 5, 2] """ # Version 1, using an early return for j in range(i, 0, -1): # This goes from i down to 1 if lst[j - 1] <= lst[j]: # The element has been inserted into the correct position! return else: # Swap lst[j - 1] and lst[j] lst[j - 1], lst[j] = lst[j], lst[j - 1] ############################################################################### # Sorting by length ############################################################################### def sort_by_len(lst: list[str]) -> None: """Sort the given list of strings by their length. >>> lst = ['david', 'is', 'cool', 'indeed'] >>> sort_by_len(lst) >>> lst ['is', 'cool', 'david', 'indeed'] """ insertion_sort_by_len(lst) def insertion_sort_by_len(lst: list) -> None: """Sort lst by the length of each element, using insertion sort.""" for i in range(0, len(lst)): _insert_by_len(lst, i) def _insert_by_len(lst: list, i: int) -> None: """Move lst[i] so that lst[:i + 1] is sorted by the length of each element. """ for j in range(i, 0, -1): if len(lst[j - 1]) <= len(lst[j]): # This line has changed! return else: lst[j - 1], lst[j] = lst[j], lst[j - 1] def insertion_sort_by_sum(lst: list) -> None: """Sort lst by the sum of each element, using insertion sort.""" for i in range(0, len(lst)): _insert_by_sum(lst, i) def _insert_by_sum(lst: list, i: int) -> None: """Move lst[i] so that lst[:i + 1] is sorted by the sum of each element. """ for j in range(i, 0, -1): if sum(lst[j - 1]) <= sum(lst[j]): # This line has changed! return else: lst[j - 1], lst[j] = lst[j], lst[j - 1] ############################################################################### # Generalized sorting ############################################################################### def insertion_sort_by_key(lst: list, key: Optional[Callable] = None) -> None: """Sort the given list using the insertion sort algorithm. If key is not None, sort the items by their corresponding return value when passed to key. """ print(id(key)) # Try this out at home for i in range(0, len(lst)): _insert_by_key(lst, i, key) def _insert_by_key(lst: list, i: int, key: Optional[Callable] = None) -> None: """Move lst[i] so that lst[:i + 1] is sorted. If key is not None, sort the items by their corresponding return value when passed to key. Precondition: - key is a single-argument function that can be called on every element of lst without error """ if key is None: for j in range(i, 0, -1): # This goes from i down to 1 if lst[j - 1] <= lst[j]: # The element has been inserted into the correct position! return else: # Swap lst[j - 1] and lst[j] lst[j - 1], lst[j] = lst[j], lst[j - 1] else: # key is a function that we should use to compare values for j in range(i, 0, -1): # This goes from i down to 1 if key(lst[j - 1]) <= key(lst[j]): # The element has been inserted into the correct position! return else: # Swap lst[j - 1] and lst[j] lst[j - 1], lst[j] = lst[j], lst[j - 1] def count_a(s: str) -> int: return s.count('a') if __name__ == '__main__': import doctest doctest.testmod(verbose=True) """CSC111 Lecture 18 Examples""" from typing import Any def mergesort(lst: list) -> list: """Return a new sorted list with the same elements as lst. This is a *non-mutating* version of mergesort; it does not mutate the input list. >>> mergesort([10, 2, 5, -6, 17, 10]) [-6, 2, 5, 10, 10, 17] """ if len(lst) < 2: return lst.copy() # Use the list.copy method to return a new list object else: # Divide the list into two parts, and sort them recursively. mid = len(lst) // 2 left_sorted = mergesort(lst[:mid]) right_sorted = mergesort(lst[mid:]) # Merge the two sorted halves. Using a helper here! return _merge(left_sorted, right_sorted) def _merge(lst1: list, lst2: list) -> list: """Return a sorted list with the elements in lst1 and lst2. Preconditions: - is_sorted(lst1) - is_sorted(lst2) >>> _merge([-1, 3, 7, 10], [-3, 0, 2, 6]) [-3, -1, 0, 2, 3, 6, 7, 10] """ i1, i2 = 0, 0 sorted_so_far = [] while i1 < len(lst1) and i2 < len(lst2): # Loop invariant: # sorted_so_far is a merged version of lst1[:i1] and lst2[:i2] assert sorted_so_far == sorted(lst1[:i1] + lst2[:i2]) if lst1[i1] <= lst2[i2]: sorted_so_far.append(lst1[i1]) i1 += 1 else: sorted_so_far.append(lst2[i2]) i2 += 1 # When the loop is over, either i1 == len(lst1) or i2 == len(lst2) assert i1 == len(lst1) or i2 == len(lst2) # In either case, the remaining unmerged elements can be concatenated to sorted_so_far. if i1 == len(lst1): return sorted_so_far + lst2[i2:] else: return sorted_so_far + lst1[i1:] def quicksort(lst: list) -> list: """Return a sorted list with the same elements as lst. This is a *non-mutating* version of quicksort; it does not mutate the input list. >>> quicksort([10, 2, 5, -6, 17, 10]) [-6, 2, 5, 10, 10, 17] """ if len(lst) < 2: return lst.copy() else: # 1. Divide the list into two parts pivot = lst[0] smaller, bigger = _partition(lst[1:], pivot) # 2. Sort each part recursively smaller_sorted = quicksort(smaller) bigger_sorted = quicksort(bigger) # 3. Combine the sorted parts return smaller_sorted + [pivot] + bigger_sorted def _partition(lst: list, pivot: Any) -> tuple[list, list]: """Return a partition of lst with the chosen pivot. Return two lists, where the first contains the items in lst that are <= pivot, and the second contains the items in lst that are > pivot. """ smaller = [] bigger = [] for item in lst: if item <= pivot: smaller.append(item) else: bigger.append(item) return (smaller, bigger) ################################################################################ # In-place quicksort ################################################################################ def _in_place_partition(lst: list) -> None: """Mutate lst so that it is partitioned with pivot lst[0]. Let pivot = lst[0]. The elements of lst are moved around so that lst looks like [x1, x2, ... x_m, pivot, y1, y2, ... y_n], where each of the x's is <= pivot, and each of the y's is > pivot. >>> lst = [10, 3, 20, 5, 16, 30, 7, 100] >>> _in_place_partition(lst) # pivot is 10 >>> lst[3] # the 10 is now at index 3 10 >>> set(lst[:3]) == {3, 5, 7} True >>> set(lst[4:]) == {16, 20, 30, 100} True """ pivot = lst[0] small_i = 1 big_i = len(lst) while small_i < big_i: # while not (small_i == big_i): # Loop invariants assert all(lst[j] <= pivot for j in range(1, small_i)) assert all(lst[j] > pivot for j in range(big_i, len(lst))) if lst[small_i] <= pivot: # Increase the "smaller" partition small_i += 1 else: # lst[small_i] > pivot lst[small_i], lst[big_i - 1] = lst[big_i - 1], lst[small_i] big_i -= 1 # Move the pivot to between the "smaller" and "bigger" parts lst[0], lst[small_i - 1] = lst[small_i - 1], lst[0] def in_place_quicksort(lst: list) -> None: """Sort the given list using the quicksort algorithm. """ _in_place_quicksort(lst, 0, len(lst)) def _in_place_quicksort(lst: list, b: int, e: int) -> None: """Sort the sublist lst[b:e] using the quicksort algorithm. Preconditions: - 0 <= b <= e <= len(lst) """ if e - b < 2: # Do nothing; lst[b:e] is already sorted pass else: # Partition lst[b:e] pivot_index = _in_place_partition_indexed(lst, b, e) # Recursively sort each partition _in_place_quicksort(lst, b, pivot_index) # smaller partition _in_place_quicksort(lst, pivot_index + 1, e) # bigger partition def _in_place_partition_indexed(lst: list, b: int, e: int) -> int: """Mutate lst[b:e] so that it is partitioned with pivot lst[b]. Return the new index of the pivot. Notes: - Only elements in lst[b:e] are rearranged. - _in_place_partition_indexed(lst, 0, len(lst)) is equivalent to _in_place_partition(lst), with an additional return value Preconditions: - 0 <= b < e <= len(lst) >>> my_lst = [10, 13, 20, 5, 16, 30, 7, 100] >>> my_pivot_index = _in_place_partition_indexed(my_lst, 1, 6) # pivot is 13 >>> my_pivot_index # pivot is now at index 2 2 >>> my_lst[my_pivot_index] 13 >>> set(my_lst[1:my_pivot_index]) == {5} True >>> set(my_lst[my_pivot_index + 1:6]) == {16, 20, 30} True >>> my_lst[:1] [10] >>> my_lst[6:] [7, 100] """ pivot = lst[b] small_i = b + 1 big_i = e while small_i < big_i: # while not (small_i == big_i): # Loop invariants (homework: update loop invariants to use b and e) # assert all(lst[j] <= pivot for j in range(1, small_i)) # assert all(lst[j] > pivot for j in range(big_i, len(lst))) if lst[small_i] <= pivot: # Increase the "smaller" partition small_i += 1 else: # lst[small_i] > pivot # Swap lst[small_i] to back and increase the "bigger" partition lst[small_i], lst[big_i - 1] = lst[big_i - 1], lst[small_i] big_i -= 1 # Move the pivot to between the "smaller" and "bigger" parts lst[b], lst[small_i - 1] = lst[small_i - 1], lst[b] # Return the new index of the pivot return small_i - 1 if __name__ == '__main__': import doctest doctest.testmod(verbose=False) """CSC111 Lecture 19 Examples""" from copy import copy import random import timeit from typing import Any, Callable, Optional import plotly.graph_objects as go from ... import selection_sort, insertion_sort, mergesort, quicksort, in_place_quicksort # You'll need to fill this in with your code ############################################################################### # Profiling (i.e., timing experiments) of sorting algorithms ############################################################################### NUM_TRIALS = 3 def profile_alg(sizes: list[int], alg: Callable[[list], Any], shuffle: bool = True) -> list[float]: """Return a list of times for the given sorting algorithms.""" times = [] for size in sizes: print(f'Profiling {alg.__qualname__} for list size {size}.') for _ in range(NUM_TRIALS): lst = list(range(size)) if shuffle: random.shuffle(lst) time = min(timeit.repeat('lst1 = copy(lst); alg(lst1)', repeat=10, number=1, globals={'copy': copy, **locals()})) times.append(time) return times def generate_images(sizes: list[int], shuffle: bool = True, prefix: str = 'running-times') -> None: """Generate images comparing selection sort, insertion sort, mergesort, and quicksort (both mutating and non-mutating), and list.sort. """ funcs = [selection_sort, insertion_sort, mergesort, quicksort, in_place_quicksort, list.sort] all_times = { func.__qualname__: profile_alg(sizes, func, shuffle=shuffle) for func in funcs } all_sizes = [x for x in sizes for _ in range(NUM_TRIALS)] comparisons = [ funcs[:-1], funcs[2:-1], funcs[2:], [insertion_sort, mergesort, in_place_quicksort] ] for i, comparison in enumerate(comparisons): fig = go.Figure() for f in comparison: alg = f.__qualname__ times = all_times[alg] fig.add_trace(go.Scatter(x=all_sizes, y=times, mode='markers', name=alg, marker={ 'size': 12, 'symbol': str(funcs.index(f) + 1) })) list_label = 'Random Lists' if shuffle else 'Sorted Lists' fig.update_layout(title_text=f'Sorting Algorithm Running Times ({list_label})') fig.update_xaxes(title_text='Size of list') fig.update_yaxes(title_text='Time (s)') fig.write_image(f'{prefix}-{i}.svg', width=800) ############################################################################### # Generalized sorting ############################################################################### def insertion_sort_by_key(lst: list, key: Optional[Callable] = None) -> None: """Sort the given list using the insertion sort algorithm. If key is not None, sort the items by their corresponding return value when passed to key. """ print(id(key)) # Try this out at home for i in range(0, len(lst)): _insert_by_key(lst, i, key) ############################################################################### # Memoized insertion sort ############################################################################### def insertion_sort_memoized(lst: list, key: Optional[Callable] = None) -> None: """...""" # Initialize a dictionary to store the results of calling `key` key_values = {} for i in range(0, len(lst)): _insert_memoized(lst, i, key, key_values) def _insert_memoized(lst: list, i: int, key: Optional[Callable] = None, key_values: Optional[dict] = None) -> None: """Same as _insert_by_key, except that: When key(x) should be computed, first look up x in key_values. - If x is in key_values, return the corresponding values - Otherwise, compute key(x) and store the result in key_values """ for j in range(i, 0, -1): # This goes from i down to 1 if key is None: if lst[j - 1] <= lst[j]: # The element has been inserted into the correct position! return else: # Swap lst[j - 1] and lst[j] lst[j - 1], lst[j] = lst[j], lst[j - 1] else: # key is a function that we should use to compare values # Get the key values (this is the part you need to change k1 = key(lst[j - 1]) k2 = key(lst[j]) # Then do the swapping. if k1 <= k2: # The element has been inserted into the correct position! return else: # Swap lst[j - 1] and lst[j] lst[j - 1], lst[j] = lst[j], lst[j - 1] if __name__ == '__main__': import doctest doctest.testmod(verbose=True) # For the sorting algorithm profiling import sys sys.setrecursionlimit(20000) LIST_SIZES = [1000 * i for i in range(1, 11)] # Try either one of the following # generate_images(LIST_SIZES, shuffle=True) # generate_images(LIST_SIZES, shuffle=False, prefix='running-times-sorted') """CSC111 Lecture 20 Examples""" from __future__ import annotations from typing import Any, Optional class Statement: """An abstract class representing a Python statement. """ def evaluate(self, env: dict[str, Any]) -> Optional[Any]: """Evaluate this statement with the given environment. """ raise NotImplementedError class Expr: """An abstract class representing a Python expression. """ def evaluate(self, env: dict[str, Any]) -> Any: """Evaluate this expression with the given environment. """ raise NotImplementedError class Num(Expr): """A numeric literal. Instance Attributes: - n: the value of the literal """ n: int | float def __init__(self, number: int | float) -> None: """Initialize a new numeric literal.""" self.n = number def evaluate(self, env: dict[str, Any]) -> Any: """Return the *value* of this expression using the given variable environment. The returned value should the result of how this expression would be evaluated by the Python interpreter. >>> expr = Num(10.5) >>> expr.evaluate({}) 10.5 """ return self.n # Simply return the value itself! def __str__(self) -> str: """Return a string representation of this expression. One feature we'll stick with for all Expr subclasses here is that we'll want to return a string that is valid Python code representing the same expression. >>> str(Num(5)) '5' """ return str(self.n) class BinOp(Expr): """An arithmetic binary operation. Instance Attributes: - left: the left operand - op: the name of the operator - right: the right operand Representation Invariants: - self.op in {'+', '*'} """ left: Expr op: str right: Expr def __init__(self, left: Expr, op: str, right: Expr) -> None: """Initialize a new binary operation expression. Preconditions: - op in {'+', '*'} """ self.left = left self.op = op self.right = right def evaluate(self, env: dict[str, Any]) -> Any: left_val = self.left.evaluate(env) right_val = self.right.evaluate(env) if self.op == '+': return left_val + right_val elif self.op == '*': return left_val * right_val else: # We shouldn't reach this branch because of our representation invariant raise ValueError(f'Invalid operator {self.op}') def __str__(self) -> str: """Return a string representation of this expression. """ return f'({str(self.left)} {self.op} {str(self.right)})' # YEHYUN class Bool(Expr): """A boolean literal. Instance Attributes: - b: the value of the literal """ b: bool def __init__(self, b: bool) -> None: """Initialize a new boolean literal.""" self.b = b def evaluate(self) -> Any: """Return the *value* of this expression. The returned value should the result of how this expression would be evaluated by the Python interpreter. >>> expr = Bool(True) >>> expr.evaluate() True """ return self.b def __str__(self) -> str: """Return a string representation of this expression. """ return str(self.b) # YEHYUN class BoolOp(Expr): """A boolean operation. Represents either a sequence of `and`s or a sequence of `or`s. Unlike BinOp, this expression can contain more than two operands, each separated by SAME operator: True and False and True and False True or False or True or False Instance Attributes: - op: the name of the boolean operation - operands: a list of operands that the operation is applied to Representation Invariants: - self.op in {'and', 'or'} - len(self.operands) >= 2 - every expression in self.operands evaluates to a boolean value """ op: str operands: list[Expr] def __init__(self, op: str, operands: list[Expr]) -> None: """Initialize a new boolean operation expression. Preconditions: - op in {'and', 'or'} - len(operands) >= 2 - every expression in operands evaluates to a boolean value """ self.op = op self.operands = operands def evaluate(self) -> Any: """Return the *value* of this expression. The returned value should the result of how this expression would be evaluated by the Python interpreter. >>> expr = BoolOp('and', [Bool(True), Bool(True), Bool(False)]) >>> expr.evaluate() False """ bools = [each_bool.evaluate() for each_bool in self.operands] if self.op == 'and': return all(bools) elif self.op == 'or': return any(bools) else: raise ValueError(f'Invalid operator {self.op}') def __str__(self) -> str: """Return a string representation of this boolean expression. >>> expr = BoolOp('and', [Bool(True), Bool(True), Bool(False)]) >>> str(expr) '(True and True and False)' """ op_string = f' {self.op} ' return f'({op_string.join([str(v) for v in self.operands])})' # YEHYUN class Compare(Expr): """A sequence of comparison operations. In Python, it is possible to chain together comparison operations: x1 <= x2 < x3 <= x4 This is logically equivalent to the more explicit binary form: (x1 <= x2) and (x2 <= x3) and (x3 <= x4), except each expression (x1, x2, x3, x4) is only evaluated once. Instance Attributes: - left: The leftmost value being compared. (In the example above, this is `x1`.) - comparisons: A list of tuples, where each tuple stores an operation and expression. (In the example above, this is [(<=, x2), (<, x3), (<= x4)].) Note: for the purpose of this prep, we'll only allow the comparison operators <= and < for this class (see representation invariant below). Representation Invariants: - len(self.comparisons) >= 1 - all(comp[0] in {'<=', '<'} for comp in self.comparisons) - self.left and every expression in self.comparisons evaluate to a number value """ left: Expr comparisons: list[tuple[str, Expr]] def __init__(self, left: Expr, comparisons: list[tuple[str, Expr]]) -> None: """Initialize a new comparison expression. Preconditions: - len(comparisons) >= 1 - all(comp[0] in {'<=', '<'} for comp in comparisons) - left and every expression in comparisons evaluate to a number value """ self.left = left self.comparisons = comparisons def evaluate(self) -> Any: """Return the *value* of this expression. The returned value should the result of how this expression would be evaluated by the Python interpreter. >>> expr = Compare(Num(1), [ ... ('<=', Num(2)), ... ('<', Num(4.5)), ... ('<=', Num(4.5))]) >>> expr.evaluate() True """ left_val = self.left.evaluate() for comparison in self.comparisons: right_val = comparison[1].evaluate() if comparison[0] == '<': if not left_val < right_val: return False elif comparison[0] == '<=': if not left_val <= right_val: return False else: raise ValueError(f'Invalid operator {comparison[0]}') left_val = right_val return True def __str__(self) -> str: """Return a string representation of this comparison expression. >>> expr = Compare(Num(1), [ ... ('<=', Num(2)), ... ('<', Num(4.5)), ... ('<=', Num(4.5))]) >>> str(expr) '(1 <= 2 < 4.5 <= 4.5)' """ s = str(self.left) for operator, subexpr in self.comparisons: s += f' {operator} {str(subexpr)}' return '(' + s + ')' ############################################################################### # Variables ############################################################################### class Name(Expr): """A variable expression. Instance Attributes: - id: The variable name in this expression. """ id: str def __init__(self, id_: str) -> None: """Initialize a new variable expression.""" self.id = id_ def evaluate(self, env: dict[str, Any]) -> Any: """Return the *value* of this expression using the given variable environment. NOTE: This version raises a KeyError if self.id isn't in the given environment. The Python interpreter would raise a "NameError" instead. Try to modify the given implementation to raise a NameError in this case. """ # Do this: (assume that in env, all values are "already evaluated") if self.id in env: return env[self.id] else: raise NameError("Error!") # Don't do this: # return env[self.id].evaluate(env) class Assign(Statement): """An assignment statement (with a single target). Instance Attributes: - target: the variable name on the left-hand side of the = sign - value: the expression on the right-hand side of the = sign """ target: str value: Expr def __init__(self, target: str, value: Expr) -> None: """Initialize a new Assign node.""" self.target = target self.value = value def evaluate(self, env: dict[str, Any]) -> None: """Evaluate this statement. This does the following: evaluate the right-hand side expression, and then update <env> to store a binding between this statement's target and the corresponding value. """ # 1. Evaluate the right-hand side evaluated_value = self.value.evaluate(env) # 2. Update <env> to store the new binding env[self.target] = evaluated_value ############################################################################### # Compound statements ############################################################################### class Module: """A class representing a full Python program. Instance Attributes: - body: A sequence of statements. """ body: list[Statement] def __init__(self, body: list[Statement]) -> None: """Initialize a new module with the given body.""" self.body = body def evaluate(self) -> None: """Evaluate this module. """ env = {} for statement in self.body: statement.evaluate(env) class Print(Statement): """A statement representing a call to the `print` function. Instance Attributes: - argument: The argument expression to the `print` function. """ argument: Expr def __init__(self, argument: Expr) -> None: """Initialize a new Print node.""" self.argument = argument def evaluate(self, env: dict[str, Any]) -> None: """Evaluate this statement. This evaluates the argument of the print call, and then actually prints it. Note that it doesn't return anything, since `print` doesn't return anything. """ # Instead, we could use the logging module here print(self.argument.evaluate(env)) # Alternate, with some additional text # print('Hey, I am printing:', self.argument.evaluate(env)) ############################################################################### # If statements ############################################################################### # NOTE: You'll want to copy over Bool/BoolOp/Compare from the prep to run the doctests # in this class. class If(Statement): """An if statement. This is a statement of the form: if <test>: <body> else: <orelse> Instance Attributes: - test: The condition expression of this if statement. - body: A sequence of statements to evaluate if the condition is True. - orelse: A sequence of statements to evaluate if the condition is False. (This would be empty in the case that there is no `else` block.) (Q2 solution) >>> If( ... Compare(Name('x'), [('<', Num(100))]), ... [Print(Name('x'))], ... [Assign('y', BinOp(Name('x'), '+', Num(2))), ... Assign('x', Num(1))] ... ) >>> If( ... Compare(Name('x'), [('<', Num(100))]), ... [Print(Name('x'))], ... [] ... ) """ test: Expr body: list[Statement] orelse: list[Statement] def __init__(self, test: Expr, body: list[Statement], orelse: list[Statement]) -> None: self.test = test self.body = body self.orelse = orelse def evaluate(self, env: dict[str, Any]) -> None: """Evaluate this statement. Preconditions: - self.test evaluates to a boolean >>> stmt = If(Bool(True), ... [Assign('x', Num(1))], ... [Assign('y', Num(0))]) ... >>> env = {} >>> stmt.evaluate(env) >>> env {'x': 1} """ # 1. Evaluate the test (if condition). test_val = self.test.evaluate(env) # print(f'Evaluated if condition, got {test_val}') # 2. If it's true, evaluate the statements in the body (if branch). # Otherwise, evaluate the statements in orelse (else branch). if test_val: # print(f'If condition was True, so evaluting if branch') for statement in self.body: statement.evaluate(env) else: # print(f'If condition was False, so evaluting else branch') for statement in self.orelse: statement.evaluate(env) ############################################################################### # For loops (over ranges) ############################################################################### class ForRange(Statement): """A for loop that loops over a range of numbers. for <target> in range(<start>, <stop>): <body> Instance Attributes: - target: The loop variable. - start: The start for the range (inclusive). - stop: The end of the range (this is *exclusive*, so <stop> is not included in the loop). - body: The statements to execute in the loop body. Q2: >>> assign = Assign('sum_so_far', BinOp(Name('sum_so_far'), '+', Name('n'))) >>> Module([ ... Assign('sum_so_far', Num(0)), ... ForRange('n', Num(1), Num(10), ... [assign]), ... Print(Name('sum_so_far')) ... ]) """ target: str start: Expr stop: Expr body: list[Statement] def __init__(self, target: str, start: Expr, stop: Expr, body: list[Statement]) -> None: """Initialize a new ForRange node.""" self.target = target self.start = start self.stop = stop self.body = body def evaluate(self, env: dict[str, Any]) -> None: """Evaluate this statement. >>> statement = ForRange('x', Num(1), BinOp(Num(2), '+', Num(3)), ... [Print(Name('x'))]) >>> statement.evaluate({}) 1 2 3 4 """ # 1. Evaluate start and stop start_value = self.start.evaluate(env) stop_value = self.stop.evaluate(env) for i in range(start_value, stop_value): # 2. Assign a new variable <target> to the value of <start>. env[self.target] = i Assign(self.target, Num(i)).evaluate(env) # 3. Execute the <body> statement(s). for statement in self.body: statement.evaluate(env)