Kernel: SageMath (system-wide)
In [1]:
import math import random import functools # ''' # ---====================--- # Begin Helper Methods # ---====================--- # ''' def merge(arr, l, m, r, cmp, reverse): cmp_helper = cmp if reverse: cmp_helper = lambda a, b: not cmp(a, b) left_midpoint = m - l + 1 right_midpoint = r - m temp_arr_left = [arr[l + i] for i in range(left_midpoint)] temp_arr_right = [arr[m + 1 + i] for i in range(right_midpoint)] i = 0 j = 0 k = l while i < left_midpoint and j < right_midpoint: if cmp_helper(temp_arr_left[i], temp_arr_right[j]): arr[k] = temp_arr_left[i] i += 1 else: arr[k] = temp_arr_right[j] j += 1 k += 1 while i < left_midpoint: arr[k] = temp_arr_left[i] i += 1 k += 1 while j < right_midpoint: arr[k] = temp_arr_right[j] j += 1 k += 1 def merge_sort(arr, left_index=None, right_index=None, cmp=lambda a, b: a < b, reverse=False): if left_index is None: left_index = 0 if right_index is None: right_index = len(arr) - 1 if left_index < right_index: midpoint = math.floor((left_index + right_index - 1)/2) merge_sort(arr, left_index, midpoint, cmp, reverse) merge_sort(arr, midpoint + 1, right_index, cmp, reverse) merge(arr, left_index, midpoint, right_index, cmp, reverse) def css_classes(): ''' pseudo-css-class generator!! dictionary mapping { pseudo-classname: inline-style } ''' classes = { 'border-light': 'border: 1px solid #a0aec0;', 'text-light': 'color: #e6fffa;', 'text-dark': 'color: #cbd5e0;', 'rounded': 'border-radius: 3px;', 'bg-dark': 'background-color: #1a202c;', 'w-max': 'width: max-content;', 'flex': 'display: flex;', 'block': 'display: block;', 'justify-between': 'justify-content: space-between;', 'text-center': 'text-align: center;', } spacings = range(0, 12) scale_factor = 1.6 # note, cocalc uses rootFontSize=10px, I want to pretend it's 16px scale_rem = lambda x: str(round(x * scale_factor, 3)) text_prefixes = 'xs sm base lg xl 2xl 3xl 4xl 5xl 6xl'.split() text_rem_sizes = [0.75, 0.875, 1, 1.125, 1.25, 1.5, 1.875, 2.25, 3, 4] classes.update({'text-{}'.format(text_prefixes[i]): 'font-size: {}rem;'.format(scale_rem(text_rem_sizes[i])) for i in range(len(text_prefixes))}) spacing_opts = { 'l': ['left: '], 'r': ['right: '], 't': ['top: '], 'b': ['bottom: '] } spacing_opts.update({ 'x': spacing_opts['l'] + spacing_opts['r'], 'y': spacing_opts['t'] + spacing_opts['b'] }) spacing_opts[''] = spacing_opts['x'] + spacing_opts['y'] for spacing in spacings: space = str(round(spacing * 0.25, 2)) + 'rem; ' for variant in ["margin", "padding"]: for prefix, rule_list in spacing_opts.items(): classes[variant[0] + prefix + '-' + str(spacing)] = "".join([variant + "-" + rule + space for rule in rule_list]) return classes def apply_classes(raw_html, classes=None): ''' pseudo-css-class injector!! note, doesn't actually support bem cause Im not caring about uniqueness (ie. card__header can be affected by card) params: - raw_html: string containing html!! - classes: object mapping classes to further either standard class names or inline styles (simulates @apply behavior from tw) ''' if classes is not None: for k, v in classes.items(): raw_html = raw_html.replace(k, v) rules = css_classes() for rule, definition in rules.items(): raw_html = raw_html.replace(rule, definition) return raw_html def assignment_html(exernum, assignment, funcs=None, params=None): ''' returns html for the assignment definition! func=[{ 'name': 'listswitch(lis, i, k)', 'params': ['lis: some list', 'i: index', 'k: index'], 'returns': ['lis with indices i and k switched'] }], params: - exernum: number of the exercise - assignment: problem statement - func: optional list of dictionaries describing functions. needs the following key-value pairs - name: <string> - params: <list<string>> - returns: <list<string>> - params: optional list of interactive inputs ''' res = ''' <div style="margin: 4rem 0;"> <h1>Exercise {}</h1> <p><b>Assignment:</b> {}</p> '''.format(exernum, assignment) if funcs: for func in funcs: res += '<p><b>Function:</b><code style="block mt-4 ml-4">{}</code></p>'.format(func.get('name', '')) if 'params' in func: res += '<div style="ml-4"><i>params:</i><ul>' for param in func['params']: res += "<li>{}</li>".format(param) res += "</ul></div>" if 'returns' in func: res += '<div style="ml-4"><i>returns:</i><ul>' for param in func['returns']: res += "<li>{}</li>".format(param) res += "</ul></div>" if params: res += "<p><b>Interactive input:</b></p><ul>" for param in params: res += "<li>{}</li>".format(param) res += "</ul>" res += '</div>' return apply_classes(res) def plot_arr(arr): ''' helper for show so that we can pass lists ''' return functools.reduce(lambda a,b : a + b, arr) def show_all(arr): ''' helper for show so that we can pass lists ''' for el in arr: show(el) def dist(point_a, point_b): ''' helper to give distance between two points of equal dimension params: - point_a: tuple for point a - point_b: tuple for point b ''' return sum([(a - b) ** 2 for a, b in zip(point_a, point_b)]) ** 0.5 def all_indices(arr, el): ''' helper to give all indices of an element in an array ''' return [i for i in range(len(arr)) if arr[i] == el] def random_list(length, min_val=0, max_val=20): ''' makes a random list ''' return [random.randint(min_val, max_val) for _ in range(length)] def arr_cmp(arr, cmp=lambda a, b: a < b, reverse=False): ''' min/max helper with comparison function params: - arr: array - amp: comparison function - reverse: order of results returns extreme of arr according to cmp ''' cmp_helper = cmp if reverse: cmp_helper = lambda a, b: not cmp(a, b) if len(arr) == 0: return None # maybe should raise an exception, not sure res = arr[0] for el in arr: if cmp_helper(el, res): res = el return res def assignment(definition, func): ''' assignment runner ''' definition() interact(func) def ccw(a, b, c): """ determines if three points are clockwise, counterclockwise, or colinear """ area2 = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]) if (area2 < 0): return -1 # clockwise elif (area2 > 0): return 1 # counterclockwise else: return 0 # colinear def draw_polygon(points, arrows=False, plot=False): # annoying, but arrow takes two points and line takes a list, so we wrap in a list and unpack connector = arrow if arrows else line inject_points = lambda arr: arr if arrows else [arr] res = [ point(a, rgbcolor="blue", size=30) + text(i, (a[0] + 0.1, a[1] + 0.1), horizontal_alignment='left', color='green') + connector(*inject_points([points[i-1], points[i]]), rgbcolor="red") for i, a in enumerate(points)] if plot: show(plot_arr(res), figsize=[5,5]) else: return res random_points = lambda n, min_val=0, max_val=10: [(random.randint(min_val, max_val), random.randint(min_val, max_val)) for _ in range(n)] # necessary globals for auto-labelling labels = 'a b c d e f g h i j k l'.split() current_label = 0 class inputs: def __init__(self): pass @staticmethod def radio(val=[0, 1], label='selector'): return selector(val, label=label) @staticmethod def box(val=None, label='input'): return input_box(default=str(val), label=label) @staticmethod def num(num=None, label=None, min_val=-10, max_val=10): global current_label global labels if not num: num = random.randint(min_val, max_val) if label in labels: # reset current_label current_label = labels.index(label) + 1 if not label: # allow auto-labelling in alphabetical order label = labels[current_label] current_label += 1 if current_label >= len(labels): current_label = 0 return input_box(default=num, label=label) @staticmethod def arr(num=None, label='arr', min_val=-10, max_val=10): if not num: num = random.randint(3, 10) return input_box(default=str(random_list(num, min_val, max_val)), label=label) @staticmethod def switch(val=False, label='show'): return (label, val) # ''' # ---========================--- # End Helper Methods # -------- # Begin Assignment Defs # ---========================--- # ''' # 2.4.1, 2.4.2, 2.4.3 assignment_defs = { '2.4.1': lambda: html(assignment_html( '2.4.1', 'Make a function that takes four points in the plane and tests if the line through the first two points intersects the line segment with endpoints the second two points, and plot the line and line segment.', funcs=[{ 'name': 'line_intersects_line_segment(a1, a2, b1, b2)', 'params': [ 'a1, a2: points defining a line', 'b1, b2: line segment endpoints', ], 'returns': [ '1: intersects', '0: intersects at an endpoint', '-1: does not intersect' ] }], params=['(a) A list of four points in the plane.'] )), '2.4.2': lambda: html(assignment_html( '2.4.2', 'Make a function that takes four points in the plane and returns the intersection of the line through the first two points and the line segment with endpoints the second two points (assuming that there is an intersection), and plot the line and line segment. Have the interactive output give an error message if there is no intersection.', funcs=[{ 'name': 'line_intersection_line_segment(a1, a2, b1, b2)', 'params': [ 'a1, a2: points defining a line', 'b1, b2: line segment endpoints', ], 'returns': [ "Returns the intersection of the line through (a1, a2) and the line segment with endpoints (b1, b2)." ] }], params=['(a) A list of four points in the plane.'] )), '2.4.2': lambda: html(assignment_html( '2.4.2', 'Make a function that takes four points in the plane and returns the intersection of the line through the first two points and the line segment with endpoints the second two points (assuming that there is an intersection), and plot the line and line segment. Have the interactive output give an error message if there is no intersection.', funcs=[{ 'name': 'ray_intersects_line_segment(a1, a2, b1, b2)', 'params': [ 'a1, a2: points defining a line', 'b1, b2: line segment endpoints', ], 'returns': [ '1: ray intersects the interior', '0: ray contains one or both of b1, b2', '-1: does not intersect the line segment', '-2: a1 is on the line segment (b1, b2)', ] }], params=['(a) A list of four points in the plane.'] )), } # ''' # ---========================--- # End Assignment Defs # -------- # Begin Assignment Methods # ---========================--- # ''' def det(a, b): ''' gives determinant of 2d matrix params: | a, b: arrays with > 2 elems returns: | determinant ''' return a[0] * b[1] - a[1] * b[0] def line_intersection(a1, a2, b1, b2): ''' computes intersection of lines [a, b] params: | a1, a2: endpoints of line | b1, b2: endpoints of line returns: | x,y of intersection ''' xdiff = (a1[0] - a2[0], b1[0] - b2[0]) ydiff = (a1[1] - a2[1], b1[1] - b2[1]) div = det(xdiff, ydiff) if div == 0: raise Exception('lines do not intersect') d = (det(a1, a2) , det(b1, b2)) x = det(d, xdiff) / div y = det(d, ydiff) / div return x, y def line_intersects_line_segment(a1, a2, b1, b2): ''' checks if line (a1, a2) intersects line segment (b1, b2) returns: | -1: does not intersect (b1, b2) | 0: contains one or both of (b1, b2) | 1: intersects interior of (b1, b2) ''' return -1 * ccw(a1, a2, b1) * ccw(a1, a2, b2) def line_intersects_line_segment(a1, a2, b1, b2): ''' checks if line (a1, a2) intersects line segment (b1, b2) returns: | intersection between (a1, a2) and (b1, b2) ''' # ax + by = dx + ey - f + c # ax - dx = ey - by - f + c return -1 * ccw(a1, a2, b1) * ccw(a1, a2, b2) # ''' # ---==========================--- # End Assignment Methods # -------- # Begin Interactive Methods # ---==========================--- # ''' def interact_line_intersects_line_segment(points=inputs.box(val=random_points(4), label='four points')): res = [ arrow(*points[0:2], rgbcolor='blue'), arrow(points[1], points[0], rgbcolor='blue'), line(points[2:], rgbcolor='red') ] res += [point(p, size=30, rgbcolor='green') for p in points] show(plot_arr(res)) show_all([ 'list: {}'.format(points), [ 'contains one or both endpoint', 'intersects the interior of the line segment', 'does not intersect' ][line_intersects_line_segment(*points)] ]) interactive = { '2.4.1': interact_line_intersects_line_segment } def run_interactive(run=interactive): for exernum, func in run.items(): assignment(assignment_defs[exernum], func) # ''' # ---=======================--- # End Interactive Methods # --------- # Begin Main # ---=======================--- # ''' def main(): run_interactive() # print(line_intersection((0.5, 0.5), (1.5, 0.75), (1, 0), (1, 2))) main()
In [0]: