# Path: scratch/linear_algebra.py
# def add(v: Vector, w: Vector) -> Vector:
# def subtract(v: Vector, w: Vector) -> Vector:
# def vector_sum(vectors: List[Vector]) -> Vector:
# def scalar_multiply(c: float, v: Vector) -> Vector:
# def vector_mean(vectors: List[Vector]) -> Vector:
# def dot(v: Vector, w: Vector) -> float:
# def sum_of_squares(v: Vector) -> float:
# def magnitude(v: Vector) -> float:
# def squared_distance(v: Vector, w: Vector) -> float:
# def distance(v: Vector, w: Vector) -> float:
# def distance(v: Vector, w: Vector) -> float:  # type: ignore
# def shape(A: Matrix) -> Tuple[int, int]:
# def get_row(A: Matrix, i: int) -> Vector:
# def get_column(A: Matrix, j: int) -> Vector:
# def make_matrix(num_rows: int,
#                 num_cols: int,
#                 entry_fn: Callable[[int, int], float]) -> Matrix:
# def identity_matrix(n: int) -> Matrix:
# A = [[1, 2, 3],  # A has 2 rows and 3 columns
#      [4, 5, 6]]
# B = [[1, 2],     # B has 3 rows and 2 columns
#      [3, 4],
#      [5, 6]]
# 
# Path: scratch/linear_algebra.py
# def vector_mean(vectors: List[Vector]) -> Vector:
#     """Computes the element-wise average"""
#     n = len(vectors)
#     return scalar_multiply(1/n, vector_sum(vectors))
# 
# Path: scratch/linear_algebra.py
# def squared_distance(v: Vector, w: Vector) -> float:
#     """Computes (v_1 - w_1) ** 2 + ... + (v_n - w_n) ** 2"""
#     return sum_of_squares(subtract(v, w))
# 
# Path: scratch/linear_algebra.py
# def distance(v: Vector, w: Vector) -> float:
#     """Computes the distance between v and w"""
#     return math.sqrt(squared_distance(v, w))


from scratch.linear_algebra import Vector
from typing import List
from scratch.linear_algebra import vector_mean
from scratch.linear_algebra import squared_distance
from typing import NamedTuple, Union
from typing import Callable
from scratch.linear_algebra import distance
from typing import Tuple
    from matplotlib import pyplot as plt
import itertools
import random
import tqdm
    import matplotlib.image as mpimg

leaf1 = Leaf([10,  20])
leaf2 = Leaf([30, -15])

class Merged(NamedTuple):
    children: tuple
    order: int

merged = Merged((leaf1, leaf2), order=1)

Cluster = Union[Leaf, Merged]

def get_values(cluster: Cluster) -> List[Vector]:
    if isinstance(cluster, Leaf):
        return [cluster.value]
    else:
        return [value
                for child in cluster.children
                for value in get_values(child)]

assert get_values(merged) == [[10, 20], [30, -15]]


def cluster_distance(cluster1: Cluster,
                     cluster2: Cluster,
                     distance_agg: Callable = min) -> float:
    """
    compute all the pairwise distances between cluster1 and cluster2
    and apply the aggregation function _distance_agg_ to the resulting list
    """

# Path: scratch/linear_algebra.py
# def add(v: Vector, w: Vector) -> Vector:
# def subtract(v: Vector, w: Vector) -> Vector:
# def vector_sum(vectors: List[Vector]) -> Vector:
# def scalar_multiply(c: float, v: Vector) -> Vector:
# def vector_mean(vectors: List[Vector]) -> Vector:
# def dot(v: Vector, w: Vector) -> float:
# def sum_of_squares(v: Vector) -> float:
# def magnitude(v: Vector) -> float:
# def squared_distance(v: Vector, w: Vector) -> float:
# def distance(v: Vector, w: Vector) -> float:
# def distance(v: Vector, w: Vector) -> float:  # type: ignore
# def shape(A: Matrix) -> Tuple[int, int]:
# def get_row(A: Matrix, i: int) -> Vector:
# def get_column(A: Matrix, j: int) -> Vector:
# def make_matrix(num_rows: int,
#                 num_cols: int,
#                 entry_fn: Callable[[int, int], float]) -> Matrix:
# def identity_matrix(n: int) -> Matrix:
# A = [[1, 2, 3],  # A has 2 rows and 3 columns
#      [4, 5, 6]]
# B = [[1, 2],     # B has 3 rows and 2 columns
#      [3, 4],
#      [5, 6]]
# 
# Path: scratch/linear_algebra.py
# def vector_mean(vectors: List[Vector]) -> Vector:
#     """Computes the element-wise average"""
#     n = len(vectors)
#     return scalar_multiply(1/n, vector_sum(vectors))
# 
# Path: scratch/linear_algebra.py
# def squared_distance(v: Vector, w: Vector) -> float:
#     """Computes (v_1 - w_1) ** 2 + ... + (v_n - w_n) ** 2"""
#     return sum_of_squares(subtract(v, w))
# 
# Path: scratch/linear_algebra.py
# def distance(v: Vector, w: Vector) -> float:
#     """Computes the distance between v and w"""
#     return math.sqrt(squared_distance(v, w))


# Path: scratch/clustering.py
from scratch.linear_algebra import Vector
from typing import List
from scratch.linear_algebra import vector_mean
from scratch.linear_algebra import squared_distance
from typing import NamedTuple, Union
from typing import Callable
from scratch.linear_algebra import distance
from typing import Tuple
    from matplotlib import pyplot as plt
import itertools
import random
import tqdm
    import matplotlib.image as mpimg


leaf1 = Leaf([10,  20])
leaf2 = Leaf([30, -15])

class Merged(NamedTuple):
    children: tuple
    order: int

merged = Merged((leaf1, leaf2), order=1)

Cluster = Union[Leaf, Merged]

def get_values(cluster: Cluster) -> List[Vector]:
    if isinstance(cluster, Leaf):
        return [cluster.value]
    else:
        return [value
                for child in cluster.children
                for value in get_values(child)]

assert get_values(merged) == [[10, 20], [30, -15]]


def cluster_distance(cluster1: Cluster,
                     cluster2: Cluster,
                     distance_agg: Callable = min) -> float:
    """
    compute all the pairwise distances between cluster1 and cluster2
    and apply the aggregation function _distance_agg_ to the resulting list
    """

    return distance_agg([distance(v1, v2)