Hands-on lab — Day 99: Vectors: Direction, Magnitude, and Meaning

"""The same nine operations, twice: your loops, then NumPy — and they agree.

This is the only file in the lab that imports NumPy. Read it after you have
written the loops in `vectors.py`, not before. The order matters: once you have
written `sum(a * a for a in v)` yourself, `np.linalg.norm(v)` is not magic, it
is your loop with a shorter name and a faster inner loop.

Every comparison uses `numpy.allclose` or `math.isclose` with a stated
tolerance. Nothing here is compared with `==`, and the reason is in
`normalise.py`.

Run from the examples directory:

    python3 agreement.py
"""

from __future__ import annotations

import math

import numpy as np

import vectors as pure

RTOL = 1e-9
ATOL = 1e-12

U = [3, 4, 12]
V = [1, -2, 5]
K = 2.5

CASES = [
    ("add(u, v)", lambda: pure.add(U, V), lambda: np.array(U) + np.array(V)),
    ("subtract(u, v)", lambda: pure.subtract(U, V), lambda: np.array(U) - np.array(V)),
    ("scale(k, u)", lambda: pure.scale(K, U), lambda: K * np.array(U)),
    ("negate(u)", lambda: pure.negate(U), lambda: -np.array(U)),
    ("zero(3)", lambda: pure.zero(3), lambda: np.zeros(3)),
    ("normalise(u)", lambda: pure.normalise(U), lambda: np.array(U) / np.linalg.norm(U)),
]

SCALAR_CASES = [
    ("dot(u, v)", lambda: pure.dot(U, V), lambda: float(np.dot(U, V))),
    ("l2_norm(u)", lambda: pure.l2_norm(U), lambda: float(np.linalg.norm(U))),
    ("l1_norm(u)", lambda: pure.l1_norm(U), lambda: float(np.linalg.norm(U, ord=1))),
    (
        "distance(u, v)",
        lambda: pure.distance(U, V),
        lambda: float(np.linalg.norm(np.array(U) - np.array(V))),
    ),
    (
        "l1_distance(u, v)",
        lambda: pure.l1_distance(U, V),
        lambda: float(np.linalg.norm(np.array(U) - np.array(V), ord=1)),
    ),
]


def main() -> int:
    print("Pure Python against NumPy, on the same inputs")
    print(f"numpy {np.__version__}")
    print(f"u = {U}    v = {V}    k = {K}")
    print(f"tolerance: rtol={RTOL}, atol={ATOL} — never ==")
    print()

    all_agree = True

    header = f"{'operation':<22}{'pure Python':<34}{'NumPy':<34}agree"
    print(header)
    print("-" * len(header))

    for name, py_fn, np_fn in CASES:
        py_out = py_fn()
        np_out = np_fn()
        agree = bool(np.allclose(py_out, np_out, rtol=RTOL, atol=ATOL))
        all_agree = all_agree and agree
        py_text = str([round(float(x), 6) for x in py_out])
        np_text = str([round(float(x), 6) for x in np_out])
        print(f"{name:<22}{py_text:<34}{np_text:<34}{agree}")

    for name, py_fn, np_fn in SCALAR_CASES:
        py_out = py_fn()
        np_out = np_fn()
        agree = math.isclose(py_out, np_out, rel_tol=RTOL, abs_tol=ATOL)
        all_agree = all_agree and agree
        print(f"{name:<22}{py_out!r:<34}{np_out!r:<34}{agree}")

    print()
    print("every operation agrees:", all_agree)
    print()

    # ---------------------------------------------------------------------
    print("Three things NumPy gives you that the loops do not")
    print()

    stacked = np.array(
        [
            [9, 0, 1, 0],
            [8, 0, 2, 0],
            [0, 9, 1, 2],
        ]
    )
    print("1. A whole table of vectors is one object, and one call measures")
    print("   every row at once:")
    print(f"     matrix shape        = {stacked.shape}")
    print(f"     norms of all rows   = {np.linalg.norm(stacked, axis=1).round(4)}")
    row_by_row = [pure.l2_norm(list(row)) for row in stacked]
    print(f"     the same, by loop   = {[round(x, 4) for x in row_by_row]}")
    print(
        "     agree               = "
        f"{bool(np.allclose(np.linalg.norm(stacked, axis=1), row_by_row, rtol=RTOL, atol=ATOL))}"
    )
    print()

    print("2. Every distance from one query to every row, in one expression:")
    query = np.array([1, 0, 0, 0])
    diffs = stacked - query
    dists = np.linalg.norm(diffs, axis=1)
    loop_dists = [pure.distance([1, 0, 0, 0], list(row)) for row in stacked]
    print(f"     query               = {query.tolist()}")
    print(f"     distances (NumPy)   = {dists.round(4)}")
    print(f"     distances (loop)    = {[round(x, 4) for x in loop_dists]}")
    print(
        "     agree               = "
        f"{bool(np.allclose(dists, loop_dists, rtol=RTOL, atol=ATOL))}"
    )
    print()
    print("   `stacked - query` subtracted a 4-component vector from every row")
    print("   of a 3-by-4 table without a loop. That is broadcasting, and it is")
    print("   the reason a search over a million embeddings is a few lines.")
    print()

    print("3. The dimension check is still there — NumPy just phrases it in")
    print("   terms of shapes:")
    try:
        np.array([1, 2]) + np.array([1, 2, 3])
    except ValueError as exc:
        print(f"     numpy : ValueError: {exc}")
    try:
        pure.add([1, 2], [1, 2, 3])
    except ValueError as exc:
        print(f"     ours  : ValueError: {exc}")

    return 0 if all_agree else 1


if __name__ == "__main__":
    raise SystemExit(main())

"""Norms and distances whose answers are exact whole numbers.

Every line this prints can be re-derived with a pen. That is the point: before
you trust a library to measure a vector, measure four of them yourself and
confirm the library agrees.

The vectors are chosen so the square root comes out whole. (3, 4) is the 3-4-5
right triangle; (2, 3, 6) and (1, 2, 2) are the same trick in three dimensions,
where 4 + 9 + 36 = 49 and 1 + 4 + 4 = 9.

Run from the examples directory:

    python3 byhand.py
"""

from __future__ import annotations

import math

from vectors import distance, l1_norm, l2_norm, subtract

# (vector, the exact magnitude a human gets on paper)
EXACT_NORMS = [
    ([3, 4], 5),
    ([6, 8], 10),
    ([2, 3, 6], 7),
    ([1, 2, 2], 3),
    ([0, 0, 0], 0),
]

# (u, v, the exact distance between them)
EXACT_DISTANCES = [
    ([1, 2], [4, 6], 5),
    ([0, 0, 0], [2, 3, 6], 7),
    ([10, 10], [10, 10], 0),
    ([1, 1, 1], [2, 3, 3], 3),
]

TOLERANCE = "rel_tol=1e-9, abs_tol=1e-12"


def show_norm(v: list[int], expected: int) -> bool:
    squares = [a * a for a in v]
    total = sum(squares)
    got = l2_norm(v)
    agrees = math.isclose(got, expected, rel_tol=1e-9, abs_tol=1e-12)
    working = " + ".join(f"{a}^2" for a in v)
    numbers = " + ".join(str(s) for s in squares)
    print(f"  |{v}|")
    print(f"      = sqrt({working})")
    print(f"      = sqrt({numbers})")
    print(f"      = sqrt({total})")
    print(f"      = {expected}          computed: {got!r}   agrees: {agrees}")
    return agrees


def show_distance(u: list[int], v: list[int], expected: int) -> bool:
    diff = subtract(u, v)
    squares = [a * a for a in diff]
    total = sum(squares)
    got = distance(u, v)
    agrees = math.isclose(got, expected, rel_tol=1e-9, abs_tol=1e-12)
    numbers = " + ".join(str(s) for s in squares)
    print(f"  dist({u}, {v})")
    print(f"      = |{u} - {v}|")
    print(f"      = |{[int(x) for x in diff]}|")
    print(f"      = sqrt({numbers}) = sqrt({total})")
    print(f"      = {expected}          computed: {got!r}   agrees: {agrees}")
    return agrees


def main() -> int:
    print("Magnitudes you can check with a pen")
    print(f"(agreement is math.isclose with {TOLERANCE}, never ==)")
    print()
    ok = True
    for v, expected in EXACT_NORMS:
        ok = show_norm(v, expected) and ok
        print()

    print("Distances you can check with a pen")
    print("(distance is not a separate formula: subtract, then measure)")
    print()
    for u, v, expected in EXACT_DISTANCES:
        ok = show_distance(u, v, expected) and ok
        print()

    print("The two norms of the same vector are different numbers")
    print()
    for v in ([3, 4], [1, 2, 2], [4, 0, 0], [2, 2, 2]):
        print(
            f"  {str(v):<12} L1 = {l1_norm(v):<6.4f} "
            f"L2 = {l2_norm(v):.4f}"
        )
    print()
    print("all exact cases agree:", ok)
    return 0 if ok else 1


if __name__ == "__main__":
    raise SystemExit(main())

"""A tiny embedding, hand-made, so that "similar" becomes a number.

Six short articles. Four features, counted by hand: how many times the article
talks about cooking, about running, about money, and about weather. That is it.
Each article is now a list of four numbers — a vector — and the sentence
"these two articles are similar" has become "these two vectors are close",
which is a claim you can check with arithmetic.

Real embeddings are produced by a trained model and have hundreds or thousands
of components whose meanings nobody assigned by hand. Everything else is the
same: a row of numbers per item, and nearness measured with a norm.

Run from the examples directory:

    python3 embeddings.py
"""

from __future__ import annotations

from vectors import distance, l2_norm, normalise, nearest, subtract

FEATURES = ("cooking", "running", "money", "weather")

CATALOGUE = {
    "roast-chicken":      [9, 0, 1, 0],
    "slow-cooker-stew":   [8, 0, 2, 0],
    "marathon-plan":      [0, 9, 1, 2],
    "race-day-nutrition": [4, 6, 3, 0],
    "household-budget":   [1, 0, 9, 0],
    "storm-bulletin":     [0, 1, 0, 9],
}


def print_catalogue() -> None:
    print("The catalogue: one row of four numbers per article")
    print()
    header = f"{'article':<20}" + "".join(f"{f:>10}" for f in FEATURES) + f"{'|v|':>10}"
    print(header)
    print("-" * len(header))
    for label, vec in CATALOGUE.items():
        row = "".join(f"{n:>10}" for n in vec)
        print(f"{label:<20}{row}{l2_norm(vec):>10.4f}")
    print()


def print_matrix() -> None:
    labels = list(CATALOGUE)
    print("Pairwise Euclidean distance (the magnitude of the difference)")
    print()
    print(f"{'':<20}" + "".join(f"{lab[:9]:>11}" for lab in labels))
    for a in labels:
        cells = "".join(f"{distance(CATALOGUE[a], CATALOGUE[b]):>11.4f}" for b in labels)
        print(f"{a:<20}{cells}")
    print()


def print_working(a: str, b: str) -> None:
    """Show one distance in full, the way you would do it on paper."""
    u, v = CATALOGUE[a], CATALOGUE[b]
    diff = [int(x) for x in subtract(u, v)]
    squares = [d * d for d in diff]
    print(f"  {a} vs {b}")
    print(f"      {u} - {v} = {diff}")
    print(f"      squares: {' + '.join(str(s) for s in squares)} = {sum(squares)}")
    print(f"      sqrt({sum(squares)}) = {distance(u, v):.4f}")


def print_nearest() -> None:
    print("Nearest neighbour of each article, itself excluded")
    print()
    for label in CATALOGUE:
        winner, score = nearest(
            CATALOGUE[label], CATALOGUE, exclude=label
        )
        print(f"  {label:<20} -> {winner:<20} at {score:.4f}")
    print()


def print_length_effect() -> None:
    """Why normalising is so common: length is not topic."""
    print("Part 1 — the same article, three times as long")
    print()
    short = CATALOGUE["roast-chicken"]
    long_version = [3 * n for n in short]
    print(f"  short = {str(short):<16} |v| = {l2_norm(short):.4f}")
    print(f"  long  = {str(long_version):<16} |v| = {l2_norm(long_version):.4f}")
    print(f"  raw distance between them       = {distance(short, long_version):.4f}")
    print(
        "  distance after normalising both = "
        f"{distance(normalise(short), normalise(long_version)):.4f}"
    )
    print()
    print("  Raw counts put these two far apart. They are not about different")
    print("  things — one is simply longer. Normalising throws the length away")
    print("  and keeps only the direction, which is the part that carries the")
    print("  topic. The long version is the short version scaled by 3, so after")
    print("  normalising they are the same vector and the distance is 0.")
    print()

    print("Part 2 — a short note, where raw counts pick the wrong article")
    print()
    query = [1, 0, 0, 0]
    print(f"  query = {query}  (a one-line cooking note: 'roast it')")
    print()
    unit_catalogue = {label: normalise(v) for label, v in CATALOGUE.items()}
    unit_query = normalise(query)
    header = f"  {'article':<20}{'raw distance':>16}{'normalised distance':>22}"
    print(header)
    print("  " + "-" * (len(header) - 2))
    for label, vec in CATALOGUE.items():
        print(
            f"  {label:<20}{distance(query, vec):>16.4f}"
            f"{distance(unit_query, unit_catalogue[label]):>22.4f}"
        )
    raw_winner, raw_score = nearest(query, CATALOGUE)
    unit_winner, unit_score = nearest(unit_query, unit_catalogue)

    raw_order = sorted(CATALOGUE, key=lambda k: distance(query, CATALOGUE[k]))
    unit_order = sorted(
        CATALOGUE, key=lambda k: distance(unit_query, unit_catalogue[k])
    )
    print()
    print(f"  nearest on raw counts : {raw_winner} at {raw_score:.4f}")
    print(f"  nearest normalised    : {unit_winner} at {unit_score:.4f}")
    print(f"  they disagree         : {raw_winner != unit_winner}")
    print(f"  raw rank of roast-chicken        : {raw_order.index('roast-chicken') + 1}")
    print(
        f"  normalised rank of roast-chicken : "
        f"{unit_order.index('roast-chicken') + 1}"
    )
    print()
    print("  The note is purely about cooking, so roast-chicken — the article")
    print("  most purely about cooking — should win. On raw counts it comes")
    print("  third, behind slow-cooker-stew and behind race-day-nutrition,")
    print("  which is mostly about running. Nothing is wrong with the")
    print("  arithmetic. The query vector is short, so it sits near the origin,")
    print("  and raw distance from a point near the origin is dominated by how")
    print("  long each article is rather than by what it is about. Normalising")
    print("  puts every vector on the unit sphere, which deletes length from")
    print("  the comparison and leaves only direction — and direction is the")
    print("  part that carries the topic. Normalised, roast-chicken wins.")
    print()


def main() -> int:
    print_catalogue()
    print_matrix()
    print("Two of those distances, worked out in full")
    print()
    print_working("roast-chicken", "slow-cooker-stew")
    print()
    print_working("roast-chicken", "household-budget")
    print()
    print_nearest()
    print_length_effect()

    closest_pair = min(
        (
            (distance(CATALOGUE[a], CATALOGUE[b]), a, b)
            for i, a in enumerate(CATALOGUE)
            for b in list(CATALOGUE)[i + 1 :]
        )
    )
    score, a, b = closest_pair
    print(f"Closest pair in the whole catalogue: {a} and {b} at {score:.4f}")
    print()
    print("That is the entire idea behind semantic search. Turn each item into")
    print("a vector, turn the query into a vector the same way, and return the")
    print("items whose vectors are nearest. Everything after this is about")
    print("getting better vectors and searching them faster.")
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

"""Normalisation, and the float comparison that will bite you.

Normalising a vector scales it to magnitude 1 while leaving its direction
alone. The arithmetic is simple. The trap is what you do next: if you write

    assert l2_norm(unit) == 1.0

you have written a test that passes for some vectors and fails for others, for
reasons that have nothing to do with your code being right. Day 46 covered why:
a float is a binary approximation, and dividing by a square root and then
squaring the results back up does not have to land on exactly 1.0.

This script normalises seven vectors and shows, for each one, the exact
repr of the resulting magnitude, whether `== 1.0` holds, and whether
`math.isclose` holds. Run it from the examples directory:

    python3 normalise.py
"""

from __future__ import annotations

import math

from vectors import l2_norm, normalise, scale

REL_TOL = 1e-9
ABS_TOL = 1e-12

CASES = [
    [3, 4],
    [1, 2, 2],
    [1, 1],
    [1, 1, 1],
    [0.1, 0.2, 0.3],
    [2, 3, 6],
    [7, 1, 5, 3, 9, 2],
]


def main() -> int:
    print("Normalising: v_hat = (1 / |v|) * v")
    print(f"tolerance in use: math.isclose(rel_tol={REL_TOL}, abs_tol={ABS_TOL})")
    print()
    header = f"{'vector':<26}{'|v|':<22}{'|v_hat| (exact repr)':<26}{'== 1.0':<9}isclose"
    print(header)
    print("-" * len(header))

    exact_equal = 0
    close_count = 0
    for v in CASES:
        unit = normalise(v)
        length = l2_norm(unit)
        equal = length == 1.0
        close = math.isclose(length, 1.0, rel_tol=REL_TOL, abs_tol=ABS_TOL)
        exact_equal += equal
        close_count += close
        print(
            f"{str(v):<26}{l2_norm(v)!r:<22}{length!r:<26}"
            f"{str(equal):<9}{close}"
        )

    print()
    print(f"exactly 1.0 : {exact_equal} of {len(CASES)}")
    print(f"isclose 1.0 : {close_count} of {len(CASES)}")
    print()
    print("This is the whole argument for never comparing floats with ==.")
    print("The maths is right in every row. Only the equality test disagrees.")
    print()

    print("Direction is preserved: v_hat scaled back up by |v| returns v")
    print()
    for v in ([3, 4], [1, 2, 2]):
        unit = normalise(v)
        back = scale(l2_norm(v), unit)
        agrees = all(
            math.isclose(a, b, rel_tol=REL_TOL, abs_tol=ABS_TOL)
            for a, b in zip(back, v)
        )
        print(f"  v      = {v}")
        print(f"  v_hat  = {[round(x, 6) for x in unit]}")
        print(f"  |v| * v_hat = {[round(x, 6) for x in back]}   recovers v: {agrees}")
        print()

    print("The zero vector cannot be normalised, and says so")
    try:
        normalise([0, 0, 0])
    except ValueError as exc:
        print(f"  normalise([0, 0, 0]) -> ValueError: {exc}")
    else:  # pragma: no cover - would be a bug in vectors.py
        print("  normalise([0, 0, 0]) returned without raising, which is a bug")
        return 1

    return 0


if __name__ == "__main__":
    raise SystemExit(main())

"""Where L1 and L2 disagree — and why that is a decision, not a detail.

Two candidate documents are compared against the same query. Under the L2
(Euclidean) norm one of them is nearer. Under the L1 (taxicab) norm the *other*
one is. Both answers are arithmetically correct. "Nearest" is only a
well-defined question once you have named a norm.

The numbers are chosen so you can do them in your head:

    query      = (0, 0, 0)
    candidate  spike   = (4, 0, 0)      one big component
    candidate  spread  = (2, 2, 2)      three small ones

    L1: |4| + |0| + |0| = 4      vs  |2| + |2| + |2| = 6      -> spike is nearer
    L2: sqrt(16 + 0 + 0) = 4     vs  sqrt(4 + 4 + 4) = sqrt(12) = 3.4641...
                                                              -> spread is nearer

Squaring is what does it. L2 squares each component before adding, so a single
component of 4 contributes 16 while three components of 2 contribute 4 each.
L1 never squares, so it counts every unit of difference at face value and one
big deviation costs exactly as much as the same total spread thinly.

Run from the examples directory:

    python3 norms.py
"""

from __future__ import annotations

from vectors import l1_distance, l1_norm, l2_norm, distance

QUERY = [0, 0, 0]
CANDIDATES = {
    "spike": [4, 0, 0],
    "spread": [2, 2, 2],
}

# A second pair, translated away from the origin, to show that the effect is
# about the shape of the difference and not about sitting at zero.
BASE = [10, 10, 10]
SHIFTED = {
    "spike": [14, 10, 10],
    "spread": [12, 12, 12],
}


def rank(query, candidates, metric) -> list[tuple[str, float]]:
    scored = [(label, metric(query, vec)) for label, vec in candidates.items()]
    return sorted(scored, key=lambda pair: (pair[1], pair[0]))


def report(title, query, candidates) -> tuple[str, str]:
    print(title)
    print(f"  query = {query}")
    for label, vec in candidates.items():
        diff = [b - a for a, b in zip(query, vec)]
        squares = " + ".join(str(d * d) for d in diff)
        abses = " + ".join(str(abs(d)) for d in diff)
        print(f"  {label:<8} = {vec}   difference = {diff}")
        print(f"           L1 = {abses} = {l1_norm(diff):.4f}")
        print(f"           L2 = sqrt({squares}) = {l2_norm(diff):.4f}")

    l2_rank = rank(query, candidates, distance)
    l1_rank = rank(query, candidates, l1_distance)
    print(f"  L2 ranking: {[f'{n} {s:.4f}' for n, s in l2_rank]}")
    print(f"  L1 ranking: {[f'{n} {s:.4f}' for n, s in l1_rank]}")
    print(f"  nearest under L2: {l2_rank[0][0]}")
    print(f"  nearest under L1: {l1_rank[0][0]}")
    print(f"  the two norms disagree: {l2_rank[0][0] != l1_rank[0][0]}")
    print()
    return l2_rank[0][0], l1_rank[0][0]


def main() -> int:
    print("L1 and L2 ranking the same two candidates in opposite orders")
    print()
    a = report("Case 1 — query at the origin", QUERY, CANDIDATES)
    b = report("Case 2 — the same shapes, moved away from the origin", BASE, SHIFTED)

    disagreed = a[0] != a[1] and b[0] != b[1]
    print("Both cases produced a disagreement:", disagreed)
    print()
    print("Neither answer is wrong. L2 is the default because it matches the")
    print("everyday meaning of distance and because squaring makes it smooth")
    print("to work with. L1 is chosen when one large deviation should not be")
    print("allowed to dominate a lot of small ones. The norm is a modelling")
    print("choice, and it belongs in the write-up next to the result.")
    return 0 if disagreed else 1


if __name__ == "__main__":
    raise SystemExit(main())

"""Vectors from scratch, in pure Python.

The reference implementation for the Day 099 lab. Every function here works on
an ordinary Python list of numbers. There is no NumPy in this file on purpose:
the point of the lab is that you write the loop first, so that when NumPy does
the same thing in one character you already know what it is doing.

A vector here is `[3, 4]` or `[9, 0, 1, 0]` — a list of numbers, in a fixed
order, where position means something. Nothing more.

Every function that takes two vectors checks that they have the same length
first. Adding a 2-dimensional vector to a 3-dimensional one is not a slightly
wrong answer, it is a meaningless question, and the code should say so rather
than silently truncating.
"""

from __future__ import annotations

import math
from collections.abc import Sequence

Vector = Sequence[float]


# --------------------------------------------------------------------------
# The guard every two-vector operation shares
# --------------------------------------------------------------------------


def check_same_dimension(u: Vector, v: Vector) -> None:
    """Raise unless `u` and `v` have the same number of components.

    Length is the dimension. Two vectors of different dimension do not live in
    the same space, and no operation below is defined across them.
    """
    if len(u) != len(v):
        raise ValueError(
            f"dimension mismatch: {len(u)} and {len(v)} "
            "— vectors must have the same number of components"
        )


# --------------------------------------------------------------------------
# Addition, subtraction, scaling
# --------------------------------------------------------------------------


def add(u: Vector, v: Vector) -> list[float]:
    """Componentwise sum. Geometrically: walk u, then walk v from where you land."""
    check_same_dimension(u, v)
    return [a + b for a, b in zip(u, v)]


def subtract(u: Vector, v: Vector) -> list[float]:
    """Componentwise difference.

    Geometrically u - v is the arrow that starts at the tip of v and ends at
    the tip of u: "how do I get from v to u". That is why the distance between
    two points is the magnitude of their difference.
    """
    check_same_dimension(u, v)
    return [a - b for a, b in zip(u, v)]


def scale(k: float, v: Vector) -> list[float]:
    """Multiply every component by the number k.

    A positive k changes magnitude and leaves direction alone. A negative k
    reverses the direction as well. k = 0 collapses the vector to the zero
    vector, which is the one vector with no direction at all.
    """
    return [k * a for a in v]


def negate(v: Vector) -> list[float]:
    """The vector of the same magnitude pointing the opposite way: -1 times v."""
    return scale(-1, v)


def zero(dimension: int) -> list[float]:
    """The zero vector of a given dimension: all components 0.

    It is the additive identity — add it to anything and nothing moves — and
    it is the one vector whose magnitude is 0 and whose direction is undefined.
    """
    if dimension < 0:
        raise ValueError(f"dimension must not be negative, got {dimension}")
    return [0.0] * dimension


# --------------------------------------------------------------------------
# Dot product
# --------------------------------------------------------------------------


def dot(u: Vector, v: Vector) -> float:
    """Multiply matching components, then add up the results.

    Returns one number, not a vector. That collapse from two lists to a single
    number is the whole reason the dot product is everywhere: it is how a
    similarity score, a projection and a weighted sum are all computed.
    """
    check_same_dimension(u, v)
    total = 0.0
    for a, b in zip(u, v):
        total += a * b
    return total


# --------------------------------------------------------------------------
# Norms — two ways of answering "how big is this vector"
# --------------------------------------------------------------------------


def l2_norm(v: Vector) -> float:
    """The Euclidean length: square every component, add, take the square root.

    This is Pythagoras, applied one dimension at a time. In 2D it is literally
    the hypotenuse. In 300 dimensions the picture is gone but the arithmetic is
    unchanged, which is the single most useful fact in this lesson.
    """
    return math.sqrt(sum(a * a for a in v))


# The name used everywhere else in the lab, because "magnitude" is the word the
# lesson uses and `norm` unqualified always means L2 in practice.
norm = l2_norm
magnitude = l2_norm


def l1_norm(v: Vector) -> float:
    """The taxicab length: add up the absolute values of the components.

    No squaring, so no square root. L1 counts every component at face value;
    L2 punishes one large component more than several small ones. That
    difference is not cosmetic — the two norms can rank the same pair of
    candidates in opposite orders, which `norms.py` demonstrates.
    """
    return sum(abs(a) for a in v)


# --------------------------------------------------------------------------
# Distance and normalisation
# --------------------------------------------------------------------------


def distance(u: Vector, v: Vector) -> float:
    """Euclidean distance: the magnitude of the difference.

    There is no separate distance formula to memorise. Subtract, then measure.
    """
    return l2_norm(subtract(u, v))


def l1_distance(u: Vector, v: Vector) -> float:
    """Manhattan distance: the L1 norm of the difference."""
    return l1_norm(subtract(u, v))


def normalise(v: Vector) -> list[float]:
    """Scale a vector to magnitude 1, keeping its direction.

    Dividing by the magnitude is the same as multiplying by 1/magnitude, so
    this is scalar multiplication with a particular scalar. The zero vector has
    magnitude 0 and no direction, so it cannot be normalised — this raises
    rather than returning a list of NaNs that would poison every later result.

    The result's magnitude is 1 to within floating-point error, and *not*
    exactly 1. Never test it with `==`; see `normalise.py`.
    """
    length = l2_norm(v)
    if length == 0.0:
        raise ValueError("cannot normalise the zero vector: it has no direction")
    return scale(1.0 / length, v)


def is_unit(v: Vector, *, rel_tol: float = 1e-9, abs_tol: float = 1e-12) -> bool:
    """True if the magnitude is 1 to the stated tolerance.

    The default tolerance is the one used throughout this lab. It is stated as
    a keyword argument rather than hidden in the body so that a caller who
    needs a looser one has to say so out loud.
    """
    return math.isclose(l2_norm(v), 1.0, rel_tol=rel_tol, abs_tol=abs_tol)


# --------------------------------------------------------------------------
# Working with a labelled collection of vectors
# --------------------------------------------------------------------------


def nearest(
    query: Vector,
    labelled: dict[str, Vector],
    *,
    metric=distance,
    exclude: str | None = None,
) -> tuple[str, float]:
    """Return the (label, score) of the closest entry under `metric`.

    `exclude` skips one label, which is what you want when the query is itself
    a member of the collection — otherwise every item's nearest neighbour is
    itself at distance 0, which is true and useless.

    Ties are broken by label so the answer is deterministic and testable.
    """
    candidates = [
        (label, metric(query, vec))
        for label, vec in labelled.items()
        if label != exclude
    ]
    if not candidates:
        raise ValueError("no candidates to compare against")
    return min(candidates, key=lambda pair: (pair[1], pair[0]))


def pairwise_distances(labelled: dict[str, Vector], *, metric=distance) -> dict:
    """Every unordered pair mapped to its distance, keyed by (label_a, label_b)."""
    labels = list(labelled)
    out = {}
    for i, a in enumerate(labels):
        for b in labels[i + 1 :]:
            out[(a, b)] = metric(labelled[a], labelled[b])
    return out


if __name__ == "__main__":
    a = [3, 4]
    b = [6, 8]
    print("a            =", a)
    print("b            =", b)
    print("a + b        =", add(a, b))
    print("b - a        =", subtract(b, a))
    print("2 * a        =", scale(2, a))
    print("a . b        =", dot(a, b))
    print("|a|          =", l2_norm(a))
    print("L1 of a      =", l1_norm(a))
    print("dist(a, b)   =", distance(a, b))
    print("normalise(a) =", normalise(a))

lesson_id: D099
day: 99
kind: guided-build
languages: [python, bash]
setup_commands:
  - cd labs/sections/math-statistics-and-data/day-099-vectors-direction-magnitude-and-meaning
  - python3 -m venv .venv
  - .venv/bin/pip install -r requirements/requirements.txt
  - .venv/bin/python3 -c "import numpy; print(numpy.__version__)"
run_commands:
  - .venv/bin/python3 starter/vectors.py
  - .venv/bin/pytest starter -q
  - cd examples && ../.venv/bin/python3 byhand.py
  - cd examples && ../.venv/bin/python3 normalise.py
  - cd examples && ../.venv/bin/python3 norms.py
  - cd examples && ../.venv/bin/python3 embeddings.py
  - cd examples && ../.venv/bin/python3 agreement.py
  - .venv/bin/pytest tests -q
test_commands:
  - bash tests/run_tests.sh
cleanup_commands:
  - "find . -type d -name '__pycache__' -prune -exec rm -rf -- {} +"
  - rm -rf .pytest_cache
  - 'rm -rf .venv  # optional: removes the lab virtual environment'
  - 'git checkout -- starter/  # optional: reset your work'
requires_network: true
requires_api_key: false
estimated_minutes: 30
last_executed: '2026-08-16'
executed_on: 'macOS 26.5.2 (Apple Silicon, arm64), Python 3.14.0, NumPy 2.5.2, pytest 9.1.1, bash 3.2.57 — bash tests/run_tests.sh -> 87 checks, 0 failure(s), exit 0; pytest tests -> 79 passed; pytest starter -> 1 passed, 11 skipped before the exercises are done and 12 passed once the reference implementation is dropped in; examples/byhand.py -> all exact cases agree: True; examples/agreement.py -> every operation agrees: True; examples/normalise.py -> isclose 1.0: 7 of 7 but exactly 1.0: only 4 of 7, which is the floating-point trap the lab teaches and which the harness asserts must reproduce; examples/norms.py -> L2 picks spread, L1 picks spike, disagreement in both cases; examples/embeddings.py -> closest pair roast-chicken and slow-cooker-stew at 1.4142. Network is needed once to install the two pinned packages; nothing in the lab opens a socket at run time. PyTorch, JAX and pandas are deliberately NOT installed here, so the lesson describes them from their documentation and reproduces no output from them; the harness confirms their absence. This run used PYTHON/PYTEST overrides pointing at an authoring interpreter outside the lab directory rather than a lab-local .venv; the harness resolves either. The harness was also verified to fail: removing abs() from l1_norm produced 87 checks, 8 failure(s) and a non-zero exit.'

# Requirements

Two packages, both pinned to the exact versions this lab was written and run
against.

| Package | Pinned version | Why the lab needs it |
| --- | --- | --- |
| `numpy` | 2.5.2 | The array library everything else in numerical Python imitates. It is used in exactly two places: `examples/agreement.py`, which proves the pure-Python implementation and NumPy give the same answers on the same inputs, and the two test suites, which assert that agreement |
| `pytest` | 9.1.1 | Runs `tests/test_vectors.py` and the `starter/` exercise suite |

Both are free and open source: NumPy is BSD-3-Clause, pytest is MIT.

## The versions are pinned on purpose

`expected-output/` was captured from a run against exactly these versions, and
`tests/run_tests.sh` checks the installed versions against this file. If you
install something else, that check fails — which is the harness telling you the
truth rather than quietly comparing your run against numbers it did not produce.

## Install

From the lab directory:

```bash
python3 -m venv .venv
.venv/bin/pip install -r requirements/requirements.txt
```

This is the only step that needs a network connection. Everything after it runs
offline.

## What the lab does not need

Nothing else. The nine vector functions the lab asks you to write use
`math.sqrt` from the standard library and nothing more, and `starter/vectors.py`
is checked by the harness for the absence of a NumPy import — writing the loop
yourself is the exercise.

The lesson also discusses PyTorch tensors, JAX arrays and pandas Series. None
of the three is installed here, and the lesson reproduces no output from any of
them; it describes them from their published documentation and says so. The
test harness confirms their absence so that claim cannot rot.

numpy==2.5.2
pytest==9.1.1

# The brief — Vectors You Can Hold

You run a small recipe-and-lifestyle site with six articles on it. Somebody
has asked for a "related articles" box: given one article, show the one most
like it.

You have no machine learning, no search engine and no budget. What you do have
is a text file per article, and the ability to count words.

So you count. For each article you count how many times it mentions cooking,
running, money and weather. Four numbers per article, always in that order.

| article | cooking | running | money | weather |
| --- | --- | --- | --- | --- |
| `roast-chicken` | 9 | 0 | 1 | 0 |
| `slow-cooker-stew` | 8 | 0 | 2 | 0 |
| `marathon-plan` | 0 | 9 | 1 | 2 |
| `race-day-nutrition` | 4 | 6 | 3 | 0 |
| `household-budget` | 1 | 0 | 9 | 0 |
| `storm-bulletin` | 0 | 1 | 0 | 9 |

That table is the entire lab. Each row is a **vector** — a list of numbers in a
fixed order where position carries meaning. The first number is always cooking.
Swap two columns and every row becomes a lie.

You already believe, looking at that table, that `roast-chicken` and
`slow-cooker-stew` belong together and that `storm-bulletin` belongs with
nothing. Your job today is to make that belief into arithmetic, so a program
can have it too.

## What you are building

Nine functions in `vectors.py`, in order, each one a few lines:

| # | function | what it does |
| --- | --- | --- |
| 1 | `add(u, v)` | componentwise sum |
| 2 | `subtract(u, v)` | componentwise difference |
| 3 | `scale(k, v)` | multiply every component by `k` |
| 4 | `dot(u, v)` | multiply matching components, add them up — returns one number |
| 5 | `l2_norm(v)` | magnitude: square, add, square-root |
| 6 | `l1_norm(v)` | taxicab length: add the absolute values |
| 7 | `distance(u, v)` | the magnitude of the difference |
| 8 | `normalise(v)` | scale to magnitude 1, keeping direction |
| 9 | `nearest(query, labelled)` | the closest entry in a labelled collection |

Exercise 7 is the one to notice. There is no distance formula to learn:
subtract, then measure. Once you see that, most of the rest of linear algebra
stops looking like a list of formulae to memorise.

## Four numbers to check yourself against

Do these on paper before you run anything. If your code disagrees with the
paper, the code is wrong.

- `l2_norm([3, 4])` — 9 + 16 = 25, so the answer is **5**.
- `l2_norm([2, 3, 6])` — 4 + 9 + 36 = 49, so **7**.
- `distance([1, 2], [4, 6])` — the difference is (−3, −4), 9 + 16 = 25, so **5**.
- `distance(roast-chicken, slow-cooker-stew)` — the difference is (1, 0, −1, 0),
  1 + 0 + 1 + 0 = 2, so **sqrt(2) ≈ 1.4142**.

## The trap, stated in advance

When you finish exercise 8, you will want to write this:

```python
assert l2_norm(normalise(v)) == 1.0
```

Do not. It passes for `[3, 4]` and fails for `[1, 1]`, and your code is correct
in both cases. A float is a binary approximation, and dividing by a square root
and squaring the results back up does not have to land on exactly 1.0. Day 46
covered this; today is where it bites.

Every assertion in this lab uses `math.isclose` or `numpy.allclose` with a
stated tolerance — `rel_tol=1e-9, abs_tol=1e-12`. There is a test whose only
job is to prove, on your machine, that `==` would have failed.

## How to work

```bash
python3 starter/vectors.py       # a progress report: which exercises return something
.venv/bin/pytest starter -q      # the exercise suite
```

Before you start: 1 test passes, 11 are skipped. Finish an exercise, delete the
`@pytest.mark.skip(...)` line above its test, run again. When all 12 pass, run
the reference programs in `examples/` and compare your reasoning with theirs.

## Do not import NumPy in `vectors.py`

Write the loops. NumPy does exactly what you are about to write, only faster,
and `examples/agreement.py` proves it operation by operation on the same
inputs. A reader who wrote the loop understands what the library is doing
before being asked to trust it — and that is the difference between using
NumPy and being at its mercy.

[pytest]
# The starter suite imports `vectors` from this directory, so this directory
# has to be on sys.path. rootdir-relative discovery plus an empty testpaths
# would not do it; adding "." explicitly does.
pythonpath = .
testpaths = .
addopts = -p no:cacheprovider

"""The exercise suite. One test per exercise, plus a worked example.

Run it from the lab directory:

    .venv/bin/pytest starter -q

Before you start, one test passes and nine are skipped. As you finish each
exercise in `vectors.py`, delete the `@pytest.mark.skip(...)` line above its
test and run the suite again.

Every numeric assertion in this file goes through `math.isclose` or
`numpy.allclose` with the tolerance stated below. None of them uses `==`, and
exercise 8 is where you find out why: normalising a vector gives a magnitude
that is 1 to within floating-point error and is sometimes not exactly 1.0. A
test written with `==` would fail on correct code, which is worse than useless
because you would go looking for a bug that is not there.
"""

from __future__ import annotations

import math

import numpy as np
import pytest

import vectors as mine

# The tolerance every assertion in this file uses, stated once so you can see
# exactly how much slack is being allowed. rel_tol handles large numbers,
# abs_tol handles values near zero where a relative tolerance is meaningless.
REL_TOL = 1e-9
ABS_TOL = 1e-12


def close(a, b) -> bool:
    return math.isclose(a, b, rel_tol=REL_TOL, abs_tol=ABS_TOL)


def allclose(a, b) -> bool:
    return bool(np.allclose(a, b, rtol=REL_TOL, atol=ABS_TOL))


CATALOGUE = {
    "roast-chicken":      [9, 0, 1, 0],
    "slow-cooker-stew":   [8, 0, 2, 0],
    "marathon-plan":      [0, 9, 1, 2],
    "race-day-nutrition": [4, 6, 3, 0],
    "household-budget":   [1, 0, 9, 0],
    "storm-bulletin":     [0, 1, 0, 9],
}


# ---------------------------------------------------------------------------
# Worked example — this one passes before you write anything. Read it first;
# it is the shape every test below follows.
# ---------------------------------------------------------------------------


def test_worked_example_the_guard_refuses_a_dimension_mismatch():
    """check_same_dimension is provided. This is what a finished test looks like."""
    mine.check_same_dimension([1, 2], [3, 4])  # same length: no complaint
    with pytest.raises(ValueError, match="dimension mismatch"):
        mine.check_same_dimension([1, 2], [3, 4, 5])


# ---------------------------------------------------------------------------
# Exercise 1 — add
# ---------------------------------------------------------------------------


@pytest.mark.skip(reason="exercise 1: implement add() in vectors.py, then delete this line")
def test_exercise_1_add():
    assert allclose(mine.add([1, 2, 3], [10, 20, 30]), [11, 22, 33])
    # Addition is commutative: the parallelogram has two equal sides.
    assert allclose(mine.add([3, -4], [1, 7]), mine.add([1, 7], [3, -4]))
    with pytest.raises(ValueError, match="dimension mismatch"):
        mine.add([1, 2], [1, 2, 3])


# ---------------------------------------------------------------------------
# Exercise 2 — subtract
# ---------------------------------------------------------------------------


@pytest.mark.skip(reason="exercise 2: implement subtract() in vectors.py, then delete this line")
def test_exercise_2_subtract():
    assert allclose(mine.subtract([4, 6], [1, 2]), [3, 4])
    # A vector minus itself is the zero vector.
    assert allclose(mine.subtract([7, -1, 4], [7, -1, 4]), [0, 0, 0])
    with pytest.raises(ValueError, match="dimension mismatch"):
        mine.subtract([1, 2], [1, 2, 3])


# ---------------------------------------------------------------------------
# Exercise 3 — scale
# ---------------------------------------------------------------------------


@pytest.mark.skip(reason="exercise 3: implement scale() in vectors.py, then delete this line")
def test_exercise_3_scale():
    assert allclose(mine.scale(3, [1, 2]), [3, 6])
    assert allclose(mine.scale(-1, [1, 2]), [-1, -2])
    assert allclose(mine.scale(0, [1, 2]), [0, 0])
    assert allclose(mine.scale(1, [4, -9]), [4, -9])


# ---------------------------------------------------------------------------
# Exercise 4 — dot
# ---------------------------------------------------------------------------


@pytest.mark.skip(reason="exercise 4: implement dot() in vectors.py, then delete this line")
def test_exercise_4_dot():
    # 1*4 + 2*5 + 3*6 = 4 + 10 + 18 = 32
    assert close(mine.dot([1, 2, 3], [4, 5, 6]), 32)
    # Perpendicular arrows have a dot product of zero.
    assert close(mine.dot([1, 0], [0, 1]), 0)
    assert close(mine.dot([3, 4], [-4, 3]), 0)
    # A number came back, not a list.
    assert not isinstance(mine.dot([1, 2], [3, 4]), list)
    # NumPy agrees on the same inputs.
    assert close(mine.dot([1, 2, 3], [4, 5, 6]), float(np.dot([1, 2, 3], [4, 5, 6])))


# ---------------------------------------------------------------------------
# Exercise 5 — l2_norm
# ---------------------------------------------------------------------------


@pytest.mark.skip(reason="exercise 5: implement l2_norm() in vectors.py, then delete this line")
def test_exercise_5_l2_norm():
    assert close(mine.l2_norm([3, 4]), 5)  # sqrt(9 + 16)
    assert close(mine.l2_norm([2, 3, 6]), 7)  # sqrt(4 + 9 + 36)
    assert close(mine.l2_norm([1, 2, 2]), 3)  # sqrt(1 + 4 + 4)
    assert close(mine.l2_norm([3, 4, 12]), 13)  # sqrt(9 + 16 + 144)
    assert close(mine.l2_norm([0, 0, 0]), 0)
    # Squaring removes the signs, so a reversed vector has the same magnitude.
    assert close(mine.l2_norm([-3, -4]), 5)
    # NumPy agrees.
    assert close(mine.l2_norm([3, 4, 12]), float(np.linalg.norm([3, 4, 12])))


# ---------------------------------------------------------------------------
# Exercise 6 — l1_norm
# ---------------------------------------------------------------------------


@pytest.mark.skip(reason="exercise 6: implement l1_norm() in vectors.py, then delete this line")
def test_exercise_6_l1_norm():
    assert close(mine.l1_norm([3, 4]), 7)
    assert close(mine.l1_norm([-3, 4]), 7)  # absolute values, so signs vanish
    assert close(mine.l1_norm([2, 2, 2]), 6)
    assert close(mine.l1_norm([4, 0, 0]), 4)
    assert close(mine.l1_norm([0, 0, 0]), 0)
    # The same vector, two different sizes. Neither is wrong.
    assert not close(mine.l1_norm([3, 4]), mine.l2_norm([3, 4]))
    assert close(mine.l1_norm([3, 4, 12]), float(np.linalg.norm([3, 4, 12], ord=1)))


# ---------------------------------------------------------------------------
# Exercise 7 — distance
# ---------------------------------------------------------------------------


@pytest.mark.skip(reason="exercise 7: implement distance() in vectors.py, then delete this line")
def test_exercise_7_distance():
    assert close(mine.distance([1, 2], [4, 6]), 5)
    assert close(mine.distance([0, 0, 0], [2, 3, 6]), 7)
    assert close(mine.distance([10, 10], [10, 10]), 0)
    # It is symmetric, because reversing the difference does not change its length.
    assert close(mine.distance([1, 2], [4, 6]), mine.distance([4, 6], [1, 2]))
    # And it really is the norm of the difference, by construction.
    assert close(
        mine.distance([9, 0, 1, 0], [1, 0, 9, 0]),
        mine.l2_norm(mine.subtract([9, 0, 1, 0], [1, 0, 9, 0])),
    )


# ---------------------------------------------------------------------------
# Exercise 8 — normalise, and the float trap
# ---------------------------------------------------------------------------


@pytest.mark.skip(reason="exercise 8: implement normalise() in vectors.py, then delete this line")
def test_exercise_8_normalise():
    assert allclose(mine.normalise([3, 4]), [0.6, 0.8])

    # Magnitude 1 for every one of these — to tolerance, never with ==.
    for v in ([3, 4], [1, 2, 2], [1, 1], [1, 1, 1], [0.1, 0.2, 0.3], [2, 3, 6]):
        assert close(mine.l2_norm(mine.normalise(v)), 1.0)

    # Direction survives: scaling the unit vector back up recovers the original.
    v = [3, 4]
    assert allclose(mine.scale(mine.l2_norm(v), mine.normalise(v)), v)

    # Magnitude does not survive, which is the whole point of normalising.
    assert not close(mine.l2_norm(mine.normalise(v)), mine.l2_norm(v))

    # The zero vector has no direction and cannot be normalised.
    with pytest.raises(ValueError, match="zero vector"):
        mine.normalise([0, 0, 0])


@pytest.mark.skip(reason="exercise 8: implement normalise() in vectors.py, then delete this line")
def test_exercise_8_why_you_must_not_use_equals_equals():
    """Proof, on this machine, that `== 1.0` is the wrong test.

    At least one of these six vectors normalises to a magnitude that is not
    exactly 1.0. Every one of them is 1.0 to tolerance. If you had written
    `assert mine.l2_norm(unit) == 1.0`, correct code would have failed.
    """
    cases = [[3, 4], [1, 2, 2], [1, 1], [1, 1, 1], [0.1, 0.2, 0.3], [2, 3, 6]]
    magnitudes = [mine.l2_norm(mine.normalise(v)) for v in cases]
    assert all(close(m, 1.0) for m in magnitudes)
    assert any(m != 1.0 for m in magnitudes)


# ---------------------------------------------------------------------------
# Exercise 9 — nearest, over the catalogue, under both norms
# ---------------------------------------------------------------------------


@pytest.mark.skip(reason="exercise 9: implement nearest() in vectors.py, then delete this line")
def test_exercise_9_nearest_neighbour_in_the_catalogue():
    winner, score = mine.nearest(
        CATALOGUE["roast-chicken"], CATALOGUE, exclude="roast-chicken"
    )
    assert winner == "slow-cooker-stew"
    # (9,0,1,0) - (8,0,2,0) = (1,0,-1,0); 1 + 1 = 2; sqrt(2)
    assert close(score, math.sqrt(2))

    expected = {
        "roast-chicken": "slow-cooker-stew",
        "slow-cooker-stew": "roast-chicken",
        "marathon-plan": "race-day-nutrition",
        "race-day-nutrition": "marathon-plan",
        "household-budget": "race-day-nutrition",
        "storm-bulletin": "marathon-plan",
    }
    for item, neighbour in expected.items():
        assert mine.nearest(CATALOGUE[item], CATALOGUE, exclude=item)[0] == neighbour

    # Without exclude, everything is its own nearest neighbour at distance 0.
    same, zero_score = mine.nearest(CATALOGUE["storm-bulletin"], CATALOGUE)
    assert same == "storm-bulletin"
    assert close(zero_score, 0)

    with pytest.raises(ValueError):
        mine.nearest([1, 2], {})


@pytest.mark.skip(reason="exercise 9: implement nearest() in vectors.py, then delete this line")
def test_exercise_9_l1_and_l2_choose_different_winners():
    """The two norms rank the same two candidates in opposite orders.

        spike  = (4, 0, 0):  L1 = 4,  L2 = 4
        spread = (2, 2, 2):  L1 = 6,  L2 = sqrt(12) = 3.4641...

    Squaring is what does it: one component of 4 contributes 16, while three
    components of 2 contribute 4 each.
    """
    query = [0, 0, 0]
    candidates = {"spike": [4, 0, 0], "spread": [2, 2, 2]}

    l2_winner, l2_score = mine.nearest(query, candidates, metric=mine.distance)
    l1_winner, l1_score = mine.nearest(query, candidates, metric=mine.l1_distance)

    assert l2_winner == "spread"
    assert close(l2_score, math.sqrt(12))
    assert l1_winner == "spike"
    assert close(l1_score, 4)
    assert l1_winner != l2_winner

"""YOUR WORK GOES HERE — nine numbered exercises.

Every function below is a working skeleton: it runs, it returns `None`, and it
tells you honestly that it is not finished yet. Replace each `return None` with
real code, in order. Nothing here needs NumPy — that is the point. You write
the loop, and only then do you compare it with the library.

Run this file at any time to see how far you have got:

    python3 starter/vectors.py

Run the exercise suite to check your work:

    .venv/bin/pytest starter -q

Nine tests are skipped until you finish the matching exercise. Remove the
`@pytest.mark.skip` line above a test in `starter/test_starter.py` once you
have implemented its function.

A vector here is an ordinary Python list of numbers: `[3, 4]`, `[9, 0, 1, 0]`.
Position means something — the first component of every article vector in this
lab counts mentions of cooking — so the order never changes and two vectors are
only comparable if they have the same length.
"""

from __future__ import annotations

import math

# --------------------------------------------------------------------------
# Provided for you: the guard every two-vector operation needs.
# Call this at the top of any function that takes two vectors.
# --------------------------------------------------------------------------


def check_same_dimension(u, v) -> None:
    """Raise ValueError unless u and v have the same number of components."""
    if len(u) != len(v):
        raise ValueError(
            f"dimension mismatch: {len(u)} and {len(v)} "
            "— vectors must have the same number of components"
        )


# --------------------------------------------------------------------------
# EXERCISE 1 — add
#
# Return a new list whose i-th entry is u[i] + v[i].
#   add([1, 2, 3], [10, 20, 30])  ->  [11, 22, 33]
#
# Call check_same_dimension(u, v) first. A list comprehension over
# zip(u, v) is the shortest way, but a plain for-loop is just as good.
# --------------------------------------------------------------------------


def add(u, v):
    return None


# --------------------------------------------------------------------------
# EXERCISE 2 — subtract
#
# Return a new list whose i-th entry is u[i] - v[i].
#   subtract([4, 6], [1, 2])  ->  [3, 4]
#
# Geometrically u - v is the arrow from the tip of v to the tip of u. Hold on
# to that: exercise 7 depends on it.
# --------------------------------------------------------------------------


def subtract(u, v):
    return None


# --------------------------------------------------------------------------
# EXERCISE 3 — scale
#
# Multiply every component by the number k and return the new list.
#   scale(3, [1, 2])   ->  [3, 6]
#   scale(-1, [1, 2])  ->  [-1, -2]
#
# Note what this does and does not change: a positive k changes the magnitude
# and leaves the direction alone; a negative k reverses the direction too.
# --------------------------------------------------------------------------


def scale(k, v):
    return None


# --------------------------------------------------------------------------
# EXERCISE 4 — dot
#
# Multiply matching components, then add up the results. Return ONE NUMBER,
# not a list.
#   dot([1, 2, 3], [4, 5, 6])  ->  1*4 + 2*5 + 3*6 = 32
#
# Check your work on a case you can see: dot([1, 0], [0, 1]) must be 0,
# because those two arrows are at right angles.
# --------------------------------------------------------------------------


def dot(u, v):
    return None


# --------------------------------------------------------------------------
# EXERCISE 5 — l2_norm  (the magnitude)
#
# Square every component, add the squares, take the square root.
#   l2_norm([3, 4])     ->  sqrt(9 + 16)      = sqrt(25) = 5
#   l2_norm([2, 3, 6])  ->  sqrt(4 + 9 + 36)  = sqrt(49) = 7
#
# Use math.sqrt, imported at the top of this file. This is Pythagoras, applied
# one dimension at a time, and it works in any number of dimensions.
# --------------------------------------------------------------------------


def l2_norm(v):
    return None


# --------------------------------------------------------------------------
# EXERCISE 6 — l1_norm  (the taxicab length)
#
# Add up the absolute values of the components. No squaring, no square root.
#   l1_norm([3, 4])   ->  3 + 4 = 7
#   l1_norm([-3, 4])  ->  3 + 4 = 7
#
# The same vector has an L1 of 7 and an L2 of 5. Both are correct answers to
# "how big is this", and exercise 9 shows they can disagree about which of two
# candidates is nearer.
# --------------------------------------------------------------------------


def l1_norm(v):
    return None


# --------------------------------------------------------------------------
# EXERCISE 7 — distance
#
# The distance between two vectors is the MAGNITUDE OF THEIR DIFFERENCE.
# There is no new formula. Subtract, then measure.
#   distance([1, 2], [4, 6])  ->  |[-3, -4]| = 5
#
# Write this in terms of the two functions you have already written.
# --------------------------------------------------------------------------


def distance(u, v):
    return None


# --------------------------------------------------------------------------
# EXERCISE 8 — normalise
#
# Scale a vector so its magnitude becomes 1, keeping its direction.
# Dividing by the magnitude is the same as scaling by 1 / magnitude.
#   normalise([3, 4])  ->  [0.6, 0.8]
#
# The zero vector has magnitude 0 and no direction. Raise ValueError with a
# message containing the words "zero vector" rather than dividing by zero.
#
# WARNING, and it is the point of the exercise: the magnitude of your result
# will be 1 to within floating-point error and sometimes NOT exactly 1.0.
# Never test it with ==. The suite uses math.isclose, and so should you.
# --------------------------------------------------------------------------


def normalise(v):
    return None


# --------------------------------------------------------------------------
# EXERCISE 9 — nearest
#
# `labelled` is a dict of name -> vector. Return the (name, score) pair with
# the smallest `metric(query, vector)`.
#
#   nearest([9, 0, 1, 0], CATALOGUE, exclude="roast-chicken")
#       ->  ("slow-cooker-stew", 1.4142135623730951)
#
# `exclude` skips one label, which is what you want when the query is itself a
# member of the collection — otherwise everything's nearest neighbour is
# itself at distance 0, which is true and useless.
#
# `metric` defaults to `distance`, so calling nearest(..., metric=l1_distance)
# answers the same question under the other norm. Break ties by label so the
# answer is deterministic: min(candidates, key=lambda pair: (pair[1], pair[0])).
#
# Raise ValueError if there are no candidates left to compare against.
# --------------------------------------------------------------------------


def l1_distance(u, v):
    """Provided: the L1 version of exercise 7, once exercises 2 and 6 are done."""
    return l1_norm(subtract(u, v))


def nearest(query, labelled, *, metric=None, exclude=None):
    if metric is None:
        metric = distance
    return None


# --------------------------------------------------------------------------
# The catalogue the exercises are checked against. Six short articles, four
# hand-counted features: cooking, running, money, weather.
# --------------------------------------------------------------------------

FEATURES = ("cooking", "running", "money", "weather")

CATALOGUE = {
    "roast-chicken":      [9, 0, 1, 0],
    "slow-cooker-stew":   [8, 0, 2, 0],
    "marathon-plan":      [0, 9, 1, 2],
    "race-day-nutrition": [4, 6, 3, 0],
    "household-budget":   [1, 0, 9, 0],
    "storm-bulletin":     [0, 1, 0, 9],
}


# --------------------------------------------------------------------------
# Progress report — run this file directly to see it.
# --------------------------------------------------------------------------

EXERCISES = [
    (1, "add", lambda: add([1, 2, 3], [10, 20, 30])),
    (2, "subtract", lambda: subtract([4, 6], [1, 2])),
    (3, "scale", lambda: scale(3, [1, 2])),
    (4, "dot", lambda: dot([1, 2, 3], [4, 5, 6])),
    (5, "l2_norm", lambda: l2_norm([3, 4])),
    (6, "l1_norm", lambda: l1_norm([3, 4])),
    (7, "distance", lambda: distance([1, 2], [4, 6])),
    (8, "normalise", lambda: normalise([3, 4])),
    (9, "nearest", lambda: nearest([9, 0, 1, 0], CATALOGUE, exclude="roast-chicken")),
]


def main() -> int:
    print("Day 099 starter — Vectors You Can Hold")
    print()
    done = 0
    for number, name, probe in EXERCISES:
        try:
            result = probe()
        except Exception as exc:  # noqa: BLE001 - a partial answer is expected
            print(f"  {number}. {name:<12} raised {type(exc).__name__}: {exc}")
            continue
        if result is None:
            print(f"  {number}. {name:<12} not started")
        else:
            done += 1
            print(f"  {number}. {name:<12} returns {result!r}")
    print()
    print(f"{done} of {len(EXERCISES)} exercises return something.")
    if done < len(EXERCISES):
        print("Keep going, then run:  .venv/bin/pytest starter -q")
    else:
        print("All nine return a value. Now check them:  .venv/bin/pytest starter -q")
    print()
    print(f"(math.sqrt is already imported for you: math.sqrt(25) = {math.sqrt(25)})")
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

#!/usr/bin/env bash
# Tests for the Day 099 lab. Run from the lab directory:
#   bash tests/run_tests.sh
#
# This harness proves the claims the lesson makes, and proves them by running
# the code rather than by reading it:
#
#   * every hand-computed magnitude and distance in the lesson comes out of
#     the code with the value a reader gets on paper;
#   * the pure-Python implementation and NumPy agree operation by operation on
#     the same inputs, to a stated tolerance and never with ==;
#   * normalising really does produce a magnitude that is sometimes not
#     exactly 1.0 on this machine, which is the bug the lab exists to teach;
#   * L1 and L2 really do rank the same two candidates in opposite orders;
#   * the embedding's nearest-neighbour answers are the ones the lesson quotes;
#   * the starter suite is not vacuous: it goes fully green against the
#     reference implementation, and RED when one rule is broken.
#
# Deterministic, non-interactive, offline. Exits 0 only if every check passes.
set -u

export PYTHONDONTWRITEBYTECODE=1

lab_dir="$(cd "$(dirname "${BASH_SOURCE[0]}")/.." && pwd)"

# Bytecode left by an EARLIER command is not this run's litter. The README
# documents `pytest starter -q`, and running it writes .pyc files that would
# then fail the cleanliness check at the end of this script -- failing the
# reader for following the instructions. Clearing them here makes that final
# check measure what it claims to: what THIS run left behind. `.venv` is
# untouched, because the packages' own bytecode is theirs, not ours.
find "${lab_dir}" -name '.venv' -prune -o -type d -name '__pycache__' -exec rm -rf {} + 2>/dev/null || true
find "${lab_dir}" -name '.venv' -prune -o -type d -name '.pytest_cache' -exec rm -rf {} + 2>/dev/null || true

failures=0
checks=0

check() {
  local label="$1" ok="$2"
  checks=$((checks + 1))
  if [ "${ok}" = "yes" ]; then
    echo "  ok: ${label}"
  else
    echo "  FAIL: ${label}"
    failures=$((failures + 1))
  fi
}

contains() {
  # contains <label> <haystack> <needle>
  case "$2" in
    *"$3"*) check "$1" "yes" ;;
    *) check "$1" "no" ;;
  esac
}

# Resolve the tools: an explicit override, then this lab's own virtual
# environment, then whatever is on PATH. Fails loudly with instructions rather
# than skipping silently — a suite that quietly does nothing is worse than one
# that stops.
resolve_tool() {
  local tool="$1" override="$2"
  if [ -n "${override}" ] && [ -x "${override}" ]; then echo "${override}"; return 0; fi
  if [ -x "${lab_dir}/.venv/bin/${tool}" ]; then echo "${lab_dir}/.venv/bin/${tool}"; return 0; fi
  if command -v "${tool}" >/dev/null 2>&1; then command -v "${tool}"; return 0; fi
  return 1
}

install_hint() {
  echo "  Install this lab's dependencies with:" >&2
  echo "    python3 -m venv .venv" >&2
  echo "    .venv/bin/pip install -r requirements/requirements.txt" >&2
  echo "  Or point this suite at an existing environment:" >&2
  echo "    PYTHON=/path/to/python3 PYTEST=/path/to/pytest bash tests/run_tests.sh" >&2
}

pytest_bin="$(resolve_tool pytest "${PYTEST:-}")" || {
  echo "FAIL: pytest not found." >&2
  install_hint
  exit 1
}

# The Python that owns that pytest is the one with numpy installed, unless an
# explicit PYTHON says otherwise.
if [ -n "${PYTHON:-}" ] && [ -x "${PYTHON}" ]; then
  python_bin="${PYTHON}"
else
  python_bin="$(dirname "${pytest_bin}")/python3"
  [ -x "${python_bin}" ] || python_bin="$(command -v python3 || true)"
fi
if [ -z "${python_bin}" ] || [ ! -x "${python_bin}" ]; then
  echo "FAIL: python3 not found." >&2
  install_hint
  exit 1
fi

if ! "${python_bin}" -c "import numpy" >/dev/null 2>&1; then
  echo "FAIL: numpy is not importable from ${python_bin}." >&2
  install_hint
  exit 1
fi

echo "Day 099 — Vectors You Can Hold"
echo

# --------------------------------------------------------------------------
echo "1. The tools and the versions this lab was written against"
# --------------------------------------------------------------------------

echo "     python  $("${python_bin}" -c 'import sys; print(sys.version.split()[0])')"
versions="$("${python_bin}" - <<'PY'
from importlib.metadata import version
for name in ("numpy", "pytest"):
    try:
        print(f"{name}=={version(name)}")
    except Exception:
        print(f"{name}==<not installed>")
PY
)"
printf '%s\n' "${versions}" | sed 's/^/     /'

for pin in "numpy==2.5.2" "pytest==9.1.1"; do
  contains "installed ${pin} matches requirements/requirements.txt" "${versions}" "${pin}"
done

# The lesson describes PyTorch, JAX and pandas from their documentation and
# reproduces no output from any of them. These checks keep that claim honest by
# confirming they really are absent here.
for absent in torch jax pandas; do
  if "${python_bin}" -c "import ${absent}" >/dev/null 2>&1; then
    check "${absent} is absent, as the lesson states" "no"
  else
    check "${absent} is absent, as the lesson states" "yes"
  fi
done

# --------------------------------------------------------------------------
echo
echo "2. The reference suite passes"
# --------------------------------------------------------------------------

tests_out="$(cd "${lab_dir}" && "${pytest_bin}" tests -q -p no:cacheprovider 2>&1)"
tests_exit=$?
if [ "${tests_exit}" -eq 0 ]; then
  check "pytest tests exits 0" "yes"
else
  check "pytest tests exits 0 (got ${tests_exit})" "no"
  printf '%s\n' "${tests_out}" | tail -40
fi
contains "pytest tests reports 79 passed" "${tests_out}" "79 passed"

collected="$(cd "${lab_dir}" && "${pytest_bin}" tests --collect-only -q -p no:cacheprovider 2>&1)"
for test_id in \
  "test_l2_norm_matches_the_hand_computed_answer" \
  "test_distance_is_the_norm_of_the_difference_by_construction" \
  "test_comparing_a_normalised_norm_with_exact_equality_really_does_fail" \
  "test_numpy_agrees_on_every_pairwise_distance" \
  "test_the_two_cooking_articles_are_the_closest_pair_in_the_catalogue" \
  "test_l1_and_l2_disagree_about_which_candidate_is_nearest" \
  "test_normalising_changes_the_nearest_article_for_a_short_query" \
  "test_the_triangle_inequality_holds"
do
  contains "collection finds ${test_id}" "${collected}" "${test_id}"
done

# The rule the whole lab is built on: no float is compared with == or !=
# inside an assertion. Every numeric assertion goes through math.isclose or
# numpy.allclose. This grep is the enforcement, and it is deliberate.
bad_float_asserts="$(grep -nE '^\s*assert .*[0-9]\.[0-9].*[!=]=' \
  "${lab_dir}/tests/test_vectors.py" "${lab_dir}/starter/test_starter.py" 2>/dev/null \
  | grep -v 'm != 1.0' | grep -v 'n != 1.0' || true)"
if [ -n "${bad_float_asserts}" ]; then
  check "no test compares a float with == or != (except the two that prove the trap)" "no"
  printf '%s\n' "${bad_float_asserts}" | sed 's/^/     /'
else
  check "no test compares a float with == or != (except the two that prove the trap)" "yes"
fi

# And the tolerance is stated in both suites rather than hidden.
for suite in tests/test_vectors.py starter/test_starter.py; do
  if grep -q "REL_TOL = 1e-9" "${lab_dir}/${suite}" \
     && grep -q "ABS_TOL = 1e-12" "${lab_dir}/${suite}"; then
    check "${suite} states its tolerance explicitly" "yes"
  else
    check "${suite} states its tolerance explicitly" "no"
  fi
done

# --------------------------------------------------------------------------
echo
echo "3. The hand-computable answers really are what the code produces"
# --------------------------------------------------------------------------

byhand_out="$(cd "${lab_dir}/examples" && "${python_bin}" byhand.py 2>&1)"
byhand_exit=$?
if [ "${byhand_exit}" -eq 0 ]; then
  check "examples/byhand.py exits 0" "yes"
else
  check "examples/byhand.py exits 0 (got ${byhand_exit})" "no"
fi

for fragment in \
  '= sqrt(9 + 16)' \
  '= sqrt(25)' \
  '= 5          computed: 5.0   agrees: True' \
  '= sqrt(4 + 9 + 36)' \
  '= 7          computed: 7.0   agrees: True' \
  '= sqrt(1 + 4 + 4)' \
  '= 3          computed: 3.0   agrees: True' \
  '= |[-3, -4]|' \
  '[3, 4]       L1 = 7.0000 L2 = 5.0000' \
  '[2, 2, 2]    L1 = 6.0000 L2 = 3.4641' \
  'all exact cases agree: True'
do
  contains "byhand shows: ${fragment}" "${byhand_out}" "${fragment}"
done

# --------------------------------------------------------------------------
echo
echo "4. Pure Python and NumPy agree, operation by operation"
# --------------------------------------------------------------------------

agree_out="$(cd "${lab_dir}/examples" && "${python_bin}" agreement.py 2>&1)"
agree_exit=$?
if [ "${agree_exit}" -eq 0 ]; then
  check "examples/agreement.py exits 0" "yes"
else
  check "examples/agreement.py exits 0 (got ${agree_exit})" "no"
fi

for fragment in \
  'every operation agrees: True' \
  'l2_norm(u)            13.0                              13.0                              True' \
  'dot(u, v)             55.0                              55.0                              True' \
  'matrix shape        = (3, 4)' \
  'norms of all rows   = [9.0554 8.2462 9.2736]' \
  'distances (NumPy)   = [8.0623 7.2801 9.3274]' \
  'ours  : ValueError: dimension mismatch: 2 and 3'
do
  contains "agreement shows: ${fragment}" "${agree_out}" "${fragment}"
done

# Count the agreement lines rather than trusting the summary line alone.
agree_true="$(printf '%s\n' "${agree_out}" | grep -c 'True$')"
if [ "${agree_true}" -ge 14 ]; then
  check "at least 14 individual agreement checks came back True (${agree_true})" "yes"
else
  check "at least 14 individual agreement checks came back True (${agree_true})" "no"
fi
if printf '%s\n' "${agree_out}" | grep -q 'False$'; then
  check "no agreement check came back False" "no"
else
  check "no agreement check came back False" "yes"
fi

# --------------------------------------------------------------------------
echo
echo "5. Normalisation, and the == trap it hides"
# --------------------------------------------------------------------------

norm_out="$(cd "${lab_dir}/examples" && "${python_bin}" normalise.py 2>&1)"
norm_exit=$?
if [ "${norm_exit}" -eq 0 ]; then
  check "examples/normalise.py exits 0" "yes"
else
  check "examples/normalise.py exits 0 (got ${norm_exit})" "no"
fi

for fragment in \
  'isclose 1.0 : 7 of 7' \
  '0.9999999999999999' \
  'cannot normalise the zero vector' \
  'recovers v: True'
do
  contains "normalise shows: ${fragment}" "${norm_out}" "${fragment}"
done

# The load-bearing claim: at least one vector normalises to something that is
# NOT exactly 1.0. If that ever stops being true on some machine, this check
# fails loudly rather than the lesson quietly telling a lie.
exact_line="$(printf '%s\n' "${norm_out}" | grep 'exactly 1.0 :' || true)"
exact_count="$(printf '%s' "${exact_line}" | awk '{print $4}')"
total_count="$(printf '%s' "${exact_line}" | awk '{print $6}')"
if [ -n "${exact_count}" ] && [ "${exact_count}" -lt "${total_count}" ]; then
  check "at least one normalised vector is NOT exactly 1.0 (${exact_count} of ${total_count} were)" "yes"
else
  check "at least one normalised vector is NOT exactly 1.0 — the == trap did not reproduce here" "no"
fi

# --------------------------------------------------------------------------
echo
echo "6. L1 and L2 rank the same two candidates in opposite orders"
# --------------------------------------------------------------------------

norms_out="$(cd "${lab_dir}/examples" && "${python_bin}" norms.py 2>&1)"
norms_exit=$?
if [ "${norms_exit}" -eq 0 ]; then
  check "examples/norms.py exits 0" "yes"
else
  check "examples/norms.py exits 0 (got ${norms_exit})" "no"
fi

for fragment in \
  'L2 = sqrt(16 + 0 + 0) = 4.0000' \
  'L2 = sqrt(4 + 4 + 4) = 3.4641' \
  'nearest under L2: spread' \
  'nearest under L1: spike' \
  'Both cases produced a disagreement: True'
do
  contains "norms shows: ${fragment}" "${norms_out}" "${fragment}"
done

disagreements="$(printf '%s\n' "${norms_out}" | grep -c 'the two norms disagree: True')"
if [ "${disagreements}" -eq 2 ]; then
  check "both cases reported a disagreement (${disagreements})" "yes"
else
  check "both cases reported a disagreement (got ${disagreements})" "no"
fi

# --------------------------------------------------------------------------
echo
echo "7. The embedding answers the question it was built for"
# --------------------------------------------------------------------------

embed_out="$(cd "${lab_dir}/examples" && "${python_bin}" embeddings.py 2>&1)"
embed_exit=$?
if [ "${embed_exit}" -eq 0 ]; then
  check "examples/embeddings.py exits 0" "yes"
else
  check "examples/embeddings.py exits 0 (got ${embed_exit})" "no"
fi

for fragment in \
  '[9, 0, 1, 0] - [8, 0, 2, 0] = [1, 0, -1, 0]' \
  'squares: 1 + 0 + 1 + 0 = 2' \
  'sqrt(2) = 1.4142' \
  'squares: 64 + 0 + 64 + 0 = 128' \
  'sqrt(128) = 11.3137' \
  'roast-chicken        -> slow-cooker-stew     at 1.4142' \
  'marathon-plan        -> race-day-nutrition   at 5.7446' \
  'household-budget     -> race-day-nutrition   at 9.0000' \
  'storm-bulletin       -> marathon-plan        at 10.6771' \
  'distance after normalising both = 0.0000' \
  'nearest on raw counts : slow-cooker-stew at 7.2801' \
  'nearest normalised    : roast-chicken at 0.1106' \
  'they disagree         : True' \
  'raw rank of roast-chicken        : 3' \
  'normalised rank of roast-chicken : 1' \
  'Closest pair in the whole catalogue: roast-chicken and slow-cooker-stew at 1.4142'
do
  contains "embeddings shows: ${fragment}" "${embed_out}" "${fragment}"
done

# --------------------------------------------------------------------------
echo
echo "8. The starter is runnable before you start, and honest about it"
# --------------------------------------------------------------------------

starter_out="$(cd "${lab_dir}" && "${pytest_bin}" starter -q -p no:cacheprovider 2>&1)"
starter_exit=$?
if [ "${starter_exit}" -eq 0 ]; then
  check "pytest starter exits 0 with the exercises unfinished" "yes"
else
  check "pytest starter exits 0 with the exercises unfinished (got ${starter_exit})" "no"
fi
contains "the starter has 1 worked test and 11 skipped exercises" \
  "${starter_out}" "1 passed, 11 skipped"

progress_out="$(cd "${lab_dir}" && "${python_bin}" starter/vectors.py 2>&1)"
progress_exit=$?
if [ "${progress_exit}" -eq 0 ]; then
  check "starter/vectors.py runs before any exercise is done" "yes"
else
  check "starter/vectors.py runs before any exercise is done (got ${progress_exit})" "no"
fi
contains "starter reports its unfinished state honestly" \
  "${progress_out}" "0 of 9 exercises return something."

# The starter must not import numpy — the whole point is writing the loop first.
if grep -qE '^\s*(import|from)\s+numpy' "${lab_dir}/starter/vectors.py"; then
  check "starter/vectors.py does not import numpy" "no"
else
  check "starter/vectors.py does not import numpy" "yes"
fi
if grep -qE '^\s*(import|from)\s+numpy' "${lab_dir}/examples/vectors.py"; then
  check "examples/vectors.py does not import numpy either" "no"
else
  check "examples/vectors.py does not import numpy either" "yes"
fi

# --------------------------------------------------------------------------
echo
echo "9. The starter suite is not vacuous — green when solved, red when broken"
# --------------------------------------------------------------------------

# Drop the reference implementation in as the student's answer, un-skip
# everything, and demand a fully green run. A suite that cannot tell finished
# work from unfinished is worth nothing.
work="$(mktemp -d "${TMPDIR:-/tmp}/day099-solved.XXXXXX")"
cp "${lab_dir}/examples/vectors.py" "${work}/vectors.py"
cp "${lab_dir}/starter/pytest.ini" "${work}/pytest.ini"
grep -v '^@pytest\.mark\.skip' "${lab_dir}/starter/test_starter.py" > "${work}/test_starter.py"

solved_out="$(cd "${work}" && "${pytest_bin}" . -q -p no:cacheprovider 2>&1)"
solved_exit=$?
if [ "${solved_exit}" -eq 0 ]; then
  check "the starter suite goes fully green against the finished implementation" "yes"
else
  check "the starter suite goes fully green against the finished implementation (exit ${solved_exit})" "no"
  printf '%s\n' "${solved_out}" | tail -20
fi
contains "all 12 starter tests pass once the exercises are done" "${solved_out}" "12 passed"

# Now break exactly one thing — make l2_norm forget the square root, which is
# the single most common way to get this wrong — and demand the suite FAILS.
"${python_bin}" - "${work}/vectors.py" <<'PY'
import sys
from pathlib import Path

path = Path(sys.argv[1])
text = path.read_text(encoding="utf-8")
broken = text.replace(
    "    return math.sqrt(sum(a * a for a in v))",
    "    return sum(a * a for a in v)",
)
assert broken != text, "the l2_norm body was not found — this check would be vacuous"
path.write_text(broken, encoding="utf-8")
PY
broken_out="$(cd "${work}" && "${pytest_bin}" . -q -p no:cacheprovider 2>&1)"
broken_exit=$?
if [ "${broken_exit}" -ne 0 ]; then
  check "dropping the square root from l2_norm makes the suite FAIL (exit ${broken_exit})" "yes"
else
  check "dropping the square root from l2_norm makes the suite FAIL — it did not, so the norm checks are vacuous" "no"
fi
contains "the failing run names the magnitude test by id" \
  "${broken_out}" "test_exercise_5_l2_norm"
rm -rf "${work}"

# And the same proof for the reference suite: break the distance definition and
# demand tests/ goes red.
work2="$(mktemp -d "${TMPDIR:-/tmp}/day099-broken.XXXXXX")"
mkdir -p "${work2}/examples" "${work2}/tests"
cp "${lab_dir}/examples/vectors.py" "${lab_dir}/examples/embeddings.py" "${work2}/examples/"
cp "${lab_dir}/tests/test_vectors.py" "${work2}/tests/"
"${python_bin}" - "${work2}/examples/vectors.py" <<'PY'
import sys
from pathlib import Path

path = Path(sys.argv[1])
text = path.read_text(encoding="utf-8")
broken = text.replace(
    "    return l2_norm(subtract(u, v))\n\n\ndef l1_distance",
    "    return l2_norm(add(u, v))\n\n\ndef l1_distance",
)
assert broken != text, "the distance body was not found — this check would be vacuous"
path.write_text(broken, encoding="utf-8")
PY
red_out="$(cd "${work2}" && "${pytest_bin}" tests -q -p no:cacheprovider 2>&1)"
red_exit=$?
if [ "${red_exit}" -ne 0 ]; then
  check "swapping subtract for add in distance makes tests/ FAIL (exit ${red_exit})" "yes"
else
  check "swapping subtract for add in distance makes tests/ FAIL — it did not" "no"
fi
contains "the failing run names a distance test by id" \
  "${red_out}" "test_distance_matches_the_hand_computed_answer"
rm -rf "${work2}"

# --------------------------------------------------------------------------
echo
echo "10. The lab left nothing behind and reaches no network"
# --------------------------------------------------------------------------

# `.venv` is deliberately NOT in this list. The README tells the reader to
# create it, and the tool resolution at the top of this file looks inside
# it — so treating it as litter would fail the lab for following its own
# setup instructions.
for stray in "out" ".pytest_cache"; do
  if [ -e "${lab_dir}/${stray}" ]; then
    check "no ${stray} left inside the lab after a full run" "no"
  else
    check "no ${stray} left inside the lab after a full run" "yes"
  fi
done

# `.venv` is pruned from the searches below. A virtual environment ships the
# installed packages' own precompiled bytecode -- hundreds of __pycache__
# directories that came with NumPy or pytest and have nothing to do with
# whether THIS lab tidied up after itself. Without the prune, following the
# README's own setup instructions makes this check fail, which reports a
# problem the reader cannot fix and did not cause.
if find "${lab_dir}" -name '.venv' -prune -o -type d -name '__pycache__' -print -quit 2>/dev/null | grep -q .; then
  check "no __pycache__ left inside the lab after a full run" "no"
else
  check "no __pycache__ left inside the lab after a full run" "yes"
fi

# Nothing here reaches the network at run time. The only network step is the
# one-off pip install described in the README. Restricted to .py files on
# purpose: this script quotes the pattern it searches for, so scanning itself
# would always match.
if find "${lab_dir}/examples" "${lab_dir}/starter" "${lab_dir}/tests" -name '*.py' -print0 2>/dev/null \
     | xargs -0 grep -qE 'requests\.|urlopen|httpx\.|socket\.(create_connection|socket)\(' 2>/dev/null; then
  check "no lab source opens a network connection at run time" "no"
else
  check "no lab source opens a network connection at run time" "yes"
fi

echo
echo "${checks} checks, ${failures} failure(s)."
[ "${failures}" -eq 0 ]

"""The reference suite for the Day 099 lab.

Two rules run through every test in this file.

1. **No float is ever compared with `==`.** Every numeric assertion goes
   through `math.isclose` or `numpy.allclose` with the tolerance stated at the
   top of the file. Where a value happens to come out exact, the test still
   uses a tolerance, because "it was exact on this machine today" is not a
   property you can rely on.

2. **Agreement with NumPy is proved, not assumed.** Every operation the lab
   implements by hand is run again through NumPy on the same inputs, and the
   two results are asserted equal to tolerance. If the loop is wrong, this
   suite says so.
"""

from __future__ import annotations

import math
import sys
from pathlib import Path

import numpy as np
import pytest

sys.path.insert(0, str(Path(__file__).resolve().parents[1] / "examples"))

import vectors as pure  # noqa: E402
from embeddings import CATALOGUE  # noqa: E402

# The tolerance used by every numeric assertion in this file. Stated once, in
# one place, so that a reader can see exactly how much slack the suite allows.
REL_TOL = 1e-9
ABS_TOL = 1e-12


def close(a: float, b: float) -> bool:
    return math.isclose(a, b, rel_tol=REL_TOL, abs_tol=ABS_TOL)


def allclose(a, b) -> bool:
    return bool(np.allclose(a, b, rtol=REL_TOL, atol=ABS_TOL))


# ---------------------------------------------------------------------------
# 1. The operations do what the definitions say
# ---------------------------------------------------------------------------


def test_addition_is_componentwise():
    assert allclose(pure.add([1, 2, 3], [10, 20, 30]), [11, 22, 33])


def test_addition_is_commutative():
    u, v = [3, -4, 0.5], [1, 7, -2]
    assert allclose(pure.add(u, v), pure.add(v, u))


def test_subtraction_is_addition_of_the_negation():
    u, v = [3, 4], [1, -2]
    assert allclose(pure.subtract(u, v), pure.add(u, pure.negate(v)))


def test_subtracting_a_vector_from_itself_gives_the_zero_vector():
    v = [7, -1, 4]
    assert allclose(pure.subtract(v, v), pure.zero(3))


def test_the_zero_vector_is_the_additive_identity():
    v = [7, -1, 4]
    assert allclose(pure.add(v, pure.zero(3)), v)


def test_scaling_by_one_changes_nothing_and_by_zero_gives_the_zero_vector():
    v = [2, -5, 9]
    assert allclose(pure.scale(1, v), v)
    assert allclose(pure.scale(0, v), pure.zero(3))


def test_scaling_multiplies_the_magnitude_by_the_absolute_value_of_the_scalar():
    v = [3, 4]
    for k in (2, 0.5, -3, 1000):
        assert close(pure.l2_norm(pure.scale(k, v)), abs(k) * pure.l2_norm(v))


def test_a_positive_scalar_leaves_the_direction_alone():
    """Same direction means the same unit vector."""
    v = [3, 4]
    assert allclose(pure.normalise(pure.scale(7, v)), pure.normalise(v))


def test_a_negative_scalar_reverses_the_direction():
    v = [3, 4]
    assert allclose(
        pure.normalise(pure.scale(-7, v)), pure.negate(pure.normalise(v))
    )


def test_dot_product_returns_one_number_not_a_vector():
    result = pure.dot([1, 2, 3], [4, 5, 6])
    assert isinstance(result, float)
    # 1*4 + 2*5 + 3*6 = 4 + 10 + 18 = 32
    assert close(result, 32)


def test_dot_product_of_perpendicular_vectors_is_zero():
    assert close(pure.dot([1, 0], [0, 1]), 0)
    assert close(pure.dot([3, 4], [-4, 3]), 0)


def test_dot_of_a_vector_with_itself_is_its_magnitude_squared():
    v = [3, 4, 12]
    assert close(pure.dot(v, v), pure.l2_norm(v) ** 2)


# ---------------------------------------------------------------------------
# 2. Magnitude, checked against answers a human can get on paper
# ---------------------------------------------------------------------------


@pytest.mark.parametrize(
    "vector,expected",
    [
        ([3, 4], 5),  # 9 + 16 = 25
        ([6, 8], 10),  # 36 + 64 = 100
        ([2, 3, 6], 7),  # 4 + 9 + 36 = 49
        ([1, 2, 2], 3),  # 1 + 4 + 4 = 9
        ([3, 4, 12], 13),  # 9 + 16 + 144 = 169
        ([7, 1, 5, 3, 9, 2], 13),  # 49 + 1 + 25 + 9 + 81 + 4 = 169
        ([0, 0, 0], 0),
        ([-3, -4], 5),  # squaring removes the signs
    ],
)
def test_l2_norm_matches_the_hand_computed_answer(vector, expected):
    assert close(pure.l2_norm(vector), expected)


@pytest.mark.parametrize(
    "vector,expected",
    [
        ([3, 4], 7),
        ([1, 2, 2], 5),
        ([-3, -4], 7),
        ([0, 0, 0], 0),
        ([4, 0, 0], 4),
        ([2, 2, 2], 6),
    ],
)
def test_l1_norm_matches_the_hand_computed_answer(vector, expected):
    assert close(pure.l1_norm(vector), expected)


def test_the_norm_of_a_unit_axis_vector_is_one_in_any_dimension():
    for dimension in (1, 2, 3, 10, 300):
        basis = pure.zero(dimension)
        basis[0] = 1.0
        assert close(pure.l2_norm(basis), 1.0)


def test_l1_is_never_smaller_than_l2():
    """A real inequality, not a coincidence: squaring shrinks the small parts."""
    for vector in ([3, 4], [1, 2, 2], [2, 2, 2], [4, 0, 0], [0.5, -0.25, 7]):
        assert pure.l1_norm(vector) >= pure.l2_norm(vector) - ABS_TOL


# ---------------------------------------------------------------------------
# 3. Distance is the magnitude of the difference
# ---------------------------------------------------------------------------


@pytest.mark.parametrize(
    "u,v,expected",
    [
        ([1, 2], [4, 6], 5),  # difference (-3, -4)
        ([0, 0, 0], [2, 3, 6], 7),
        ([1, 1, 1], [2, 3, 3], 3),
        ([10, 10], [10, 10], 0),
    ],
)
def test_distance_matches_the_hand_computed_answer(u, v, expected):
    assert close(pure.distance(u, v), expected)


def test_distance_is_the_norm_of_the_difference_by_construction():
    u, v = [9, 0, 1, 0], [1, 0, 9, 0]
    assert close(pure.distance(u, v), pure.l2_norm(pure.subtract(u, v)))


def test_distance_is_symmetric():
    u, v = [9, 0, 1, 0], [0, 9, 1, 2]
    assert close(pure.distance(u, v), pure.distance(v, u))


def test_distance_from_a_point_to_itself_is_zero():
    for vector in CATALOGUE.values():
        assert close(pure.distance(vector, vector), 0)


def test_the_triangle_inequality_holds():
    """Going via a third point is never shorter than going direct."""
    a, b, c = [1, 2], [7, 1], [4, 9]
    assert pure.distance(a, c) <= pure.distance(a, b) + pure.distance(b, c) + ABS_TOL


# ---------------------------------------------------------------------------
# 4. Normalisation, and the float trap it hides
# ---------------------------------------------------------------------------


@pytest.mark.parametrize(
    "vector",
    [[3, 4], [1, 2, 2], [1, 1], [1, 1, 1], [0.1, 0.2, 0.3], [2, 3, 6], [-5, 12]],
)
def test_a_normalised_vector_has_magnitude_one_to_tolerance(vector):
    assert close(pure.l2_norm(pure.normalise(vector)), 1.0)
    assert pure.is_unit(pure.normalise(vector), rel_tol=REL_TOL, abs_tol=ABS_TOL)


def test_normalising_preserves_direction_but_not_magnitude():
    v = [3, 4]
    unit = pure.normalise(v)
    # Direction preserved: unit is v scaled by a positive number, so scaling it
    # back up by the original magnitude recovers v exactly to tolerance.
    assert allclose(pure.scale(pure.l2_norm(v), unit), v)
    # Magnitude changed: 5 became 1.
    assert not close(pure.l2_norm(unit), pure.l2_norm(v))


def test_comparing_a_normalised_norm_with_exact_equality_really_does_fail():
    """The bug this lab exists to teach, demonstrated rather than asserted.

    At least one of these vectors normalises to a magnitude that is not
    exactly 1.0, so a suite written with `==` would fail on it. If this test
    ever stops finding such a vector, the lesson's claim needs re-checking on
    the machine in question — not silently deleting.
    """
    cases = [[3, 4], [1, 2, 2], [1, 1], [1, 1, 1], [0.1, 0.2, 0.3], [2, 3, 6]]
    norms = [pure.l2_norm(pure.normalise(v)) for v in cases]
    assert all(close(n, 1.0) for n in norms), "every case is 1.0 to tolerance"
    assert any(n != 1.0 for n in norms), (
        "no case departed from exactly 1.0 on this machine; the == trap did "
        "not reproduce here and the lesson's numbers must be re-verified"
    )


def test_the_zero_vector_cannot_be_normalised():
    with pytest.raises(ValueError, match="zero vector"):
        pure.normalise([0, 0, 0])


def test_normalising_an_already_unit_vector_is_a_no_op():
    unit = pure.normalise([3, 4])
    assert allclose(pure.normalise(unit), unit)


# ---------------------------------------------------------------------------
# 5. Dimension mismatches are refused, not silently truncated
# ---------------------------------------------------------------------------


@pytest.mark.parametrize(
    "operation",
    [pure.add, pure.subtract, pure.dot, pure.distance, pure.l1_distance],
)
def test_operations_refuse_vectors_of_different_dimension(operation):
    with pytest.raises(ValueError, match="dimension mismatch"):
        operation([1, 2], [1, 2, 3])


def test_zero_refuses_a_negative_dimension():
    with pytest.raises(ValueError):
        pure.zero(-1)


# ---------------------------------------------------------------------------
# 6. NumPy agrees — proved on the same inputs, not assumed
# ---------------------------------------------------------------------------

U = [3, 4, 12]
V = [1, -2, 5]


def test_numpy_agrees_on_addition_and_subtraction():
    assert allclose(pure.add(U, V), np.array(U) + np.array(V))
    assert allclose(pure.subtract(U, V), np.array(U) - np.array(V))


def test_numpy_agrees_on_scaling():
    assert allclose(pure.scale(2.5, U), 2.5 * np.array(U))


def test_numpy_agrees_on_the_dot_product():
    assert close(pure.dot(U, V), float(np.dot(U, V)))


def test_numpy_agrees_on_the_l2_norm():
    assert close(pure.l2_norm(U), float(np.linalg.norm(U)))


def test_numpy_agrees_on_the_l1_norm():
    assert close(pure.l1_norm(U), float(np.linalg.norm(U, ord=1)))


def test_numpy_agrees_on_distance():
    assert close(
        pure.distance(U, V), float(np.linalg.norm(np.array(U) - np.array(V)))
    )


def test_numpy_agrees_on_normalisation():
    assert allclose(pure.normalise(U), np.array(U) / np.linalg.norm(U))


def test_numpy_agrees_on_every_catalogue_norm_at_once():
    labels = list(CATALOGUE)
    matrix = np.array([CATALOGUE[label] for label in labels], dtype=float)
    assert allclose(
        np.linalg.norm(matrix, axis=1),
        [pure.l2_norm(CATALOGUE[label]) for label in labels],
    )


def test_numpy_agrees_on_every_pairwise_distance():
    labels = list(CATALOGUE)
    matrix = np.array([CATALOGUE[label] for label in labels], dtype=float)
    for i, a in enumerate(labels):
        row = np.linalg.norm(matrix - matrix[i], axis=1)
        expected = [pure.distance(CATALOGUE[a], CATALOGUE[b]) for b in labels]
        assert allclose(row, expected)


# ---------------------------------------------------------------------------
# 7. The embedding: which item is nearest to which
# ---------------------------------------------------------------------------


def test_the_two_cooking_articles_are_the_closest_pair_in_the_catalogue():
    labels = list(CATALOGUE)
    pairs = [
        (pure.distance(CATALOGUE[a], CATALOGUE[b]), a, b)
        for i, a in enumerate(labels)
        for b in labels[i + 1 :]
    ]
    score, a, b = min(pairs)
    assert {a, b} == {"roast-chicken", "slow-cooker-stew"}
    # (9,0,1,0) - (8,0,2,0) = (1,0,-1,0); 1 + 1 = 2; sqrt(2)
    assert close(score, math.sqrt(2))


@pytest.mark.parametrize(
    "item,expected_neighbour",
    [
        ("roast-chicken", "slow-cooker-stew"),
        ("slow-cooker-stew", "roast-chicken"),
        ("marathon-plan", "race-day-nutrition"),
        ("race-day-nutrition", "marathon-plan"),
        ("household-budget", "race-day-nutrition"),
        ("storm-bulletin", "marathon-plan"),
    ],
)
def test_each_article_has_the_expected_nearest_neighbour(item, expected_neighbour):
    winner, _score = pure.nearest(CATALOGUE[item], CATALOGUE, exclude=item)
    assert winner == expected_neighbour


def test_the_budget_to_race_day_distance_is_exactly_nine():
    # (1,0,9,0) - (4,6,3,0) = (-3,-6,6,0); 9 + 36 + 36 = 81; sqrt(81) = 9
    assert close(
        pure.distance(CATALOGUE["household-budget"], CATALOGUE["race-day-nutrition"]),
        9,
    )


def test_nearest_without_exclude_returns_the_item_itself_at_zero():
    winner, score = pure.nearest(CATALOGUE["roast-chicken"], CATALOGUE)
    assert winner == "roast-chicken"
    assert close(score, 0)


def test_nearest_raises_when_there_is_nothing_to_compare_against():
    with pytest.raises(ValueError):
        pure.nearest([1, 2], {}, exclude=None)


def test_pairwise_distances_covers_every_unordered_pair_once():
    result = pure.pairwise_distances(CATALOGUE)
    n = len(CATALOGUE)
    assert len(result) == n * (n - 1) // 2


# ---------------------------------------------------------------------------
# 8. L1 and L2 rank the same candidates differently
# ---------------------------------------------------------------------------


def test_l1_and_l2_disagree_about_which_candidate_is_nearest():
    query = [0, 0, 0]
    candidates = {"spike": [4, 0, 0], "spread": [2, 2, 2]}

    l2_winner, l2_score = pure.nearest(query, candidates, metric=pure.distance)
    l1_winner, l1_score = pure.nearest(query, candidates, metric=pure.l1_distance)

    assert l2_winner == "spread"
    assert close(l2_score, math.sqrt(12))
    assert l1_winner == "spike"
    assert close(l1_score, 4)
    assert l2_winner != l1_winner


def test_the_disagreement_survives_moving_away_from_the_origin():
    """It is the shape of the difference that matters, not the position."""
    query = [10, 10, 10]
    candidates = {"spike": [14, 10, 10], "spread": [12, 12, 12]}
    assert pure.nearest(query, candidates, metric=pure.distance)[0] == "spread"
    assert pure.nearest(query, candidates, metric=pure.l1_distance)[0] == "spike"


def test_numpy_agrees_about_the_disagreement():
    query = np.zeros(3)
    spike = np.array([4.0, 0.0, 0.0])
    spread = np.array([2.0, 2.0, 2.0])
    assert float(np.linalg.norm(spread - query)) < float(
        np.linalg.norm(spike - query)
    )
    assert float(np.linalg.norm(spike - query, ord=1)) < float(
        np.linalg.norm(spread - query, ord=1)
    )


# ---------------------------------------------------------------------------
# 9. Normalising changes which article wins
# ---------------------------------------------------------------------------


def test_normalising_changes_the_nearest_article_for_a_short_query():
    query = [1, 0, 0, 0]
    unit_catalogue = {k: pure.normalise(v) for k, v in CATALOGUE.items()}

    raw_winner, _ = pure.nearest(query, CATALOGUE)
    unit_winner, _ = pure.nearest(pure.normalise(query), unit_catalogue)

    assert raw_winner == "slow-cooker-stew"
    assert unit_winner == "roast-chicken"
    assert raw_winner != unit_winner


def test_a_longer_copy_of_the_same_article_is_identical_once_normalised():
    short = CATALOGUE["roast-chicken"]
    long_version = pure.scale(3, short)
    assert pure.distance(short, long_version) > 1.0
    assert close(pure.distance(pure.normalise(short), pure.normalise(long_version)), 0)


def test_articles_with_no_cooking_component_are_perpendicular_to_a_cooking_query():
    """Dot product zero means perpendicular, and it shows up as distance sqrt(2)."""
    query_unit = pure.normalise([1, 0, 0, 0])
    for label in ("marathon-plan", "storm-bulletin"):
        item_unit = pure.normalise(CATALOGUE[label])
        assert close(pure.dot(query_unit, item_unit), 0)
        assert close(pure.distance(query_unit, item_unit), math.sqrt(2))