# 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

def num_differences(v1: Vector, v2: Vector) -> int:
    assert len(v1) == len(v2)
    return len([x1 for x1, x2 in zip(v1, v2) if x1 != x2])

assert num_differences([1, 2, 3], [2, 1, 3]) == 2
assert num_differences([1, 2], [1, 2]) == 0


def cluster_means(k: int,
                  inputs: List[Vector],
                  assignments: List[int]) -> List[Vector]:
    # clusters[i] contains the inputs whose assignment is i
    clusters = [[] for i in range(k)]
    for input, assignment in zip(inputs, assignments):
        clusters[assignment].append(input)

    # if a cluster is empty, just use a random point

# 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


def num_differences(v1: Vector, v2: Vector) -> int:
    assert len(v1) == len(v2)
    return len([x1 for x1, x2 in zip(v1, v2) if x1 != x2])

assert num_differences([1, 2, 3], [2, 1, 3]) == 2
assert num_differences([1, 2], [1, 2]) == 0


def cluster_means(k: int,
                  inputs: List[Vector],
                  assignments: List[int]) -> List[Vector]:
    # clusters[i] contains the inputs whose assignment is i
    clusters = [[] for i in range(k)]
    for input, assignment in zip(inputs, assignments):
        clusters[assignment].append(input)

    # if a cluster is empty, just use a random point

    return [vector_mean(cluster) if cluster else random.choice(inputs)