assignment_06.sagews

#All good.

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;',
        'font-sans': 'font-family: system-ui, -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, "Helvetica Neue", Arial, "Noto Sans", sans-serif, "Apple Color Emoji", "Segoe UI Emoji", "Segoe UI Symbol", "Noto Color Emoji";',
        'font-serif': 'font-family: Georgia, Cambria, "Times New Roman", Times, serif;',
        'font-mono': 'font-family: Menlo, Monaco, Consolas, "Liberation Mono", "Courier New", monospace;',
    }
    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(scale_rem(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])
                classes['-' + variant[0] + prefix + '-' + str(spacing * -1)] = "".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="font-sans text-base margin: 4rem 0;">
        <div style="text-xl mb-2 color: lime;">Exercise {}</div>
        <div style="ml-3 text-sm font-sans">
        <p><b>Assignment:</b> {}</p>
    '''.format(exernum, assignment)
    if funcs:
        for func in funcs:
            res += '<p><b>Function:</b><code style="font-mono 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></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 float_eq(a, b, epsilon=0.00001):
    '''
    checks if a ~= b within epsilon
    '''
    return abs(a - b) < epsilon

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
    '''
    show(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

def check_point_on_segment(query_point, a, b):
    '''
    returns:
    |  0 if query point is a or b
    |  1 if query point is on line segment
    | -1 if query point is not on line segment
    '''
    if any([query_point == p for p in [a, b]]): return 0
    return 1 if float_eq(dist(a, query_point) + dist(query_point, b), dist(a, b)) else -1

def arr_comb(arr):
    '''
    this sage kernel doesn't like unpacking
    '''
    res = []
    for a in arr:
        res += a
    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.3': lambda: html(assignment_html(
        '2.4.3',
        'Make a function that takes four points in the plane and tests if the ray from the first point through the second point intersects the line segment with endpoints the second two points, and plot the ray and line segment.',
        funcs=[{
            'name': 'ray_intersects_line_segment(a1, a2, b1, b2)',
            'params': [
                'a1, a2: points defining a ray',
                '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
    '''
    # get differences across axes
    xdiff = [a1[0] - a2[0], b1[0] - b2[0]]
    ydiff = [a1[1] - a2[1], b1[1] - b2[1]]
    # get divisor!
    div = det(xdiff, ydiff)
    if div == 0:
        raise Exception('lines do not intersect')
    d = [det(a1, a2) , det(b1, b2)]
    return det(d, xdiff) / div, det(d, ydiff) / div

def get_point_slope(a, b):
    '''
    derives point-slope form from two points on a line
    returns:
    | m: slope
    | c: y-intercept
    '''
    y = a[1] - b[1]
    m = y / (a[0] - b[0])
    c = a[1] - (m * a[0])
    return m, c

def point_on_line(querypoint, a, b):
    '''
    returns if querypoint is on the line ab
    '''
    # solves point-slope eq
    m, c = get_point_slope(a, b)
    if querypoint[1] == ((m * querypoint[0]) + c): return True
    return False

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)
    '''
    # just have to check directions
    return -1 * ccw(a1, a2, b1) * ccw(a1, a2, b2)

def line_intersection_line_segment(a1, a2, b1, b2):
    '''
    checks if line (a1, a2) intersects line segment (b1, b2)
    returns:
    | intersection between (a1, a2) and (b1, b2)
    | None if doesn't intersect
    '''
    try:
        # if theres an intersection, check if intersection is on segment
        intersection = line_intersection(a1, a2, b1, b2)
        if check_point_on_segment(intersection, b1, b2) == 1:
            return intersection
    except: pass
    return None

def ray_intersects_line_segment(a1, a2, b1, b2):
    '''
    checks if ray (a1, a2) intersects line segment (b1, b2)
    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)
    '''
    try:
        intersection = line_intersection(a1, a2, b1, b2)
        # checks if ray base is on line segment
        if check_point_on_segment(a1, b1, b2) == 0:
            return -2, None
        # checks if intersection is on the ray (maybe should write a 'ensure_tonicity(points, coord)')
        if check_point_on_segment(intersection, b1, b2) == 1:
            if a1[0] < a2[0] and intersection[0] >= a1[0]: return 1, intersection
            if a1[0] > a2[0] and intersection[0] <= a1[0]: return 1, intersection
        # checks if segment endpoints are on ray
        for point in [b1, b2]:
            if point_on_line(point, a1, a2):
                if a1[0] < a2[0] and point[0] >= a1[0]: return 0, point
                if a1[0] > a2[0] and point[0] <= a1[0]: return 0, point
    except: pass
    return -1, None

# '''
# ---==========================---
#    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)]
    ])

def interact_line_intersection_line_segment(
    line_endpoints=inputs.box(val=random_points(2), label='line endpoints'),
    segment_endpoints=inputs.box(val=random_points(2), label='segment endpoints')
):
    res = [
       arrow(*line_endpoints, rgbcolor='blue'),
       arrow(line_endpoints[1], line_endpoints[0], rgbcolor='blue'),
       line(segment_endpoints, rgbcolor='red')
    ]
    res += [point(p, size=30, rgbcolor='green') for p in arr_comb([line_endpoints, segment_endpoints])]
    show(plot_arr(res))
    intersection = line_intersection_line_segment(*arr_comb([line_endpoints, segment_endpoints]))
    show_all([
        'list: {}'.format(arr_comb([line_endpoints, segment_endpoints])),
        'intersection: {}'.format(intersection) if intersection is not None else 'does not intersect',
        'floats: {}'.format(list(map(float, intersection))) if intersection is not None else ''
    ])

def interact_ray_intersects_line_segment(
    ray_endpoints=inputs.box(val=random_points(2), label='line endpoints'),
    segment_endpoints=inputs.box(val=random_points(2), label='segment endpoints')
):
    res = [
       arrow(*ray_endpoints, rgbcolor='blue'),
       line(segment_endpoints, rgbcolor='red')
    ]
    res += [point(p, size=30, rgbcolor='green') for p in arr_comb([ray_endpoints, segment_endpoints])]
    show(plot_arr(res))
    ray_intersects, p = ray_intersects_line_segment(*arr_comb([ray_endpoints, segment_endpoints]))
    opts = [
        'ray contains one or both of b1, b2',
        'ray intersects the interior',
        'a1 is on the line segment (b1, b2)',
        'does not intersect the line segment'
    ]
    intersection = line_intersection_line_segment(*arr_comb([ray_endpoints, segment_endpoints]))
    show_all([
        'list: {}'.format(arr_comb([ray_endpoints, segment_endpoints])),
        'result: {}'.format(opts[ray_intersects]),
        'intersection: {}'.format(p) if p is not None else '',
        'floats: {}'.format(list(map(float, p))) if p is not None else '',
    ])

interactive = {
    '2.4.1': interact_line_intersects_line_segment,
    '2.4.2': interact_line_intersection_line_segment,
    '2.4.3': interact_ray_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()


main()

Exercise 2.4.3

Assignment: Make a function that takes four points in the plane and tests if the ray from the first point through the second point intersects the line segment with endpoints the second two points, and plot the ray and line segment.

Function:ray_intersects_line_segment(a1, a2, b1, b2)

params:

• a1, a2: points defining a ray
• 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)

Interactive input:

• (a) A list of four points in the plane.

$\displaystyle \mathrm{None}$

Interact: please open in CoCalc

Exercise 2.4.2

Assignment: 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.

Function: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).

Interactive input:

• (a) A list of four points in the plane.

$\displaystyle \mathrm{None}$

Interact: please open in CoCalc

Exercise 2.4.1

Assignment: 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.

Function: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

Interactive input:

• (a) A list of four points in the plane.

$\displaystyle \mathrm{None}$

Interact: please open in CoCalc