Hands-on lab — Day 103: Dot Products and Similarity

"""Section 1 — Euclidean distance answers the wrong question about text.

Day 99 measured how far apart two articles were with Euclidean distance, and
that worked well enough that it was easy to miss what it was actually
measuring. Here is the miss, in one number.

Take roast-chicken and write it again at twice the length. Same subject, same
emphasis, every count doubled. Euclidean distance says the doubled copy is
further from the original than an article about race-day nutrition is — which
is mostly about running.

Nothing is wrong with the arithmetic. The question was wrong. "How far apart
are these two points" is not the same question as "are these two articles
about the same thing", and for text they have different answers.

Run from the examples directory:

    python3 01_the_length_confound.py
"""

from __future__ import annotations

from catalogue import CATALOGUE, FEATURES, LONG_ROAST_CHICKEN
from similarity import cosine_similarity, euclidean_distance, l2_norm, normalise

TOL = 1e-12


def show_the_two_articles() -> None:
    short = CATALOGUE["roast-chicken"]
    print("The same article, written twice as long")
    print()
    header = f"  {'article':<26}" + "".join(f"{f:>10}" for f in FEATURES) + f"{'|v|':>10}"
    print(header)
    print("  " + "-" * (len(header) - 2))
    print(f"  {'roast-chicken':<26}" + "".join(f"{n:>10}" for n in short)
          + f"{l2_norm(short):>10.4f}")
    print(f"  {'roast-chicken (2x length)':<26}"
          + "".join(f"{n:>10}" for n in LONG_ROAST_CHICKEN)
          + f"{l2_norm(LONG_ROAST_CHICKEN):>10.4f}")
    print()
    print("  Every count doubled. The writer said the same things, twice each.")
    print()


def show_the_failure() -> None:
    short = CATALOGUE["roast-chicken"]
    rival = CATALOGUE["race-day-nutrition"]

    d_long = euclidean_distance(short, LONG_ROAST_CHICKEN)
    d_rival = euclidean_distance(short, rival)

    print("Euclidean distance, worked out in full")
    print()
    diff_long = [a - b for a, b in zip(short, LONG_ROAST_CHICKEN)]
    print("  roast-chicken vs its own doubled copy")
    print(f"      {short} - {LONG_ROAST_CHICKEN} = {diff_long}")
    print(f"      squares: {' + '.join(str(d * d) for d in diff_long)}"
          f" = {sum(d * d for d in diff_long)}")
    print(f"      sqrt({sum(d * d for d in diff_long)}) = {d_long:.4f}")
    print()
    diff_rival = [a - b for a, b in zip(short, rival)]
    print("  roast-chicken vs race-day-nutrition")
    print(f"      {short} - {rival} = {diff_rival}")
    print(f"      squares: {' + '.join(str(d * d) for d in diff_rival)}"
          f" = {sum(d * d for d in diff_rival)}")
    print(f"      sqrt({sum(d * d for d in diff_rival)}) = {d_rival:.4f}")
    print()
    print("  So Euclidean distance says the doubled copy of roast-chicken")
    print(f"  ({d_long:.4f}) is FURTHER from roast-chicken than an article")
    print(f"  about race-day nutrition is ({d_rival:.4f}).")
    print()
    assert d_long > d_rival, "the confound should put the doubled copy further away"

    print("  There is a tidy reason the first number came out the way it did.")
    print("  Doubling a vector v gives 2v, and the difference is 2v - v = v, so")
    print("  the distance between an article and its doubled copy is exactly the")
    print(f"  article's own length: |v| = {l2_norm(short):.4f}. Longer articles are")
    print("  punished harder, which is the opposite of what a search should do.")
    print()


def show_the_fix() -> None:
    short = CATALOGUE["roast-chicken"]
    rival = CATALOGUE["race-day-nutrition"]

    cos_long = cosine_similarity(short, LONG_ROAST_CHICKEN)
    cos_rival = cosine_similarity(short, rival)

    print("Cosine similarity, on exactly the same numbers")
    print()
    print(f"  cos(roast-chicken, its doubled copy)   = {cos_long:.10f}")
    print(f"  cos(roast-chicken, race-day-nutrition) = {cos_rival:.10f}")
    print()
    print("  1.0 means the angle between them is zero: the two vectors point")
    print("  in exactly the same direction. They are the same article, and the")
    print("  measure says so.")
    print()
    assert abs(cos_long - 1.0) < TOL, "a scaled copy must have cosine similarity 1"
    assert cos_rival < cos_long

    print("  Why it is exactly 1 rather than nearly 1: cosine similarity")
    print("  divides by both lengths, so scaling either vector by a positive")
    print("  number multiplies the top and the bottom by the same factor and")
    print("  cancels. Here is that cancellation with the real numbers:")
    print()
    dot_long = sum(a * b for a, b in zip(short, LONG_ROAST_CHICKEN))
    print(f"      dot = 9*18 + 0*0 + 1*2 + 0*0 = {dot_long}")
    print(f"      |v|  = {l2_norm(short):.6f}")
    print(f"      |2v| = {l2_norm(LONG_ROAST_CHICKEN):.6f}"
          f"  (exactly twice {l2_norm(short):.6f})")
    print(f"      {dot_long} / ({l2_norm(short):.6f} * "
          f"{l2_norm(LONG_ROAST_CHICKEN):.6f}) = {cos_long:.10f}")
    print()

    unit_short = normalise(short)
    unit_long = normalise(LONG_ROAST_CHICKEN)
    print("  The same thing said with unit vectors. Normalise both — divide each")
    print("  by its own length — and they land on the identical point:")
    print()
    print(f"      unit(roast-chicken)   = [{', '.join(f'{x:.6f}' for x in unit_short)}]")
    print(f"      unit(doubled copy)    = [{', '.join(f'{x:.6f}' for x in unit_long)}]")
    print(f"      distance between them = "
          f"{euclidean_distance(unit_short, unit_long):.10f}")
    print()
    assert euclidean_distance(unit_short, unit_long) < TOL


def show_the_whole_catalogue() -> None:
    short = CATALOGUE["roast-chicken"]
    print("Both measures against roast-chicken, whole catalogue, doubled copy included")
    print()
    rows = dict(CATALOGUE)
    rows["roast-chicken (2x)"] = LONG_ROAST_CHICKEN
    header = f"  {'article':<24}{'Euclidean':>12}{'cosine':>12}{'agrees?':>10}"
    print(header)
    print("  " + "-" * (len(header) - 2))

    by_euclid = sorted(rows, key=lambda k: euclidean_distance(short, rows[k]))
    by_cosine = sorted(rows, key=lambda k: -cosine_similarity(short, rows[k]))
    for label, vector in rows.items():
        agrees = by_euclid.index(label) == by_cosine.index(label)
        print(f"  {label:<24}{euclidean_distance(short, vector):>12.4f}"
              f"{cosine_similarity(short, vector):>12.4f}{str(agrees):>10}")
    print()
    print(f"  ranked by Euclidean : {', '.join(by_euclid)}")
    print(f"  ranked by cosine    : {', '.join(by_cosine)}")
    print()
    print("  The two rankings disagree on RAW counts, and they disagree in the")
    print("  place that matters: cosine puts the doubled copy joint first,")
    print("  Euclidean puts it fourth. Section 4 shows that once every vector is")
    print("  normalised the two measures agree completely — the disagreement is")
    print("  entirely about magnitude.")
    print()
    assert by_euclid != by_cosine, "the whole point is that raw rankings differ"
    assert by_cosine[0] in ("roast-chicken", "roast-chicken (2x)")


def main() -> int:
    show_the_two_articles()
    show_the_failure()
    show_the_fix()
    show_the_whole_catalogue()
    print("01_the_length_confound.py: every assertion held.")
    return 0


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

"""Section 2 — what the dot product IS, and what its sign tells you.

Day 101 computed dot products mechanically: multiply component by component,
add up the results. That is correct and it is not an explanation. Today the
same number gets its geometric meaning:

    a dot b = |a| |b| cos(theta)

Read that right to left and it says: the dot product is how much of one vector
lies along the other, scaled by both lengths. Read the sign alone and it says
something simpler and immediately useful — positive means the angle is under
90 degrees, zero means exactly 90, negative means over 90.

Run from the examples directory:

    python3 02_dot_product_and_sign.py
"""

from __future__ import annotations

import math

from catalogue import PROJECTION_A, PROJECTION_B, SIGN_CASES
from similarity import (
    angle_degrees,
    cosine_similarity,
    dot,
    l2_norm,
    scalar_projection,
    vector_projection,
)

TOL = 1e-9


def show_the_two_definitions_agree() -> None:
    a, b = PROJECTION_A, PROJECTION_B
    print("The algebraic definition and the geometric one are the same number")
    print()
    print(f"  a = {a}   |a| = {l2_norm(a):.4f}   (a 3-4-5 triangle, so exactly 5)")
    print(f"  b = {b}   |b| = {l2_norm(b):.4f}")
    print()
    products = [x * y for x, y in zip(a, b)]
    print("  Algebraic: multiply component by component, then add.")
    print(f"      {a[0]}*{b[0]} + {a[1]}*{b[1]} = {products[0]} + {products[1]}"
          f" = {dot(a, b):.0f}")
    print()
    theta = angle_degrees(a, b)
    cos_theta = cosine_similarity(a, b)
    print("  Geometric: |a| |b| cos(theta).")
    print(f"      theta = {theta:.4f} degrees, cos(theta) = {cos_theta:.4f}")
    print(f"      {l2_norm(a):.0f} * {l2_norm(b):.0f} * {cos_theta:.4f}"
          f" = {l2_norm(a) * l2_norm(b) * cos_theta:.4f}")
    print()
    assert abs(dot(a, b) - l2_norm(a) * l2_norm(b) * cos_theta) < TOL
    print("  Same number, reached two ways. The algebraic route is what a")
    print("  computer runs; the geometric route is what it means.")
    print()


def show_the_projection() -> None:
    a, b = PROJECTION_A, PROJECTION_B
    print("The projection picture: how much of b lies along a")
    print()
    shadow_length = scalar_projection(a, b)
    shadow = vector_projection(a, b)
    print("  Shine a light straight down onto a's direction. b casts a shadow.")
    print(f"      length of the shadow = (a dot b) / |a| = {dot(a, b):.0f} /"
          f" {l2_norm(a):.0f} = {shadow_length:.4f}")
    print(f"      the shadow as a vector = [{', '.join(f'{x:.4f}' for x in shadow)}]")
    print(f"      its length             = {l2_norm(shadow):.4f}")
    print()
    assert abs(l2_norm(shadow) - shadow_length) < TOL
    print(f"  Check it the other way: |b| cos(theta) = {l2_norm(b):.0f} *"
          f" {cosine_similarity(a, b):.4f} = {l2_norm(b) * cosine_similarity(a, b):.4f}")
    print()
    assert abs(l2_norm(b) * cosine_similarity(a, b) - shadow_length) < TOL

    other_way = scalar_projection(b, a)
    print("  The projection is NOT symmetric. Projecting a onto b instead:")
    print(f"      (b dot a) / |b| = {dot(b, a):.0f} / {l2_norm(b):.0f}"
          f" = {other_way:.4f}")
    print(f"  The dot product does not care about order — {dot(a, b):.0f} either")
    print("  way — but the shadow does, because you have chosen a different")
    print("  surface to cast it on.")
    print()
    assert abs(dot(a, b) - dot(b, a)) < TOL
    assert abs(other_way - shadow_length) > TOL

    print("  And the special case that ties Day 99 to today: project a onto")
    print("  itself and the shadow is the whole vector.")
    print(f"      (a dot a) / |a| = {dot(a, a):.0f} / {l2_norm(a):.0f}"
          f" = {scalar_projection(a, a):.4f} = |a|")
    print(f"      so |a| = sqrt(a dot a) = sqrt({dot(a, a):.0f}) = {l2_norm(a):.4f}")
    print()
    assert abs(scalar_projection(a, a) - l2_norm(a)) < TOL
    assert abs(math.sqrt(dot(a, a)) - l2_norm(a)) < TOL


def show_the_sign_cases() -> None:
    print("What the sign tells you, one worked example of each")
    print()
    header = (f"  {'case':<20}{'a':>10}{'b':>10}{'a.b':>8}"
              f"{'cos':>10}{'angle':>10}{'sign':>11}")
    print(header)
    print("  " + "-" * (len(header) - 2))
    for label, a, b, expected_sign in SIGN_CASES:
        value = dot(a, b)
        actual_sign = "positive" if value > 0 else ("zero" if value == 0 else "negative")
        assert actual_sign == expected_sign, (label, value, expected_sign)
        print(f"  {label:<20}{str(a):>10}{str(b):>10}{value:>8.0f}"
              f"{cosine_similarity(a, b):>10.4f}{angle_degrees(a, b):>10.2f}"
              f"{actual_sign:>11}")
    print()
    print("  Read the middle two columns together and the rule falls out:")
    print()
    print("    dot > 0  <->  cos > 0  <->  angle under 90 degrees   (agreeing)")
    print("    dot = 0  <->  cos = 0  <->  angle exactly 90 degrees (unrelated)")
    print("    dot < 0  <->  cos < 0  <->  angle over 90 degrees    (opposing)")
    print()
    print("  The sign of the dot product and the sign of the cosine are always")
    print("  the same, because the two lengths you divide by are never negative.")
    print("  So if all you need is the DIRECTION of the relationship, the raw")
    print("  dot product answers it and you can skip both square roots.")
    print()


def show_orthogonality_in_the_catalogue() -> None:
    from catalogue import CATALOGUE

    print("Orthogonality is not an abstraction: three pairs in the catalogue have it")
    print()
    labels = list(CATALOGUE)
    found = []
    for i, first in enumerate(labels):
        for second in labels[i + 1:]:
            value = dot(CATALOGUE[first], CATALOGUE[second])
            if value == 0:
                found.append((first, second))
    for first, second in found:
        print(f"  {first} . {second} = 0")
        pairs = " + ".join(
            f"{x}*{y}" for x, y in zip(CATALOGUE[first], CATALOGUE[second])
        )
        print(f"      {pairs} = 0")
        print(f"      cosine similarity {cosine_similarity(CATALOGUE[first], CATALOGUE[second]):.4f},"
              f" angle {angle_degrees(CATALOGUE[first], CATALOGUE[second]):.2f} degrees")
    print()
    assert ("roast-chicken", "storm-bulletin") in found
    print("  Every product in that sum is zero because wherever one article has")
    print("  a count the other has none. They share no vocabulary at all, and")
    print("  orthogonal is exactly what that means: not opposed, just entirely")
    print("  unrelated. Nothing you learn about one tells you anything about")
    print("  the other.")
    print()


def main() -> int:
    show_the_two_definitions_agree()
    show_the_projection()
    show_the_sign_cases()
    show_orthogonality_in_the_catalogue()
    print("02_dot_product_and_sign.py: every assertion held.")
    return 0


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

"""Section 3 — fifteen lines of pure Python, checked against NumPy line by line.

Everything today's lesson claims comes out of three functions, and all three
fit on one screen:

    dot(a, b)               = sum(x*y for x, y in zip(a, b))
    cosine_similarity(a, b) = dot(a, b) / (l2_norm(a) * l2_norm(b))
    cosine_distance(a, b)   = 1 - cosine_similarity(a, b)

This script runs each of them against NumPy's own machinery on every pair in
the catalogue and asserts agreement to a stated tolerance, so that "my version
matches the library" is a measurement rather than a hope. It then shows the
three places where the from-scratch version and the library version genuinely
differ — which is worth more than the agreement, because those are the places
where a real implementation goes wrong.

Run from the examples directory:

    python3 03_from_scratch_vs_numpy.py
"""

from __future__ import annotations

import math

import numpy as np

from catalogue import CATALOGUE
from similarity import (
    angle_degrees,
    cosine_distance,
    cosine_similarity,
    dot,
    l2_norm,
    normalise,
)

TOL = 1e-12


def numpy_cosine(a, b) -> float:
    """The same formula in NumPy, written out rather than imported."""
    a = np.asarray(a, dtype=float)
    b = np.asarray(b, dtype=float)
    return float(a @ b / (np.linalg.norm(a) * np.linalg.norm(b)))


def show_every_pair_agrees() -> None:
    print("Every pair in the catalogue, mine against NumPy's")
    print()
    labels = list(CATALOGUE)
    header = (f"  {'pair':<40}{'dot':>8}{'mine':>12}{'numpy':>12}"
              f"{'difference':>14}")
    print(header)
    print("  " + "-" * (len(header) - 2))
    worst = 0.0
    pairs = 0
    for i, first in enumerate(labels):
        for second in labels[i + 1:]:
            a, b = CATALOGUE[first], CATALOGUE[second]
            mine = cosine_similarity(a, b)
            theirs = numpy_cosine(a, b)
            gap = abs(mine - theirs)
            worst = max(worst, gap)
            pairs += 1
            print(f"  {first + ' / ' + second:<40}{dot(a, b):>8.0f}"
                  f"{mine:>12.6f}{theirs:>12.6f}{gap:>14.2e}")
            assert gap < TOL, (first, second, mine, theirs)
    print()
    print(f"  {pairs} pairs, largest disagreement {worst:.2e}, tolerance {TOL:.0e}")
    print()
    print("  Note that this is agreement, not identity. The two implementations")
    print("  add the products up in the same order here, so they happen to")
    print("  produce bit-identical answers, but nothing guarantees that in")
    print("  general — NumPy is free to reorder a summation for speed, and")
    print("  floating-point addition is not associative (Day 70). Compare with")
    print("  a tolerance, always.")
    print()


def show_the_three_equivalent_routes() -> None:
    a = CATALOGUE["roast-chicken"]
    b = CATALOGUE["race-day-nutrition"]
    print("Three routes to the same cosine similarity")
    print()
    direct = dot(a, b) / (l2_norm(a) * l2_norm(b))
    via_units = dot(normalise(a), normalise(b))
    via_numpy = float(np.dot(normalise(a), normalise(b)))
    print(f"  divide the dot product by both lengths : {direct:.15f}")
    print(f"  dot product of the two UNIT vectors    : {via_units:.15f}")
    print(f"  the same, through numpy.dot            : {via_numpy:.15f}")
    print()
    assert abs(direct - via_units) < TOL
    assert abs(via_units - via_numpy) < TOL
    print("  The second route is the one that matters in practice. Normalise")
    print("  every vector ONCE when you store it, and every later comparison is")
    print("  a bare dot product with no square roots in it at all. That is what")
    print("  a vector index does, and it is why 'dot product' and 'cosine' are")
    print("  offered as separate options by systems that store embeddings: on")
    print("  already-normalised vectors they are the same thing, and the dot")
    print("  product is cheaper.")
    print()


def show_the_edges() -> None:
    print("Three places where the naive formula needs care")
    print()

    print("  1. The zero vector. It has no direction, so the angle to it does")
    print("     not exist, and the formula divides by zero.")
    zero = [0, 0, 0, 0]
    with np.errstate(invalid="ignore", divide="ignore"):
        naive = np.dot(zero, CATALOGUE["roast-chicken"]) / (
            np.linalg.norm(zero) * np.linalg.norm(CATALOGUE["roast-chicken"])
        )
    print(f"     written out in NumPy without a guard : {naive}")
    try:
        cosine_similarity(zero, CATALOGUE["roast-chicken"])
    except ValueError as exc:
        print(f"     this lab's version                   : ValueError: {exc}")
    else:  # pragma: no cover - the guard is asserted below
        raise AssertionError("cosine_similarity must refuse the zero vector")
    print("     A NaN sorts unpredictably and spreads through every average it")
    print("     touches. Raise instead. An empty document is a real thing that")
    print("     happens, and it should stop the pipeline, not poison it.")
    print()

    print("  2. Rounding past 1. Compare a vector with ITSELF and the answer")
    print("     should be exactly 1.0. Here is what it actually is, unclamped,")
    print("     for all six articles — plain integer counts, nothing exotic:")
    print()
    print(f"     {'article':<22}{'unclamped (a dot a) / (|a| |a|)':>36}")
    print("     " + "-" * 57)
    over = []
    under = []
    for label, vector in CATALOGUE.items():
        length = math.sqrt(sum(x * x for x in vector))
        unclamped = sum(x * y for x, y in zip(vector, vector)) / (length * length)
        print(f"     {label:<22}{unclamped!r:>36}")
        if unclamped > 1.0:
            over.append((label, unclamped))
        elif unclamped < 1.0:
            under.append((label, unclamped))
    print()
    print(f"     exactly 1.0 : {6 - len(over) - len(under)} of 6")
    print(f"     just under  : {len(under)} of 6")
    print(f"     just over   : {len(over)} of 6")
    print()
    assert over, "at least one article should round above 1.0"
    label, unclamped = over[0]
    print(f"     The one that rounds UP is {label}, at {unclamped!r},")
    print("     and that single bit of rounding is fatal downstream:")
    try:
        math.acos(unclamped)
    except ValueError as exc:
        print(f"       math.acos({unclamped!r}) -> ValueError: {exc}")
    else:  # pragma: no cover - the domain error is the point
        raise AssertionError("acos above 1.0 should raise")
    vector = CATALOGUE[label]
    print(f"       clamped, this lab gives {cosine_similarity(vector, vector)!r}")
    print(f"       and an angle of {angle_degrees(vector, vector):.1f} degrees")
    print()
    print("     Half a dozen four-component integer vectors were enough to")
    print("     produce this, which is the point: it is not an exotic case you")
    print("     will meet once. Any code that turns a similarity into an angle,")
    print("     or asserts a score is at most 1.0, clamps first. This lab")
    print("     clamps, and every reported similarity below is a clamped one.")
    assert unclamped > 1.0
    assert cosine_similarity(vector, vector) == 1.0
    print()

    print("  3. Mismatched lengths. Two vectors of different sizes cannot be")
    print("     compared, and the failure should be loud.")
    try:
        dot([1, 2, 3], [1, 2])
    except ValueError as exc:
        print(f"     this lab's version : ValueError: {exc}")
    else:  # pragma: no cover
        raise AssertionError("dot must refuse mismatched lengths")
    try:
        np.array([1, 2, 3]) @ np.array([1, 2])
    except ValueError as exc:
        print(f"     NumPy              : ValueError: {exc}")
    else:  # pragma: no cover
        raise AssertionError("numpy must refuse mismatched lengths")
    print("     Both raise ValueError, which is deliberate: one except clause")
    print("     catches either implementation.")
    print()


def show_cosine_distance() -> None:
    print("Cosine distance is just 1 minus the similarity")
    print()
    header = f"  {'pair':<40}{'similarity':>12}{'distance':>12}"
    print(header)
    print("  " + "-" * (len(header) - 2))
    examples = [
        ("roast-chicken", "roast-chicken"),
        ("roast-chicken", "slow-cooker-stew"),
        ("roast-chicken", "race-day-nutrition"),
        ("roast-chicken", "storm-bulletin"),
    ]
    for first, second in examples:
        a, b = CATALOGUE[first], CATALOGUE[second]
        print(f"  {first + ' / ' + second:<40}{cosine_similarity(a, b):>12.6f}"
              f"{cosine_distance(a, b):>12.6f}")
    opposed = cosine_distance([1, 0], [-1, 0])
    print(f"  {'[1, 0] / [-1, 0] (opposite directions)':<40}"
          f"{cosine_similarity([1, 0], [-1, 0]):>12.6f}{opposed:>12.6f}")
    print()
    print("  The range is 0 to 2, not 0 to 1 — because similarity runs from 1")
    print("  down to -1. On count vectors, where nothing is ever negative, no")
    print("  pair can be more than 90 degrees apart, so the distance never")
    print("  exceeds 1 and 'orthogonal' is as far apart as two articles get.")
    print("  Embeddings from a trained model DO have negative components, and")
    print("  there the upper half of the range is reachable.")
    print()
    assert abs(opposed - 2.0) < TOL
    assert all(
        cosine_distance(CATALOGUE[a], CATALOGUE[b]) <= 1.0 + TOL
        for a in CATALOGUE
        for b in CATALOGUE
    )


def main() -> int:
    show_every_pair_agrees()
    show_the_three_equivalent_routes()
    show_the_edges()
    show_cosine_distance()
    print("03_from_scratch_vs_numpy.py: every assertion held.")
    return 0


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

"""Section 4 — on normalised vectors the two measures rank identically.

This is the most useful fact in the day, and it is the one most often stated
without proof. Here it is proved twice: once with algebra you can follow with a
pen, and once by ranking the whole catalogue both ways and asserting the orders
match.

The algebra, for two UNIT vectors u and v:

    |u - v|^2 = (u - v) dot (u - v)
              = u dot u  -  2 (u dot v)  +  v dot v
              = 1 - 2 (u dot v) + 1
              = 2 - 2 cos(theta)

so                                    Euclidean distance = sqrt(2 - 2 cos)

Cosine goes up, the bracket goes down, the square root goes down. The distance
is a strictly decreasing function of the similarity, so sorting by one gives
exactly the reverse of sorting by the other. Not approximately. Exactly.

That is why a vector database normalises its vectors on the way in and then
uses whichever comparison its hardware runs fastest: on the unit sphere the
choice is a performance decision, not a semantic one.

Run from the examples directory:

    python3 04_same_ranking_on_the_sphere.py
"""

from __future__ import annotations

import math

from catalogue import CATALOGUE, LONG_ROAST_CHICKEN
from similarity import (
    cosine_similarity,
    euclidean_distance,
    normalise,
    normalise_all,
    rank_by_cosine,
    rank_by_euclidean,
)

TOL = 1e-12


def show_the_identity() -> None:
    print("The identity, checked on every pair in the catalogue")
    print()
    units = normalise_all(CATALOGUE)
    labels = list(units)
    header = (f"  {'pair':<40}{'cos':>10}{'sqrt(2-2cos)':>14}"
              f"{'|u - v|':>12}{'gap':>12}")
    print(header)
    print("  " + "-" * (len(header) - 2))
    worst = 0.0
    for i, first in enumerate(labels):
        for second in labels[i + 1:]:
            u, v = units[first], units[second]
            cos = cosine_similarity(u, v)
            predicted = math.sqrt(2 - 2 * cos)
            measured = euclidean_distance(u, v)
            gap = abs(predicted - measured)
            worst = max(worst, gap)
            print(f"  {first + ' / ' + second:<40}{cos:>10.6f}{predicted:>14.6f}"
                  f"{measured:>12.6f}{gap:>12.2e}")
            assert gap < TOL
    print()
    print(f"  Largest gap between the formula and the measurement: {worst:.2e}")
    print()


def show_the_rankings_match() -> None:
    print("Rank the catalogue both ways, from the same query, after normalising")
    print()
    query = CATALOGUE["roast-chicken"]
    unit_query = normalise(query)
    units = normalise_all(CATALOGUE)

    by_cosine = rank_by_cosine(unit_query, units)
    by_euclid = rank_by_euclidean(unit_query, units)

    header = (f"  {'rank':<6}{'by cosine (high first)':<26}{'sim':>10}   "
              f"{'by distance (low first)':<26}{'dist':>10}")
    print(header)
    print("  " + "-" * (len(header) - 2))
    for position, (left, right) in enumerate(zip(by_cosine, by_euclid), start=1):
        print(f"  {position:<6}{left[0]:<26}{left[1]:>10.6f}   "
              f"{right[0]:<26}{right[1]:>10.6f}")
    print()
    cosine_order = [label for label, _ in by_cosine]
    euclid_order = [label for label, _ in by_euclid]
    print(f"  the two orders are identical : {cosine_order == euclid_order}")
    print()
    assert cosine_order == euclid_order

    print("  Now the same comparison WITHOUT normalising, to show what the")
    print("  normalisation was doing. The doubled copy of roast-chicken is")
    print("  added so the length difference is real:")
    print()
    raw = dict(CATALOGUE)
    raw["roast-chicken (2x)"] = LONG_ROAST_CHICKEN
    raw_cosine = [label for label, _ in rank_by_cosine(query, raw)]
    raw_euclid = [label for label, _ in rank_by_euclidean(query, raw)]
    print(f"    by cosine   : {', '.join(raw_cosine)}")
    print(f"    by distance : {', '.join(raw_euclid)}")
    print(f"    identical?  : {raw_cosine == raw_euclid}")
    print()
    assert raw_cosine != raw_euclid
    print("  So the claim is precise and worth stating precisely: the two")
    print("  measures agree on NORMALISED vectors and can disagree on raw ones.")
    print("  Normalising is not a tidying step you do out of habit. It is the")
    print("  step that makes the two measures interchangeable, and if you skip")
    print("  it, which one you picked changes the answers.")
    print()


def show_the_monotone_curve() -> None:
    print("The curve behind the claim, sampled")
    print()
    print(f"  {'cosine':>10}{'distance on the unit sphere':>30}{'angle':>10}")
    print("  " + "-" * 48)
    previous = None
    for cos in (1.0, 0.9, 0.5, 0.0, -0.5, -0.9, -1.0):
        distance = math.sqrt(2 - 2 * cos)
        angle = math.degrees(math.acos(cos))
        print(f"  {cos:>10.1f}{distance:>30.6f}{angle:>10.1f}")
        if previous is not None:
            assert distance > previous, "distance must rise as cosine falls"
        previous = distance
    print()
    print("  Every step down in cosine is a step up in distance, with no")
    print("  exceptions and no flat stretches. Two unit vectors pointing the")
    print("  same way are 0 apart; perpendicular ones are sqrt(2) = 1.414214")
    print("  apart; opposite ones are 2 apart, which is the diameter of the")
    print("  sphere and the furthest two unit vectors can get.")
    print()
    print("  What this does NOT say: the two measures produce the same SCORES.")
    print("  They do not, and a threshold tuned for one is meaningless for the")
    print("  other. A cut-off of 'similarity above 0.9' is 'distance below")
    print(f"  {math.sqrt(2 - 2 * 0.9):.6f}', and nothing about the second number is")
    print("  guessable from the first. Only the ORDER is preserved.")
    print()


def main() -> int:
    show_the_identity()
    show_the_rankings_match()
    show_the_monotone_curve()
    print("04_same_ranking_on_the_sphere.py: every assertion held.")
    return 0


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

"""Section 5 — cosine distance is not a metric, and here is the counter-example.

"Distance" is a word with a technical meaning. A function d is a metric when it
satisfies four conditions:

    1. d(a, b) >= 0                        never negative
    2. d(a, b) = 0 exactly when a = b      identity of indiscernibles
    3. d(a, b) = d(b, a)                   symmetry
    4. d(a, c) <= d(a, b) + d(b, c)        the triangle inequality

Cosine distance satisfies 1, 3 and half of 2, and fails 4. It also fails the
other half of 2, because any two vectors pointing the same way — an article and
its doubled copy — are at distance 0 without being equal, which is exactly the
property that made it useful an hour ago.

The failure of 4 is the one that costs you something. A great deal of fast
search machinery — ball trees, KD-trees, metric indexes, anything that prunes
"this whole branch is too far away to contain the answer" — is built on the
triangle inequality. Feed it a function that fails the inequality and it will
still return answers, and some of them will be wrong, and nothing will say so.

This is not a reason to avoid cosine similarity. It is a reason to normalise
your vectors and hand the index Euclidean distance, which IS a metric, knowing
from section 4 that the ranking is identical.

Run from the examples directory:

    python3 05_not_a_metric.py
"""

from __future__ import annotations

import math

from catalogue import TRIANGLE_A, TRIANGLE_B, TRIANGLE_C
from similarity import (
    angle_degrees,
    cosine_distance,
    cosine_similarity,
    euclidean_distance,
    normalise,
)

TOL = 1e-12


def show_the_counter_example() -> None:
    a, b, c = TRIANGLE_A, TRIANGLE_B, TRIANGLE_C
    print("Three vectors, chosen so every number is exact on paper")
    print()
    print(f"  a = {a}   pointing straight along the first axis")
    print(f"  b = {b}   the bisector, 45 degrees from each")
    print(f"  c = {c}   pointing straight along the second axis")
    print()

    ab = cosine_distance(a, b)
    bc = cosine_distance(b, c)
    ac = cosine_distance(a, c)

    print("Their cosine distances")
    print()
    for label, first, second, value in (
        ("d(a, b)", a, b, ab),
        ("d(b, c)", b, c, bc),
        ("d(a, c)", a, c, ac),
    ):
        print(f"  {label} = 1 - cos = 1 - {cosine_similarity(first, second):.6f}"
              f" = {value:.6f}"
              f"   (angle {angle_degrees(first, second):.1f} degrees)")
    print()
    print(f"  a to b is 1 - 1/sqrt(2) = 1 - {1 / math.sqrt(2):.6f}"
          f" = {1 - 1 / math.sqrt(2):.6f}, and so is b to c.")
    print()

    print("The triangle inequality, tested")
    print()
    print(f"  going the long way round : d(a, b) + d(b, c) = {ab:.6f}"
          f" + {bc:.6f} = {ab + bc:.6f}")
    print(f"  going direct             : d(a, c)            = {ac:.6f}")
    print(f"  is direct <= long way?   : {ac <= ab + bc + TOL}")
    print()
    print(f"  The direct route is longer than the detour, by {ac - (ab + bc):.6f}.")
    print("  That is not a rounding artefact and it is not a bug in the code.")
    print("  It is what 'not a metric' means, in one line of arithmetic.")
    print()
    assert ac > ab + bc + TOL, "cosine distance must fail the triangle inequality here"


def show_euclidean_holds() -> None:
    a, b, c = TRIANGLE_A, TRIANGLE_B, TRIANGLE_C
    print("The same three points under Euclidean distance, which IS a metric")
    print()
    ua, ub, uc = normalise(a), normalise(b), normalise(c)
    print("  On the raw vectors:")
    print(f"    d(a, b) + d(b, c) = {euclidean_distance(a, b):.6f} +"
          f" {euclidean_distance(b, c):.6f} = "
          f"{euclidean_distance(a, b) + euclidean_distance(b, c):.6f}")
    print(f"    d(a, c)           = {euclidean_distance(a, c):.6f}")
    print(f"    holds?            = "
          f"{euclidean_distance(a, c) <= euclidean_distance(a, b) + euclidean_distance(b, c) + TOL}")
    print()
    print("  And on the normalised ones, which is the case that matters,")
    print("  because section 4 said to normalise and then use Euclidean:")
    print(f"    d(a, b) + d(b, c) = {euclidean_distance(ua, ub):.6f} +"
          f" {euclidean_distance(ub, uc):.6f} = "
          f"{euclidean_distance(ua, ub) + euclidean_distance(ub, uc):.6f}")
    print(f"    d(a, c)           = {euclidean_distance(ua, uc):.6f}")
    print(f"    holds?            = "
          f"{euclidean_distance(ua, uc) <= euclidean_distance(ua, ub) + euclidean_distance(ub, uc) + TOL}")
    print()
    assert euclidean_distance(a, c) <= euclidean_distance(a, b) + euclidean_distance(b, c) + TOL
    assert euclidean_distance(ua, uc) <= euclidean_distance(ua, ub) + euclidean_distance(ub, uc) + TOL


def show_the_angle_holds() -> None:
    a, b, c = TRIANGLE_A, TRIANGLE_B, TRIANGLE_C
    print("The angle itself, on the same triple")
    print()
    ab = angle_degrees(a, b)
    bc = angle_degrees(b, c)
    ac = angle_degrees(a, c)
    print(f"  angle(a, b) + angle(b, c) = {ab:.1f} + {bc:.1f} = {ab + bc:.1f} degrees")
    print(f"  angle(a, c)               = {ac:.1f} degrees")
    print(f"  holds, with equality?     = {abs((ab + bc) - ac) < 1e-9}")
    print()
    print("  It holds here, and it holds with equality, because b sits exactly")
    print("  on the shortest path from a to c — the three vectors are in one")
    print("  plane and b is the halfway point. That is the degenerate case of a")
    print("  triangle, a straight line, where the inequality becomes equality.")
    print()
    print("  Being careful about what this does and does not show: one triple")
    print("  where a rule holds is not a proof that it always holds. The angle")
    print("  between two vectors is arc length on the unit sphere, and great-")
    print("  circle distance on a sphere is known to be a metric — but that")
    print("  proof is not in this lab, and this run does not supply it. What")
    print("  this run does supply is the counter-example above, and one")
    print("  counter-example IS a proof, of the negative: cosine distance is")
    print("  not a metric, demonstrated, not asserted.")
    print()
    assert abs((ab + bc) - ac) < 1e-9


def show_the_identity_failure() -> None:
    print("The other condition it fails, and why you wanted it to")
    print()
    short = [9, 0, 1, 0]
    doubled = [18, 0, 2, 0]
    distance = cosine_distance(short, doubled)
    print(f"  d({short}, {doubled}) = {distance:.6f}")
    print(f"  are the two vectors equal? {short == doubled}")
    print()
    print("  A metric must have d(a, b) = 0 only when a and b are the same")
    print("  point. Cosine distance gives 0 for every pair on the same ray from")
    print("  the origin. That is a failure of the definition and the entire")
    print("  reason the measure is useful for text: 'same direction' and 'same")
    print("  vector' are different claims, and for documents you want the first")
    print("  one. The measure is not broken. It is answering the question you")
    print("  asked, and that question was never 'are these the same point'.")
    print()
    assert abs(distance) < TOL
    assert short != doubled


def main() -> int:
    show_the_counter_example()
    show_euclidean_holds()
    show_the_angle_holds()
    show_the_identity_failure()
    print("05_not_a_metric.py: every assertion held.")
    return 0


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

"""Section 6 — a semantic search, complete, in about fifteen lines.

Everything in this file that does actual work is imported from
`similarity.py`, and the search itself is four lines:

    def search(query, catalogue, k=3):
        scored = [(label, cosine_similarity(query, v)) for label, v in catalogue.items()]
        scored.sort(key=lambda pair: (-pair[1], pair[0]))
        return scored[:k]

That is the retrieval step of a document-answering system. Everything a real
one adds is about getting better vectors — a trained model instead of hand
counts — and about searching millions of them quickly instead of six of them
exhaustively. The comparison at the centre does not change.

Run from the examples directory:

    python3 06_semantic_search.py
"""

from __future__ import annotations

from catalogue import CATALOGUE, FEATURES, QUERIES
from similarity import (
    angle_degrees,
    cosine_similarity,
    dot,
    euclidean_distance,
    l2_norm,
    normalise_all,
    rank_by_cosine,
    rank_by_euclidean,
)

TOL = 1e-12


def search(query, catalogue, k=3):
    """The whole retrieval step. Score everything, sort, take the top k."""
    scored = [
        (label, cosine_similarity(query, vector)) for label, vector in catalogue.items()
    ]
    scored.sort(key=lambda pair: (-pair[1], pair[0]))
    return scored[:k]


def show_the_index() -> None:
    print("The index: six articles, four features, and their unit vectors")
    print()
    units = normalise_all(CATALOGUE)
    header = (f"  {'article':<20}" + "".join(f"{f:>9}" for f in FEATURES)
              + f"{'|v|':>9}   unit vector")
    print(header)
    print("  " + "-" * (len(header) - 2))
    for label, vector in CATALOGUE.items():
        unit = "[" + ", ".join(f"{x:.3f}" for x in units[label]) + "]"
        print(f"  {label:<20}" + "".join(f"{n:>9}" for n in vector)
              + f"{l2_norm(vector):>9.4f}   {unit}")
    print()
    print("  Normalising once, on the way in, is what a vector store does. After")
    print("  this every query is a dot product and there is not a square root")
    print("  left in the hot path.")
    print()
    for label, unit in units.items():
        assert abs(l2_norm(unit) - 1.0) < 1e-12, label


def run_one_query(text: str, query, expected_top: str) -> None:
    print(f"Query: \"{text}\"  ->  {query}")
    print()
    header = (f"  {'rank':<6}{'article':<22}{'a.b':>7}{'cosine':>10}"
              f"{'angle':>9}{'euclid (raw)':>15}")
    print(header)
    print("  " + "-" * (len(header) - 2))
    ranked = rank_by_cosine(query, CATALOGUE)
    for position, (label, score) in enumerate(ranked, start=1):
        vector = CATALOGUE[label]
        print(f"  {position:<6}{label:<22}{dot(query, vector):>7.0f}{score:>10.6f}"
              f"{angle_degrees(query, vector):>9.2f}"
              f"{euclidean_distance(query, vector):>15.4f}")
    print()
    top, top_score = ranked[0]
    runner, runner_score = ranked[1]
    print(f"  top result : {top} at {top_score:.6f}")
    print(f"  runner-up  : {runner} at {runner_score:.6f}")
    print(f"  margin     : {top_score - runner_score:.6f}")
    print()
    assert top == expected_top, (text, top, expected_top)

    raw_euclid = rank_by_euclidean(query, CATALOGUE)
    print("  For contrast, the same query ranked by RAW Euclidean distance:")
    print(f"    {', '.join(label for label, _ in raw_euclid)}")
    print(f"    nearest by distance: {raw_euclid[0][0]} at {raw_euclid[0][1]:.4f}")
    if raw_euclid[0][0] != top:
        print("    which is NOT the cosine winner. Raw distance is still being")
        print("    dominated by how long each article is.")
    else:
        print("    which agrees with cosine here — agreement is possible, it is")
        print("    just not guaranteed while the vectors have different lengths.")
    print()

    by_dot = sorted(
        CATALOGUE, key=lambda label: (-dot(query, CATALOGUE[label]), label)
    )
    print("  And by the RAW dot product, with no division at all:")
    print(f"    {', '.join(by_dot)}")
    print(f"    highest dot product: {by_dot[0]} at {dot(query, CATALOGUE[by_dot[0]]):.0f}")
    if by_dot[0] != top:
        print("    also NOT the cosine winner. The dot product rewards long")
        print("    articles, because a longer vector has more of everything to")
        print("    multiply. Dot product and cosine are the same ranking only")
        print("    after the vectors are normalised.")
    else:
        print("    which agrees with cosine here, but only by luck of these")
        print("    particular lengths.")
    print()


def show_top_three() -> None:
    print("The four-line search, used the way it would be used")
    print()
    for text, query in QUERIES.items():
        hits = search(query, CATALOGUE, k=3)
        print(f"  \"{text}\"")
        for position, (label, score) in enumerate(hits, start=1):
            print(f"      {position}. {label:<22}{score:.4f}")
        print()


def show_magnitude_does_not_matter() -> None:
    print("The query's own length is irrelevant, which is worth proving")
    print()
    base = QUERIES["roast it"]
    header = f"  {'query':<22}{'roast-chicken':>16}{'slow-cooker-stew':>20}"
    print(header)
    print("  " + "-" * (len(header) - 2))
    first = None
    for factor in (1, 3, 100):
        scaled = [factor * x for x in base]
        chicken = cosine_similarity(scaled, CATALOGUE["roast-chicken"])
        stew = cosine_similarity(scaled, CATALOGUE["slow-cooker-stew"])
        print(f"  {str(scaled):<22}{chicken:>16.10f}{stew:>20.10f}")
        if first is None:
            first = (chicken, stew)
        else:
            assert abs(chicken - first[0]) < TOL
            assert abs(stew - first[1]) < TOL
    print()
    print("  Identical to ten decimal places. A one-word query and the same")
    print("  word repeated a hundred times rank the catalogue exactly the same,")
    print("  because the only thing cosine reads is the direction. Under raw")
    print("  Euclidean distance those three queries give three different")
    print("  answers, and Day 99 showed the shortest of them picking the wrong")
    print("  article.")
    print()


def main() -> int:
    show_the_index()
    run_one_query("roast it", QUERIES["roast it"], "roast-chicken")
    run_one_query(
        "training for a race and what to eat",
        QUERIES["training for a race and what to eat"],
        "race-day-nutrition",
    )
    show_top_three()
    show_magnitude_does_not_matter()
    print("06_semantic_search.py: every assertion held.")
    return 0


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

"""Section 7 — as the dimension grows, random vectors become nearly orthogonal.

Real embeddings do not have four components. They have hundreds or thousands.
Something happens in that space which has no analogue in two or three
dimensions, and which is worth measuring rather than being told:

  * two random directions become almost perpendicular, so almost every pair of
    unrelated things scores near 0;
  * the distances between random points bunch up, so the nearest and the
    furthest point in a random cloud stop being very different.

Both are measured here with a seeded generator, so the numbers below are
reproducible: numpy.random.default_rng(103) on numpy 2.5.2. Re-run it and you
get the same values. Change the seed and the numbers move a little; the shape
of the result does not.

The vectors are drawn from a standard normal distribution, which is the usual
choice because it gives a direction that is uniform over the sphere. Drawing
each component uniformly from a box would bias the directions towards the
corners.

Run from the examples directory:

    python3 07_curse_of_dimensionality.py
"""

from __future__ import annotations

import math

import numpy as np

SEED = 103
PAIRS = 2000
DIMENSIONS = (2, 3, 8, 32, 128, 512, 2048, 8192)


def exact_mean_abs_cos(dimension: int) -> float:
    """The exact mean of |cos| for two independent random directions in d dims.

        E|cos| = gamma(d/2) / (sqrt(pi) * gamma((d+1)/2))

    Two values are checkable by hand and both come out of this expression:
    in 2 dimensions the angle is uniform over the circle so the answer is
    2/pi = 0.63662, and in 3 dimensions the cosine itself is uniform over
    -1 to 1 so the answer is exactly 0.5.
    """
    return math.exp(
        math.lgamma(dimension / 2)
        - 0.5 * math.log(math.pi)
        - math.lgamma((dimension + 1) / 2)
    )


def cosine_rows(a: np.ndarray, b: np.ndarray) -> np.ndarray:
    """Cosine similarity of matching rows of two arrays, vectorised."""
    numerator = np.einsum("ij,ij->i", a, b)
    denominator = np.linalg.norm(a, axis=1) * np.linalg.norm(b, axis=1)
    return np.clip(numerator / denominator, -1.0, 1.0)


def measure() -> list[dict[str, float]]:
    rng = np.random.default_rng(SEED)
    rows = []
    for dimension in DIMENSIONS:
        a = rng.standard_normal((PAIRS, dimension))
        b = rng.standard_normal((PAIRS, dimension))
        cosines = cosine_rows(a, b)
        angles = np.degrees(np.arccos(cosines))
        rows.append(
            {
                "dimension": dimension,
                "mean_abs_cos": float(np.mean(np.abs(cosines))),
                "max_abs_cos": float(np.max(np.abs(cosines))),
                "mean_angle": float(np.mean(angles)),
                "std_angle": float(np.std(angles)),
                "exact": exact_mean_abs_cos(dimension),
                "asymptotic": math.sqrt(2.0 / (math.pi * dimension)),
                "frac_within_10_deg": float(np.mean(np.abs(angles - 90.0) < 10.0)),
            }
        )
    return rows


def show_orthogonality(rows) -> None:
    print(f"Mean |cosine| between {PAIRS} random vector pairs, by dimension")
    print(f"(numpy.random.default_rng({SEED}), standard normal components)")
    print()
    header = (f"  {'dimension':>10}{'mean |cos|':>13}{'exact':>10}"
              f"{'sqrt(2/(pi d))':>16}{'max |cos|':>12}{'mean angle':>13}"
              f"{'sd of angle':>13}{'within 10 deg':>15}")
    print(header)
    print("  " + "-" * (len(header) - 2))
    for row in rows:
        print(f"  {row['dimension']:>10}{row['mean_abs_cos']:>13.4f}"
              f"{row['exact']:>10.4f}{row['asymptotic']:>16.4f}"
              f"{row['max_abs_cos']:>12.4f}"
              f"{row['mean_angle']:>13.2f}{row['std_angle']:>13.2f}"
              f"{row['frac_within_10_deg'] * 100:>14.1f}%")
    print()

    first, last = rows[0], rows[-1]
    print(f"  From dimension {first['dimension']} to dimension {last['dimension']},"
          f" the mean absolute cosine")
    print(f"  fell from {first['mean_abs_cos']:.4f} to {last['mean_abs_cos']:.4f}"
          f" — a factor of {first['mean_abs_cos'] / last['mean_abs_cos']:.0f}.")
    print(f"  The fraction of pairs within 10 degrees of a right angle rose from")
    print(f"  {first['frac_within_10_deg'] * 100:.1f}% to"
          f" {last['frac_within_10_deg'] * 100:.1f}%.")
    print()

    for earlier, later in zip(rows, rows[1:]):
        assert later["mean_abs_cos"] < earlier["mean_abs_cos"], (earlier, later)
    assert rows[-1]["mean_abs_cos"] < 0.02

    worst_exact = max(
        abs(row["mean_abs_cos"] - row["exact"]) / row["exact"] for row in rows
    )
    worst_asymptotic = max(
        abs(row["exact"] - row["asymptotic"]) / row["exact"] for row in rows
    )
    print("  Two predictions sit beside the measurement, and the difference")
    print("  between them is worth a paragraph. The 'exact' column is")
    print("  gamma(d/2) / (sqrt(pi) gamma((d+1)/2)), the true mean of |cos| for")
    print("  two independent random directions. The last column is the")
    print("  approximation sqrt(2 / (pi d)), which is the one usually quoted.")
    print()
    print(f"  The measurement matches the exact value to within"
          f" {worst_exact * 100:.1f}% at every")
    print(f"  dimension, on {PAIRS} pairs. The approximation is off by up to"
          f" {worst_asymptotic * 100:.0f}%")
    print("  at the small dimensions — it is a large-d limit, and at d = 2 and")
    print("  d = 3 it simply is not the right number. Two hand-checkable cases")
    print("  settle which column to trust: in 2 dimensions the angle is uniform")
    print("  around the circle so the mean of |cos| is 2/pi = 0.63662, and in 3")
    print("  dimensions the cosine itself is uniform from -1 to 1 so the mean is")
    print("  exactly 0.5. The exact column gives both; the approximation gives")
    print("  neither; the measurement agrees with the exact column. This is a")
    print("  small thing, and it is the habit that matters: when a run and a")
    print("  quoted formula disagree, find out which one is answering your")
    print("  question before assuming the run is wrong.")
    print()
    for row in rows:
        assert abs(row["mean_abs_cos"] - row["exact"]) / row["exact"] < 0.05
    assert abs(exact_mean_abs_cos(2) - 2 / math.pi) < 1e-12
    assert abs(exact_mean_abs_cos(3) - 0.5) < 1e-12
    print("  None of that changes the headline, which is the first column")
    print("  falling towards zero as the dimension grows.")
    print()


def show_distance_concentration() -> None:
    print("The second half of the curse: distances bunch up")
    print()
    rng = np.random.default_rng(SEED + 1)
    points = 500
    header = (f"  {'dimension':>10}{'nearest':>12}{'furthest':>12}"
              f"{'ratio':>10}{'spread / mean':>16}")
    print(header)
    print("  " + "-" * (len(header) - 2))
    ratios = []
    for dimension in DIMENSIONS:
        cloud = rng.standard_normal((points, dimension))
        query = rng.standard_normal(dimension)
        distances = np.linalg.norm(cloud - query, axis=1)
        nearest = float(distances.min())
        furthest = float(distances.max())
        ratio = furthest / nearest
        spread = float(distances.std() / distances.mean())
        ratios.append(ratio)
        print(f"  {dimension:>10}{nearest:>12.4f}{furthest:>12.4f}"
              f"{ratio:>10.4f}{spread:>16.4f}")
    print()
    print(f"  In {DIMENSIONS[0]} dimensions the furthest of {points} random points")
    print(f"  is {ratios[0]:.1f} times as far as the nearest. In"
          f" {DIMENSIONS[-1]} dimensions it is {ratios[-1]:.2f} times as far.")
    print("  'Nearest neighbour' still has an answer, but the answer stops being")
    print("  meaningfully nearer than everything else, and small errors in the")
    print("  vectors start deciding the winner.")
    print()
    assert ratios[-1] < ratios[0]
    assert ratios[-1] < 1.5


def show_what_it_means() -> None:
    print("What this changes about reading a similarity score")
    print()
    print("  A cosine similarity of 0.3 is a strong signal in 1000 dimensions")
    print("  and unremarkable in 2, because in 1000 dimensions two unrelated")
    print("  things score near 0 and almost nothing lands at 0.3 by accident.")
    print("  The table above is the calibration: in this run at dimension 512")
    print("  the mean |cos| between unrelated pairs was already under 0.04.")
    print()
    print("  Three practical consequences, in order of how often they bite:")
    print()
    print("  1. Never read a raw similarity score without knowing the")
    print("     dimension. 'Above 0.8 means relevant' is a claim about one")
    print("     model in one space, not a general fact.")
    print("  2. Calibrate against your own data. Score a few hundred pairs you")
    print("     know are unrelated, look at the distribution, and set the")
    print("     threshold from that rather than from a number in a blog post.")
    print("  3. Expect exact nearest-neighbour search to stop paying for")
    print("     itself as the dimension grows. When the nearest point is barely")
    print("     nearer than the tenth nearest, an approximate index that is")
    print("     usually right is a good trade — which is what real vector")
    print("     databases do, and why they are called approximate.")
    print()


def main() -> int:
    rows = measure()
    show_orthogonality(rows)
    show_distance_concentration()
    show_what_it_means()
    print("07_curse_of_dimensionality.py: every assertion held.")
    return 0


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

"""The Day 99 article set, unchanged, plus the queries this lab asks of it.

Six short invented articles, each described by four hand-counted features: how
many times the article talks about cooking, about running, about money, and
about weather. Day 99 used exactly these numbers to introduce vectors, norms
and Euclidean distance. Today they answer a better question, and the fact that
the data has not changed is the point — the measure changed, and that was
enough to change every answer.

Nothing here is real. The articles do not exist and the counts were chosen by
hand so that every number in this lab can be re-derived with a pen.
"""

from __future__ import annotations

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],
}

# The same article, written at twice the length: every count doubled. Same
# subject, same emphasis, twice as many words. This is the vector that breaks
# Euclidean distance in section 1.
LONG_ROAST_CHICKEN = [18, 0, 2, 0]

# Two queries, written as feature counts the same way the articles were.
QUERIES = {
    # A one-line cooking note: "roast it".
    "roast it": [1, 0, 0, 0],
    # "training for a race and what to eat" — two counts for cooking, five for
    # running. Deliberately a close call between two articles; the lab reports
    # the margin rather than pretending the winner was obvious.
    "training for a race and what to eat": [2, 5, 0, 0],
}

# Three vectors whose cosine distances break the triangle inequality. Chosen so
# every number is exact on paper: two axis vectors and the bisector between
# them.
TRIANGLE_A = [1, 0]
TRIANGLE_B = [1, 1]
TRIANGLE_C = [0, 1]

# The sign cases. Each pair is (label, a, b, expected sign of a dot b), with
# `a` fixed so only the second vector's direction changes.
SIGN_CASES = (
    ("same direction",     [3, 0], [6, 0],   "positive"),
    ("45 degrees apart",   [3, 0], [1, 1],   "positive"),
    ("perpendicular",      [3, 0], [0, 5],   "zero"),
    ("135 degrees apart",  [3, 0], [-2, 2],  "negative"),
    ("opposite direction", [3, 0], [-6, 0],  "negative"),
)

# The projection picture: a 3-4-5 triangle, so the arithmetic is exact.
PROJECTION_A = [3, 4]   # length 5
PROJECTION_B = [10, 0]  # length 10

"""Make this directory's own similarity.py the one its tests import.

Both `examples/` and `starter/` contain a module called `similarity`, and
pytest imports test files by putting their directory on `sys.path`. Without
this file, running `pytest` across both directories at once would import
whichever `similarity` was seen first and reuse it for the other suite — so the
starter tests would silently pass against the reference solution instead of
skipping. That is a wrong answer with a green tick on it, which is the worst
kind, and Day 100 shipped a version of this bug before it was caught.

So: put this directory first on the import path, and drop any already-imported
`similarity` or `catalogue` that came from somewhere else.
"""

import sys
from pathlib import Path

HERE = str(Path(__file__).parent.resolve())

if HERE in sys.path:
    sys.path.remove(HERE)
sys.path.insert(0, HERE)

for name in ("similarity", "catalogue", "answers"):
    module = sys.modules.get(name)
    origin = getattr(module, "__file__", "") or ""
    if module is not None and not origin.startswith(HERE):
        del sys.modules[name]

"""The reference implementation: dot product, cosine similarity, cosine distance.

Pure Python, no imports beyond the standard library's `math`. Every function
here is a few lines, and together they are the arithmetic underneath every
semantic search and every retrieval step in a document-answering system.

This is the answer key for `starter/similarity.py`. Read it after you have
written yours, not before.

Design notes worth carrying into any real implementation:

* Every function that compares two vectors checks that the lengths match
  first, and raises ValueError rather than returning a wrong number quietly.
  NumPy raises ValueError for the same mistake, so one `except ValueError`
  catches both.
* `cosine_similarity` refuses the zero vector instead of returning NaN. A zero
  vector has no direction, so "which way does it point" has no answer, and a
  silent NaN travelling through a ranking is much worse than a loud error.
* Results are clamped to [-1, 1]. Floating point can hand you 1.0000000000000002
  for a vector compared with itself, and `math.acos` of that raises ValueError
  — a real failure this lab hit while it was being written.
"""

from __future__ import annotations

import math
from typing import Iterable, Sequence


def _check_same_length(a: Sequence[float], b: Sequence[float]) -> None:
    if len(a) != len(b):
        raise ValueError(
            f"vectors must have the same number of components: "
            f"got {len(a)} and {len(b)}"
        )


def dot(a: Sequence[float], b: Sequence[float]) -> float:
    """Multiply the two vectors component by component, then add it all up.

    That is the whole definition. a dot b = a1*b1 + a2*b2 + ... + an*bn, and
    the answer is a single number, not a vector.
    """
    _check_same_length(a, b)
    return float(sum(x * y for x, y in zip(a, b)))


def l2_norm(a: Sequence[float]) -> float:
    """The length of the vector: the square root of the sum of its squares.

    Note that l2_norm(a) is exactly sqrt(dot(a, a)) — a vector's length is the
    dot product of the vector with itself, square-rooted. Day 99 defined this
    with Pythagoras; today it turns out to be a special case of the dot
    product, which is the first hint that the dot product is the more
    fundamental operation.
    """
    return math.sqrt(dot(a, a))


def normalise(a: Sequence[float]) -> list[float]:
    """Return the unit vector pointing the same way: same direction, length 1."""
    length = l2_norm(a)
    if length == 0.0:
        raise ValueError("the zero vector has no direction, so it cannot be normalised")
    return [x / length for x in a]


def euclidean_distance(a: Sequence[float], b: Sequence[float]) -> float:
    """The straight-line distance between the two points: the length of a - b."""
    _check_same_length(a, b)
    return math.sqrt(sum((x - y) ** 2 for x, y in zip(a, b)))


def cosine_similarity(a: Sequence[float], b: Sequence[float]) -> float:
    """The cosine of the angle between the two vectors, in the range -1 to 1.

    a dot b = |a| |b| cos(theta), so cos(theta) = (a dot b) / (|a| |b|). The two
    divisions are what make this magnitude-free: scaling either vector by any
    positive number multiplies the top and the bottom by the same factor, and
    the answer does not move.

    Equivalently, and this is worth knowing because it is how a vector database
    ends up doing it: cosine similarity is the plain dot product of the two
    UNIT vectors. Normalise once, and every later comparison is a dot product.
    """
    _check_same_length(a, b)
    na, nb = l2_norm(a), l2_norm(b)
    if na == 0.0 or nb == 0.0:
        raise ValueError(
            "cosine similarity is undefined when either vector is the zero "
            "vector: it has no direction to compare"
        )
    return _clamp(dot(a, b) / (na * nb))


def cosine_distance(a: Sequence[float], b: Sequence[float]) -> float:
    """1 minus the cosine similarity: 0 for identical direction, 2 for opposite.

    Called a distance because it grows as things get less alike, but it is NOT
    a metric — it fails the triangle inequality, and section 5 of this lab
    shows a concrete triple where it does.
    """
    return 1.0 - cosine_similarity(a, b)


def angle_degrees(a: Sequence[float], b: Sequence[float]) -> float:
    """The angle between the two vectors, in degrees, from 0 to 180."""
    return math.degrees(math.acos(cosine_similarity(a, b)))


def scalar_projection(a: Sequence[float], b: Sequence[float]) -> float:
    """How much of b lies along a: the length of b's shadow on a's direction.

    (a dot b) / |a|. Note the asymmetry — this is b measured against a's
    direction, so swapping the arguments generally changes the answer, even
    though the dot product itself does not care about order.
    """
    na = l2_norm(a)
    if na == 0.0:
        raise ValueError("cannot project onto the zero vector: it has no direction")
    return dot(a, b) / na


def vector_projection(a: Sequence[float], b: Sequence[float]) -> list[float]:
    """The shadow itself: the part of b that points along a, as a vector."""
    unit_a = normalise(a)
    length = dot(unit_a, b)
    return [length * x for x in unit_a]


def _clamp(value: float, low: float = -1.0, high: float = 1.0) -> float:
    """Keep a cosine inside [-1, 1] despite floating-point rounding."""
    return max(low, min(high, value))


def rank_by_cosine(
    query: Sequence[float], catalogue: dict[str, Sequence[float]]
) -> list[tuple[str, float]]:
    """Every item scored against the query, best first. This is the search.

    Ties are broken by name so the ranking is deterministic and testable; a
    real system would break them by document id or by insertion order, and it
    matters that it breaks them by SOMETHING, because an unstable sort makes a
    ranking that changes between runs.
    """
    scored = [
        (label, cosine_similarity(query, vector)) for label, vector in catalogue.items()
    ]
    return sorted(scored, key=lambda pair: (-pair[1], pair[0]))


def rank_by_euclidean(
    query: Sequence[float], catalogue: dict[str, Sequence[float]]
) -> list[tuple[str, float]]:
    """Every item scored by straight-line distance, nearest first."""
    scored = [
        (label, euclidean_distance(query, vector))
        for label, vector in catalogue.items()
    ]
    return sorted(scored, key=lambda pair: (pair[1], pair[0]))


def normalise_all(catalogue: dict[str, Sequence[float]]) -> dict[str, list[float]]:
    """Put every vector in the catalogue on the unit sphere, once."""
    return {label: normalise(vector) for label, vector in catalogue.items()}


def mean_absolute_cosine(pairs: Iterable[tuple[Sequence[float], Sequence[float]]]) -> float:
    """The average of |cos| over a collection of vector pairs.

    Used in section 6 to measure how nearly orthogonal random vectors become as
    the number of dimensions grows.
    """
    values = [abs(cosine_similarity(a, b)) for a, b in pairs]
    if not values:
        raise ValueError("need at least one pair to average over")
    return sum(values) / len(values)

"""The reference suite: every claim the lesson makes, asserted on real values.

Run from the LAB DIRECTORY:

    .venv/bin/pytest examples -q

Every float comparison declares a tolerance. TOL is 1e-12 for arithmetic that
should agree to the last few bits, and a looser, named tolerance is used where
sampling noise is involved and said so.
"""

from __future__ import annotations

import math

import numpy as np
import pytest

from catalogue import (
    CATALOGUE,
    LONG_ROAST_CHICKEN,
    PROJECTION_A,
    PROJECTION_B,
    QUERIES,
    SIGN_CASES,
    TRIANGLE_A,
    TRIANGLE_B,
    TRIANGLE_C,
)
from similarity import (
    angle_degrees,
    cosine_distance,
    cosine_similarity,
    dot,
    euclidean_distance,
    l2_norm,
    mean_absolute_cosine,
    normalise,
    normalise_all,
    rank_by_cosine,
    rank_by_euclidean,
    scalar_projection,
    vector_projection,
)

TOL = 1e-12
SAMPLING_TOL = 0.05  # 5%: the dimensionality section samples, so it has noise


# -- The dot product itself --------------------------------------------------


def test_dot_is_the_sum_of_products():
    assert dot([1, 2, 3], [4, 5, 6]) == 32.0  # 4 + 10 + 18


def test_dot_matches_numpy_on_every_catalogue_pair():
    for first, a in CATALOGUE.items():
        for second, b in CATALOGUE.items():
            assert dot(a, b) == pytest.approx(float(np.dot(a, b)), abs=TOL), (
                first,
                second,
            )


def test_dot_is_symmetric():
    a, b = CATALOGUE["roast-chicken"], CATALOGUE["marathon-plan"]
    assert dot(a, b) == dot(b, a)


def test_dot_of_a_vector_with_itself_is_its_length_squared():
    for label, vector in CATALOGUE.items():
        assert dot(vector, vector) == pytest.approx(l2_norm(vector) ** 2, abs=1e-9), label


def test_dot_refuses_mismatched_lengths():
    with pytest.raises(ValueError):
        dot([1, 2, 3], [1, 2])


def test_the_geometric_and_algebraic_definitions_agree():
    a, b = PROJECTION_A, PROJECTION_B
    geometric = l2_norm(a) * l2_norm(b) * cosine_similarity(a, b)
    assert dot(a, b) == pytest.approx(geometric, abs=1e-9)


def test_the_projection_triangle_is_three_four_five():
    assert l2_norm(PROJECTION_A) == pytest.approx(5.0, abs=TOL)
    assert l2_norm(PROJECTION_B) == pytest.approx(10.0, abs=TOL)
    assert dot(PROJECTION_A, PROJECTION_B) == pytest.approx(30.0, abs=TOL)


def test_scalar_projection_is_the_shadow_length():
    assert scalar_projection(PROJECTION_A, PROJECTION_B) == pytest.approx(6.0, abs=1e-9)


def test_the_shadow_vector_has_the_shadow_length():
    shadow = vector_projection(PROJECTION_A, PROJECTION_B)
    assert l2_norm(shadow) == pytest.approx(6.0, abs=1e-9)
    assert shadow == pytest.approx([3.6, 4.8], abs=1e-9)


def test_projection_is_not_symmetric_even_though_dot_is():
    onto_a = scalar_projection(PROJECTION_A, PROJECTION_B)
    onto_b = scalar_projection(PROJECTION_B, PROJECTION_A)
    assert onto_a == pytest.approx(6.0, abs=1e-9)
    assert onto_b == pytest.approx(3.0, abs=1e-9)
    assert dot(PROJECTION_A, PROJECTION_B) == dot(PROJECTION_B, PROJECTION_A)


def test_projecting_a_vector_onto_itself_gives_its_length():
    for label, vector in CATALOGUE.items():
        assert scalar_projection(vector, vector) == pytest.approx(
            l2_norm(vector), abs=1e-9
        ), label


# -- The sign of the dot product ---------------------------------------------


@pytest.mark.parametrize("label,a,b,expected", SIGN_CASES)
def test_the_sign_cases(label, a, b, expected):
    value = dot(a, b)
    sign = "positive" if value > 0 else ("zero" if value == 0 else "negative")
    assert sign == expected, label


@pytest.mark.parametrize("label,a,b,expected", SIGN_CASES)
def test_the_sign_of_the_cosine_matches_the_sign_of_the_dot(label, a, b, expected):
    value = dot(a, b)
    cos = cosine_similarity(a, b)
    assert (value > 0) == (cos > 0), label
    assert (value == 0) == (abs(cos) < TOL), label


def test_the_five_angles_are_the_expected_ones():
    expected = [0.0, 45.0, 90.0, 135.0, 180.0]
    measured = [angle_degrees(a, b) for _, a, b, _ in SIGN_CASES]
    assert measured == pytest.approx(expected, abs=1e-9)


def test_perpendicular_vectors_have_a_zero_dot_product():
    assert dot([3, 0], [0, 5]) == 0.0
    assert cosine_similarity([3, 0], [0, 5]) == pytest.approx(0.0, abs=TOL)


def test_three_pairs_in_the_catalogue_are_exactly_orthogonal():
    orthogonal = {
        (first, second)
        for i, first in enumerate(CATALOGUE)
        for second in list(CATALOGUE)[i + 1:]
        if dot(CATALOGUE[first], CATALOGUE[second]) == 0
    }
    assert orthogonal == {
        ("roast-chicken", "storm-bulletin"),
        ("slow-cooker-stew", "storm-bulletin"),
        ("household-budget", "storm-bulletin"),
    }


# -- The length confound -----------------------------------------------------


def test_the_doubled_copy_is_every_count_doubled():
    assert LONG_ROAST_CHICKEN == [2 * n for n in CATALOGUE["roast-chicken"]]


def test_euclidean_distance_to_the_doubled_copy_is_the_articles_own_length():
    short = CATALOGUE["roast-chicken"]
    assert euclidean_distance(short, LONG_ROAST_CHICKEN) == pytest.approx(
        l2_norm(short), abs=1e-9
    )
    assert euclidean_distance(short, LONG_ROAST_CHICKEN) == pytest.approx(
        math.sqrt(82), abs=1e-9
    )


def test_euclidean_calls_the_doubled_copy_further_than_a_different_article():
    short = CATALOGUE["roast-chicken"]
    to_copy = euclidean_distance(short, LONG_ROAST_CHICKEN)
    to_rival = euclidean_distance(short, CATALOGUE["race-day-nutrition"])
    assert to_copy > to_rival
    assert to_copy == pytest.approx(9.055385, abs=1e-6)
    assert to_rival == pytest.approx(8.062258, abs=1e-6)


def test_cosine_calls_the_doubled_copy_identical():
    short = CATALOGUE["roast-chicken"]
    assert cosine_similarity(short, LONG_ROAST_CHICKEN) == pytest.approx(1.0, abs=TOL)
    assert cosine_distance(short, LONG_ROAST_CHICKEN) == pytest.approx(0.0, abs=TOL)


@pytest.mark.parametrize("factor", [0.5, 2, 3, 10, 1000])
def test_scaling_either_vector_by_any_positive_number_leaves_cosine_unchanged(factor):
    a, b = CATALOGUE["roast-chicken"], CATALOGUE["race-day-nutrition"]
    base = cosine_similarity(a, b)
    assert cosine_similarity([factor * x for x in a], b) == pytest.approx(base, abs=TOL)
    assert cosine_similarity(a, [factor * x for x in b]) == pytest.approx(base, abs=TOL)


def test_scaling_by_a_negative_number_flips_the_sign():
    a, b = CATALOGUE["roast-chicken"], CATALOGUE["race-day-nutrition"]
    base = cosine_similarity(a, b)
    flipped = cosine_similarity([-x for x in a], b)
    assert flipped == pytest.approx(-base, abs=TOL)


# -- Cosine similarity against NumPy -----------------------------------------


def numpy_cosine(a, b) -> float:
    a = np.asarray(a, dtype=float)
    b = np.asarray(b, dtype=float)
    return float(a @ b / (np.linalg.norm(a) * np.linalg.norm(b)))


def test_cosine_matches_numpy_on_every_catalogue_pair():
    for first, a in CATALOGUE.items():
        for second, b in CATALOGUE.items():
            assert cosine_similarity(a, b) == pytest.approx(
                numpy_cosine(a, b), abs=TOL
            ), (first, second)


def test_cosine_is_the_dot_product_of_the_unit_vectors():
    for first, a in CATALOGUE.items():
        for second, b in CATALOGUE.items():
            assert cosine_similarity(a, b) == pytest.approx(
                dot(normalise(a), normalise(b)), abs=TOL
            ), (first, second)


def test_every_cosine_lands_inside_minus_one_to_one():
    for a in CATALOGUE.values():
        for b in CATALOGUE.values():
            value = cosine_similarity(a, b)
            assert -1.0 <= value <= 1.0


def test_a_vector_compared_with_itself_is_exactly_one_after_clamping():
    for label, vector in CATALOGUE.items():
        assert cosine_similarity(vector, vector) == pytest.approx(1.0, abs=1e-12), label
        assert cosine_similarity(vector, vector) <= 1.0, label


def test_the_unclamped_formula_really_does_miss_one_on_this_catalogue():
    """The clamp is not defensive decoration: three of six articles miss.

    Measured on the authoring machine with Python 3.14.0. The exact set of
    articles that miss could differ on another platform's floating point, so
    the test asserts the shape of the finding — at least one below and at
    least one above — rather than naming them.
    """
    below, above, exact = [], [], []
    for label, vector in CATALOGUE.items():
        length = math.sqrt(sum(x * x for x in vector))
        raw = sum(x * y for x, y in zip(vector, vector)) / (length * length)
        (below if raw < 1.0 else above if raw > 1.0 else exact).append(label)
    assert below, "expected at least one article to round below 1.0"
    assert above, "expected at least one article to round above 1.0"
    assert len(below) + len(above) + len(exact) == len(CATALOGUE)
    for label in above:
        vector = CATALOGUE[label]
        length = math.sqrt(sum(x * x for x in vector))
        raw = sum(x * y for x, y in zip(vector, vector)) / (length * length)
        with pytest.raises(ValueError):
            math.acos(raw)


def test_cosine_refuses_the_zero_vector():
    with pytest.raises(ValueError):
        cosine_similarity([0, 0, 0, 0], CATALOGUE["roast-chicken"])


def test_normalise_refuses_the_zero_vector():
    with pytest.raises(ValueError):
        normalise([0, 0])


def test_the_clamp_keeps_acos_in_its_domain():
    # race-day-nutrition compared with itself gives 1.0000000000000002 through
    # the unguarded formula, which math.acos refuses. Not invented: found by
    # this suite failing while the lab was being written.
    vector = CATALOGUE["race-day-nutrition"]
    length = math.sqrt(sum(x * x for x in vector))
    unclamped = sum(x * y for x, y in zip(vector, vector)) / (length * length)
    assert unclamped > 1.0
    with pytest.raises(ValueError):
        math.acos(unclamped)
    assert cosine_similarity(vector, vector) == 1.0
    assert angle_degrees(vector, vector) == pytest.approx(0.0, abs=1e-9)


def test_normalised_vectors_all_have_length_one():
    for label, unit in normalise_all(CATALOGUE).items():
        assert l2_norm(unit) == pytest.approx(1.0, abs=TOL), label


# -- Cosine distance and the metric conditions -------------------------------


def test_cosine_distance_is_one_minus_similarity():
    for a in CATALOGUE.values():
        for b in CATALOGUE.values():
            assert cosine_distance(a, b) == pytest.approx(
                1.0 - cosine_similarity(a, b), abs=TOL
            )


def test_cosine_distance_runs_from_zero_to_two():
    assert cosine_distance([1, 0], [1, 0]) == pytest.approx(0.0, abs=TOL)
    assert cosine_distance([1, 0], [0, 1]) == pytest.approx(1.0, abs=TOL)
    assert cosine_distance([1, 0], [-1, 0]) == pytest.approx(2.0, abs=TOL)


def test_no_pair_of_count_vectors_exceeds_distance_one():
    for a in CATALOGUE.values():
        for b in CATALOGUE.values():
            assert cosine_distance(a, b) <= 1.0 + TOL


def test_cosine_distance_fails_the_triangle_inequality():
    ab = cosine_distance(TRIANGLE_A, TRIANGLE_B)
    bc = cosine_distance(TRIANGLE_B, TRIANGLE_C)
    ac = cosine_distance(TRIANGLE_A, TRIANGLE_C)
    assert ab == pytest.approx(1 - 1 / math.sqrt(2), abs=1e-9)
    assert bc == pytest.approx(1 - 1 / math.sqrt(2), abs=1e-9)
    assert ac == pytest.approx(1.0, abs=1e-9)
    assert ac > ab + bc  # the failure, asserted


def test_euclidean_distance_holds_the_triangle_inequality_on_the_same_triple():
    for a, b, c in ((TRIANGLE_A, TRIANGLE_B, TRIANGLE_C),):
        assert euclidean_distance(a, c) <= euclidean_distance(a, b) + euclidean_distance(
            b, c
        ) + TOL
        ua, ub, uc = normalise(a), normalise(b), normalise(c)
        assert euclidean_distance(ua, uc) <= euclidean_distance(
            ua, ub
        ) + euclidean_distance(ub, uc) + TOL


def test_cosine_distance_is_zero_for_vectors_that_are_not_equal():
    # It fails the identity condition too, and that failure is the useful part.
    assert cosine_distance(CATALOGUE["roast-chicken"], LONG_ROAST_CHICKEN) == (
        pytest.approx(0.0, abs=TOL)
    )
    assert CATALOGUE["roast-chicken"] != LONG_ROAST_CHICKEN


def test_cosine_distance_is_symmetric():
    for a in CATALOGUE.values():
        for b in CATALOGUE.values():
            assert cosine_distance(a, b) == pytest.approx(cosine_distance(b, a), abs=TOL)


# -- The ranking equivalence on the unit sphere ------------------------------


def test_the_unit_sphere_identity_holds_on_every_pair():
    units = normalise_all(CATALOGUE)
    for first, u in units.items():
        for second, v in units.items():
            predicted = math.sqrt(max(0.0, 2 - 2 * cosine_similarity(u, v)))
            assert euclidean_distance(u, v) == pytest.approx(predicted, abs=1e-9), (
                first,
                second,
            )


@pytest.mark.parametrize("query_label", list(CATALOGUE))
def test_normalised_rankings_are_identical_under_both_measures(query_label):
    units = normalise_all(CATALOGUE)
    query = units[query_label]
    by_cosine = [label for label, _ in rank_by_cosine(query, units)]
    by_euclid = [label for label, _ in rank_by_euclidean(query, units)]
    assert by_cosine == by_euclid


def test_raw_rankings_can_disagree():
    raw = dict(CATALOGUE)
    raw["roast-chicken (2x)"] = LONG_ROAST_CHICKEN
    query = CATALOGUE["roast-chicken"]
    by_cosine = [label for label, _ in rank_by_cosine(query, raw)]
    by_euclid = [label for label, _ in rank_by_euclidean(query, raw)]
    assert by_cosine != by_euclid


def test_distance_on_the_sphere_falls_strictly_as_cosine_rises():
    previous = None
    for cos in (-1.0, -0.5, 0.0, 0.5, 0.9, 1.0):
        distance = math.sqrt(2 - 2 * cos)
        if previous is not None:
            assert distance < previous
        previous = distance


# -- The semantic search -----------------------------------------------------


def test_the_cooking_note_retrieves_roast_chicken():
    ranked = rank_by_cosine(QUERIES["roast it"], CATALOGUE)
    assert ranked[0][0] == "roast-chicken"
    assert ranked[0][1] == pytest.approx(0.993884, abs=1e-6)
    assert ranked[1][0] == "slow-cooker-stew"


def test_the_training_query_retrieves_race_day_nutrition_narrowly():
    ranked = rank_by_cosine(
        QUERIES["training for a race and what to eat"], CATALOGUE
    )
    assert ranked[0][0] == "race-day-nutrition"
    assert ranked[1][0] == "marathon-plan"
    # The margin is genuinely small, and the test says so rather than hiding it.
    assert 0.002 < ranked[0][1] - ranked[1][1] < 0.003


def test_raw_euclidean_gets_the_cooking_note_wrong():
    ranked = rank_by_euclidean(QUERIES["roast it"], CATALOGUE)
    assert ranked[0][0] == "slow-cooker-stew"
    assert ranked[0][0] != "roast-chicken"


def test_the_raw_dot_product_gets_the_training_query_wrong():
    query = QUERIES["training for a race and what to eat"]
    by_dot = sorted(CATALOGUE, key=lambda label: (-dot(query, CATALOGUE[label]), label))
    assert by_dot[0] == "marathon-plan"
    assert dot(query, CATALOGUE["marathon-plan"]) == 45.0
    assert dot(query, CATALOGUE["race-day-nutrition"]) == 38.0


@pytest.mark.parametrize("factor", [1, 3, 100, 1000])
def test_the_querys_own_length_changes_nothing(factor):
    base = QUERIES["roast it"]
    scaled = [factor * x for x in base]
    assert [label for label, _ in rank_by_cosine(scaled, CATALOGUE)] == [
        label for label, _ in rank_by_cosine(base, CATALOGUE)
    ]


def test_the_ranking_is_deterministic_under_ties():
    # Two articles score exactly 0 against the cooking note. The tie must break
    # the same way every run, or the test suite becomes flaky.
    ranked = rank_by_cosine(QUERIES["roast it"], CATALOGUE)
    tail = [label for label, score in ranked if abs(score) < TOL]
    assert tail == ["marathon-plan", "storm-bulletin"]


# -- The curse of dimensionality ---------------------------------------------


def exact_mean_abs_cos(dimension: int) -> float:
    return math.exp(
        math.lgamma(dimension / 2)
        - 0.5 * math.log(math.pi)
        - math.lgamma((dimension + 1) / 2)
    )


def test_the_exact_formula_reproduces_the_two_hand_checkable_cases():
    assert exact_mean_abs_cos(2) == pytest.approx(2 / math.pi, abs=1e-12)
    assert exact_mean_abs_cos(3) == pytest.approx(0.5, abs=1e-12)


@pytest.mark.parametrize("dimension", [2, 8, 128, 2048])
def test_measured_mean_absolute_cosine_matches_the_exact_formula(dimension):
    rng = np.random.default_rng(103)
    a = rng.standard_normal((2000, dimension))
    b = rng.standard_normal((2000, dimension))
    numerator = np.einsum("ij,ij->i", a, b)
    denominator = np.linalg.norm(a, axis=1) * np.linalg.norm(b, axis=1)
    measured = float(np.mean(np.abs(numerator / denominator)))
    expected = exact_mean_abs_cos(dimension)
    assert abs(measured - expected) / expected < SAMPLING_TOL


def test_mean_absolute_cosine_falls_as_dimension_grows():
    rng = np.random.default_rng(103)
    previous = None
    for dimension in (2, 8, 32, 128, 512, 2048):
        pairs = [
            (rng.standard_normal(dimension), rng.standard_normal(dimension))
            for _ in range(300)
        ]
        value = mean_absolute_cosine(pairs)
        if previous is not None:
            assert value < previous, dimension
        previous = value
    assert previous < 0.05


def test_the_measurement_is_reproducible_with_the_same_seed():
    def run():
        rng = np.random.default_rng(103)
        a = rng.standard_normal((500, 64))
        b = rng.standard_normal((500, 64))
        numerator = np.einsum("ij,ij->i", a, b)
        denominator = np.linalg.norm(a, axis=1) * np.linalg.norm(b, axis=1)
        return float(np.mean(np.abs(numerator / denominator)))

    assert run() == run()


def test_distances_concentrate_as_dimension_grows():
    rng = np.random.default_rng(104)
    ratios = []
    for dimension in (2, 8192):
        cloud = rng.standard_normal((500, dimension))
        query = rng.standard_normal(dimension)
        distances = np.linalg.norm(cloud - query, axis=1)
        ratios.append(float(distances.max() / distances.min()))
    assert ratios[0] > 5.0
    assert ratios[1] < 1.5

lesson_id: D103
day: 103
kind: guided-build
languages: [python, bash]
setup_commands:
  - cd labs/sections/math-statistics-and-data/day-103-dot-products-and-similarity
  - python3 -m venv .venv
  - .venv/bin/pip install -r requirements/requirements.txt
  - .venv/bin/python3 -c "import numpy; print(numpy.__version__)"
run_commands:
  - 'cd examples && ../.venv/bin/python3 01_the_length_confound.py && cd ..'
  - 'cd examples && ../.venv/bin/python3 02_dot_product_and_sign.py && cd ..'
  - 'cd examples && ../.venv/bin/python3 03_from_scratch_vs_numpy.py && cd ..'
  - 'cd examples && ../.venv/bin/python3 04_same_ranking_on_the_sphere.py && cd ..'
  - 'cd examples && ../.venv/bin/python3 05_not_a_metric.py && cd ..'
  - 'cd examples && ../.venv/bin/python3 06_semantic_search.py && cd ..'
  - 'cd examples && ../.venv/bin/python3 07_curse_of_dimensionality.py && cd ..'
  - .venv/bin/pytest examples -q -p no:cacheprovider
  - .venv/bin/pytest starter -q -p no:cacheprovider
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 -> 49 checks, 0 failure(s), exit 0; pytest examples -> 76 passed; pytest starter -> 1 passed, 51 skipped on an untouched checkout, and 52 passed against a fully solved copy of starter/ kept outside the lab. All seven reference scripts exit 0 with every internal assertion holding. Network is needed once to install numpy and pytest; nothing else in the lab opens a socket, and section 7 of the harness greps the sources to prove it. Section 6 re-runs the harness with the ranking-equivalence expectation deliberately inverted and asserts that the re-run exits non-zero and reports exactly one failure, so the suite is demonstrated to be capable of failing rather than merely claimed to be. One finding changed the lab while it was being written: the reference suite failed on an assertion that a vector compared with itself gives exactly 1.0 — three of the six articles miss it, and race-day-nutrition returns 1.0000000000000002 through the unguarded formula, which math.acos refuses. The clamp and the tests around it come from that measured failure, not from anticipation.'

# Dependencies for the Day 103 lab

Two packages, both free and open source, both installed from the Python
Package Index with `pip`, both running entirely on your own machine.

| Package | Pinned version | Why this lab needs it |
| --- | --- | --- |
| `numpy` | `2.5.2` | Two jobs. It is the independent check that your from-scratch dot product and cosine similarity are right — `numpy.dot` and `numpy.linalg.norm` computed the same values by a different route. And it supplies `numpy.random.default_rng`, the seeded generator that makes the curse-of-dimensionality measurement reproducible. |
| `pytest` | `9.1.1` | The test runner from Days 071–074. Nothing new here except what it is pointed at. |

Nothing else is required. Both suites and all seven reference scripts run on
those two packages plus the standard library. The functions you write in
`starter/similarity.py` use nothing but `math`.

## Why numpy is pinned

Two reasons, and only the second is about correctness.

The measurement in `examples/07_curse_of_dimensionality.py` draws random
numbers. It is seeded with `numpy.random.default_rng(103)`, and NumPy
guarantees that a given generator with a given seed produces the same stream —
a guarantee that holds within a major version and is not promised across one.
The captured numbers in `../expected-output/07-curse-of-dimensionality.txt`
therefore belong to numpy 2.5.2 specifically. On a different version the
*shape* of the result will be identical (mean absolute cosine falling towards
zero as the dimension grows, tracking the exact formula) and individual digits
may move.

The second reason is that the version is *checked* rather than assumed.
Section 1 of `tests/run_tests.sh` reads the installed version and compares it
against `requirements.txt`, so a mismatch is reported at the top of the run
instead of surfacing later as a confusing diff.

The version was read from the installed package rather than guessed:

```bash
.venv/bin/python3 -c "from importlib.metadata import version; print(version('numpy'))"
```

On the authoring machine, on 16 August 2026, that printed `2.5.2`.

## Licences

NumPy is distributed under the BSD 3-Clause licence and pytest under the MIT
licence, each stated on that project's own documentation site. Both are
maintained in the open, cost nothing, and need no account, no key and no
signup — personally or commercially.

## One-time install

From the lab directory:

```bash
python3 -m venv .venv
.venv/bin/pip install -r requirements/requirements.txt
.venv/bin/python3 -c "import numpy; print(numpy.__version__)"
```

Expect `2.5.2`. Day 43 covered `python3 -m venv` in full; this is the same
pattern. The environment lives in `.venv/` inside the lab, is already excluded
from version control, and can be deleted at any time with `rm -rf .venv`.

## Network

Installing needs the network, once. **Nothing else in this lab does.** No
script opens a socket, reads a URL or contacts a service, and section 7 of
`tests/run_tests.sh` greps every file under `examples/` and `starter/` for the
patterns that would indicate otherwise.

If you are offline and already have NumPy available somewhere, you do not need
the install at all — see the next section.

## Running without a lab-local environment

If NumPy and pytest are already available in an environment you have
activated, the harness will find `pytest` on your `PATH`. You can also point it
at a specific binary:

```bash
PYTEST=/path/to/pytest bash tests/run_tests.sh
```

The harness uses the `python3` that sits beside that `pytest`, because that is
the interpreter NumPy is installed into. If NumPy is not importable from it,
the harness says so and stops rather than skipping checks quietly.

## What you would give up without NumPy

Exercise 1 — the seven functions in `starter/similarity.py` — needs nothing but
the standard library, and you can complete every one of them on a bare
`python3`. What you lose is the checking: the tests compare your answers
against `numpy.dot` and `numpy.linalg.norm`, and "my implementation agrees with
an independent one" is a much stronger statement than "my implementation
returns a number". You would also lose the dimensionality measurement in
section 7, which needs to draw and compare thousands of high-dimensional
vectors quickly. A pure-Python version of that runs, but it takes long enough
to be annoying, which is itself a fair demonstration of why NumPy exists.

## A package this lab describes but does NOT install

`scipy.spatial.distance` provides `cosine`, `euclidean` and about twenty other
distance functions, and it is the tool you would reach for in real work rather
than writing your own. It is **not** in `requirements.txt` and it was **not**
run here, so this lab reproduces no output from it and makes no claim about
its numbers. The lesson describes it from its own documentation and says
plainly that nothing was executed. SciPy is BSD-licensed and free, and
installing it is one line if you want to compare — but then the comparison is
yours, not this lab's.

numpy==2.5.2
pytest==9.1.1

# Your brief — Which Question Are You Asking?

Day 99 taught you to measure how far apart two vectors are. Today you find out
that "how far apart" is usually the wrong question about text, write the
measure that asks the right one, and prove three things about it that most
people who use it every day have never checked.

There are two files to edit and one command to run.

## The command

From the **lab directory** — one level up from here:

```bash
.venv/bin/pytest starter -q
```

Anything you have not written yet is **skipped**, not failed. On an untouched
checkout you should see `1 passed, 51 skipped`. That is your running score:
every exercise you finish turns a skip into a pass, and a wrong answer fails
loudly with both numbers printed.

## The files

| File | What you do in it |
| --- | --- |
| `similarity.py` | Write seven functions. Pure Python; `import math` is the only import allowed. |
| `answers.py` | Replace 24 `None` values with predictions you make **before** running anything. |

## Exercise 1 — the toolkit (7 functions)

| # | Function | One-line summary |
| --- | --- | --- |
| 1.1 | `dot` | Multiply component by component, then add. |
| 1.2 | `l2_norm` | `sqrt(dot(a, a))` — a vector's length is the square root of it dotted with itself. |
| 1.3 | `normalise` | Divide by the length. Refuse the zero vector. |
| 1.4 | `euclidean_distance` | The length of the difference. Day 99's measure. |
| 1.5 | `cosine_similarity` | `dot(a, b) / (|a| * |b|)`, clamped to -1..1, refusing the zero vector. |
| 1.6 | `cosine_distance` | `1 - cosine_similarity(a, b)`. |
| 1.7 | `rank_by_cosine` | Score every item, sort best first, break ties by label. |

Three of them have a trap in them, and each trap has its own test:

- **1.3 and 1.5 must refuse the zero vector** with `ValueError`. It has no
  direction, so there is no angle to it. Returning `NaN` is the tempting
  shortcut; a `NaN` sorts unpredictably and poisons every average downstream.
- **1.5 must clamp.** Three of this lab's six articles, compared with
  themselves through the unguarded formula, come out at something other than
  exactly 1.0 — one of them at `1.0000000000000002`, which `math.acos` refuses
  outright. This is measured on the authoring machine, not hypothetical.
- **1.7 must break ties deterministically.** Two articles score exactly 0.0
  against the cooking query. A ranking that orders them differently between
  runs makes a test suite that fails at random.

## Exercises 2 to 6 — predict, then check

Twenty-four predictions in `answers.py`, grouped by theme:

| Exercise | Theme | What you are predicting |
| --- | --- | --- |
| 2 | The length confound | Two distances, one cosine, and the general fact behind them |
| 3 | The sign | Three dot products, one angle, and which articles are orthogonal |
| 4 | Not a metric | Two cosine distances, and whether the triangle inequality survives |
| 5 | The unit sphere | The identity `sqrt(2 - 2cos)`, two distances, two ranking questions |
| 6 | Search and the curse | Four retrieval outcomes and one limit |

Write the predictions **first**. That is not a study tip, it is the design of
the exercise: the entire day is about two measures that feel like they should
agree and do not, and the only way to find out whether your intuition is right
is to commit to an answer while it can still be wrong.

Several tests then check that your predictions and your own implementation
agree with **each other**, so a lucky guess with broken code still fails.

## When you are done

`52 passed`. Then read `examples/similarity.py` and compare — your version and
the reference should agree on behaviour, not on wording. Then run the seven
demonstration scripts in `examples/` in order; they take the same numbers much
further than the tests do.

## Rules

- No `numpy` in `similarity.py`. The whole point is that nothing is done for
  you; NumPy appears only in the tests, as the independent check.
- Never modify an argument. Return new lists.
- Raise `ValueError`, not a bare `assert`, on nonsense input — NumPy raises
  `ValueError` for the same situations, so one `except ValueError` catches your
  code and the library alike.

"""Exercises 2 to 6 — predict first, then let the arithmetic tell you.

Every value below is a prediction you make BEFORE running anything. Replace
each `None` with your answer, then check from the lab directory:

    .venv/bin/pytest starter -q

Each prediction still set to None is SKIPPED rather than failed, so the run is
a running score. A wrong prediction fails with both numbers printed.

Predicting first matters here more than usual, because the whole day is about
two measures that feel like they should agree and do not. The only way to find
out whether your intuition is right is to commit to an answer while it can
still be wrong.

The data everything below refers to — the same six invented articles as Day 99,
described by how often each one talks about four things:

                        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

and one more: roast-chicken written at twice the length, every count doubled,

    roast-chicken (2x)       18        0      2        0

Float answers are compared with a tolerance of 1e-6, so four decimal places is
plenty. Where a whole number is exact, give the whole number.
"""

# ---------------------------------------------------------------------------
# Exercise 2 — the length confound
# ---------------------------------------------------------------------------

# 2.1 The Euclidean distance between roast-chicken and its doubled copy.
#     Work it out on paper: subtract, square, add, square-root.
#     [9, 0, 1, 0] - [18, 0, 2, 0] = ?
DISTANCE_TO_DOUBLED_COPY = None

# 2.2 The Euclidean distance between roast-chicken and race-day-nutrition.
DISTANCE_TO_RACE_DAY = None

# 2.3 Given those two numbers: does Euclidean distance place the doubled copy
#     of roast-chicken FURTHER from roast-chicken than race-day-nutrition is?
#     True or False.
DOUBLED_COPY_IS_FURTHER = None

# 2.4 The cosine similarity between roast-chicken and its doubled copy.
#     You should be able to answer this one without any arithmetic at all.
COSINE_TO_DOUBLED_COPY = None

# 2.5 There is a tidy general fact behind 2.1. For any vector v, the distance
#     between v and 2v equals one of the following. Which? Answer with the
#     string exactly as written: "0", "|v|", "2|v|", or "|v| squared".
DISTANCE_BETWEEN_V_AND_2V = None


# ---------------------------------------------------------------------------
# Exercise 3 — the sign of the dot product
# ---------------------------------------------------------------------------

# 3.1 [3, 0] dot [6, 0] — a single number.
DOT_SAME_DIRECTION = None

# 3.2 [3, 0] dot [0, 5].
DOT_PERPENDICULAR = None

# 3.3 [3, 0] dot [-6, 0].
DOT_OPPOSITE = None

# 3.4 The angle in degrees between [3, 0] and [1, 1]. A whole number.
ANGLE_45_CASE = None

# 3.5 Which articles in the table above have a dot product of exactly 0 with
#     storm-bulletin? A dot product of 0 means the two share no vocabulary at
#     all — wherever one has a count, the other has none. Answer with a list
#     of the article names, sorted alphabetically. (There is more than one.)
ORTHOGONAL_TO_STORM_BULLETIN = None


# ---------------------------------------------------------------------------
# Exercise 4 — cosine distance is not a metric
# ---------------------------------------------------------------------------
#
# Three vectors in two dimensions:
#
#     a = [1, 0]      b = [1, 1]      c = [0, 1]
#

# 4.1 The cosine distance from a to b, to four decimal places.
D_A_TO_B = None

# 4.2 The cosine distance from a to c.
D_A_TO_C = None

# 4.3 The triangle inequality says d(a, c) <= d(a, b) + d(b, c). Does it hold
#     for these three under COSINE distance? True or False.
TRIANGLE_HOLDS_FOR_COSINE = None

# 4.4 Does it hold for the same three under EUCLIDEAN distance? True or False.
TRIANGLE_HOLDS_FOR_EUCLIDEAN = None


# ---------------------------------------------------------------------------
# Exercise 5 — the same ranking on the unit sphere
# ---------------------------------------------------------------------------
#
# For two UNIT vectors u and v:
#
#     |u - v|^2 = (u - v) dot (u - v)
#               = (u dot u) - 2 (u dot v) + (v dot v)
#               = 1 - 2 cos(theta) + 1
#

# 5.1 Complete the identity. The Euclidean distance between two unit vectors
#     equals sqrt of what expression in cos? Answer with the string exactly as
#     written: "2 - 2cos", "1 - cos", "2 + 2cos", or "1 - 2cos".
UNIT_DISTANCE_FORMULA = None

# 5.2 Two unit vectors at 90 degrees. How far apart are they, to four decimal
#     places?
DISTANCE_BETWEEN_PERPENDICULAR_UNIT_VECTORS = None

# 5.3 Two unit vectors pointing in opposite directions. How far apart?
DISTANCE_BETWEEN_OPPOSITE_UNIT_VECTORS = None

# 5.4 Rank the catalogue against a normalised roast-chicken, once by cosine
#     similarity descending and once by Euclidean distance ascending. Are the
#     two orderings identical? True or False.
NORMALISED_RANKINGS_MATCH = None

# 5.5 Do the same on the RAW vectors, with the doubled copy included in the
#     catalogue. Are those two orderings identical? True or False.
RAW_RANKINGS_MATCH = None


# ---------------------------------------------------------------------------
# Exercise 6 — the search, and the curse
# ---------------------------------------------------------------------------

# 6.1 The query "roast it" becomes [1, 0, 0, 0]. Which article does cosine
#     similarity rank first? A string, exactly as spelled in the table.
TOP_HIT_FOR_ROAST_IT = None

# 6.2 The same query, ranked by RAW Euclidean distance instead. Which article
#     comes first? (Day 99 answered this one; it is not the same answer.)
NEAREST_BY_RAW_EUCLIDEAN_FOR_ROAST_IT = None

# 6.3 The query "training for a race and what to eat" becomes [2, 5, 0, 0].
#     Which article does cosine rank first?
TOP_HIT_FOR_TRAINING = None

# 6.4 Multiply that query by 100, giving [200, 500, 0, 0]. Does the cosine
#     ranking change? True or False.
SCALING_THE_QUERY_CHANGES_THE_RANKING = None

# 6.5 Two random vectors in a high-dimensional space. As the number of
#     dimensions grows, the average absolute cosine similarity between them
#     tends towards which value? Answer with a number: 0, 0.5, or 1.
MEAN_ABS_COSINE_TENDS_TOWARDS = None

"""Make this directory's own similarity.py the one its tests import.

Both `examples/` and `starter/` contain a module called `similarity`, and
pytest imports test files by putting their directory on `sys.path`. Without
this file, running `pytest` across both directories at once would import
whichever `similarity` was seen first and reuse it for the other suite — so
these starter tests would silently pass against the reference solution instead
of skipping. That is a wrong answer with a green tick on it, which is the worst
kind, and Day 100 shipped a version of this bug before it was caught.

So: put this directory first on the import path, and drop any already-imported
`similarity` or `answers` that came from somewhere else.

Section 4 of tests/run_tests.sh checks that this still works, by comparing the
skip count from `pytest starter` against the skip count from a combined run.
"""

import sys
from pathlib import Path

HERE = str(Path(__file__).parent.resolve())

if HERE in sys.path:
    sys.path.remove(HERE)
sys.path.insert(0, HERE)

for name in ("similarity", "catalogue", "answers"):
    module = sys.modules.get(name)
    origin = getattr(module, "__file__", "") or ""
    if module is not None and not origin.startswith(HERE):
        del sys.modules[name]

"""Exercise 1 — write the similarity toolkit yourself, in pure Python.

Seven functions, none longer than four lines. Together they are the entire
arithmetic of semantic search, and after writing them you will never again be
unsure what a vector database is doing when it says "cosine".

Check your work as you go, from the LAB DIRECTORY (one level up from here):

    .venv/bin/pytest starter -q

Every test for a function you have not written yet is SKIPPED, not failed, so
the output is a running score rather than a wall of red. When all of them pass,
compare your file with examples/similarity.py — they should agree on behaviour,
not necessarily on wording.

Rules for all seven:

  * pure Python only — `import math` is allowed and nothing else. The point of
    the exercise is that nothing here is done for you;
  * never modify the arguments;
  * raise ValueError, not a bare assert, when the input makes no sense. NumPy
    raises ValueError for the same situations, so one `except ValueError` will
    catch your code and the library alike.
"""

from __future__ import annotations

import math


def _check_same_length(a, b) -> None:
    """Written for you: refuse two vectors of different lengths, loudly.

    Every function below that takes two vectors should call this first.
    """
    if len(a) != len(b):
        raise ValueError(
            f"vectors must have the same number of components: "
            f"got {len(a)} and {len(b)}"
        )


# ------------------------------------------------------------------ 1.1 --
def dot(a, b):
    """EXERCISE 1.1 — the dot product: multiply component by component, then add.

        dot([1, 2, 3], [4, 5, 6]) = 1*4 + 2*5 + 3*6 = 4 + 10 + 18 = 32.0

    Return a float, not a list — the dot product of two vectors is a single
    number. Call _check_same_length first.

    Hint: sum(x * y for x, y in zip(a, b)), wrapped in float().
    """
    raise NotImplementedError("write dot")


# ------------------------------------------------------------------ 1.2 --
def l2_norm(a):
    """EXERCISE 1.2 — the length of a vector: sqrt of the sum of its squares.

        l2_norm([3, 4]) = sqrt(9 + 16) = sqrt(25) = 5.0

    Day 99 built this with Pythagoras. Today there is a shorter route worth
    noticing and using: a vector's length is the square root of the vector
    dotted with ITSELF.

    Hint: math.sqrt(dot(a, a)). One line, and it reuses 1.1.
    """
    raise NotImplementedError("write l2_norm")


# ------------------------------------------------------------------ 1.3 --
def normalise(a):
    """EXERCISE 1.3 — the unit vector: same direction, length exactly 1.

        normalise([3, 4]) = [0.6, 0.8]

    Divide every component by the vector's own length, and return a NEW list.

    The zero vector has no direction, so there is no unit vector pointing the
    same way. Raise ValueError with a message saying so, rather than letting
    Python raise ZeroDivisionError from somewhere deeper.
    """
    raise NotImplementedError("write normalise")


# ------------------------------------------------------------------ 1.4 --
def euclidean_distance(a, b):
    """EXERCISE 1.4 — straight-line distance: the length of the difference.

        euclidean_distance([9, 0, 1, 0], [8, 0, 2, 0])
            = sqrt(1 + 0 + 1 + 0) = sqrt(2) = 1.41421...

    This is Day 99's measure, and today's job is to know when it is the wrong
    one. Call _check_same_length first.
    """
    raise NotImplementedError("write euclidean_distance")


# ------------------------------------------------------------------ 1.5 --
def cosine_similarity(a, b):
    """EXERCISE 1.5 — the cosine of the angle between them, from -1 to 1.

        a dot b = |a| |b| cos(theta)      so      cos(theta) = (a dot b) / (|a| |b|)

    Three things this function must get right, and each of them is asserted by
    a separate test:

      1. Divide by BOTH lengths. That is what makes the result magnitude-free:
         doubling either vector must not change the answer at all.
      2. Raise ValueError if either vector is the zero vector. Returning NaN
         is the tempting shortcut and it is a bad one — a NaN sorts
         unpredictably and quietly ruins every average it touches.
      3. Clamp the result into the range -1 to 1 before returning it. Floating
         point can hand you 1.0000000000000002 for a vector compared with
         itself — three of this lab's six articles miss exact 1.0 — and
         math.acos of anything above 1.0 raises ValueError.

    Hint for the clamp: max(-1.0, min(1.0, value)).
    """
    raise NotImplementedError("write cosine_similarity")


# ------------------------------------------------------------------ 1.6 --
def cosine_distance(a, b):
    """EXERCISE 1.6 — one minus the cosine similarity.

        cosine_distance(a, b) = 1 - cosine_similarity(a, b)

    Zero when the two point the same way, 1 when they are perpendicular, 2
    when they point in opposite directions. One line, reusing 1.5.

    Remember what exercise 3 will make you prove about it: despite the name,
    this is not a metric.
    """
    raise NotImplementedError("write cosine_distance")


# ------------------------------------------------------------------ 1.7 --
def rank_by_cosine(query, catalogue):
    """EXERCISE 1.7 — the search itself. Score everything, best first.

    `catalogue` is a dict of {label: vector}. Return a list of
    (label, similarity) pairs sorted so the highest similarity comes first.

    Break ties by label, alphabetically. That matters more than it looks: two
    articles in this lab score exactly 0.0 against the cooking query, and a
    ranking that puts them in a different order on different runs makes a test
    suite that fails at random.

    Hint: build the list of pairs, then
        sorted(pairs, key=lambda pair: (-pair[1], pair[0]))
    The minus sign sorts the score downwards while the label still sorts
    upwards, which is the whole trick.
    """
    raise NotImplementedError("write rank_by_cosine")

"""Your running score. Run from the LAB DIRECTORY:

    .venv/bin/pytest starter -q

Anything you have not written yet is SKIPPED, not failed. A skip means "not
attempted"; a failure means "attempted and wrong", and the failure prints both
your answer and the real one.

Float comparisons use a tolerance of TOL, stated below, because floating-point
equality is a trap (Day 70) and because this lab measured three of six articles
missing exact 1.0 when compared with themselves.
"""

from __future__ import annotations

import math

import numpy as np
import pytest

import answers
from similarity import (
    cosine_distance,
    cosine_similarity,
    dot,
    euclidean_distance,
    l2_norm,
    normalise,
    rank_by_cosine,
)

TOL = 1e-6

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],
}
LONG_ROAST_CHICKEN = [18, 0, 2, 0]

TRIANGLE_A = [1, 0]
TRIANGLE_B = [1, 1]
TRIANGLE_C = [0, 1]

QUERY_ROAST = [1, 0, 0, 0]
QUERY_TRAINING = [2, 5, 0, 0]


def written(fn, *args, **kwargs):
    """Run part of your toolkit, or skip the test if it is not written yet."""
    try:
        return fn(*args, **kwargs)
    except NotImplementedError as exc:
        pytest.skip(f"not written yet: {exc}")


def predicted(name):
    """Read one prediction from answers.py, or skip if it is still None."""
    value = getattr(answers, name)
    if value is None:
        pytest.skip(f"answers.{name} is still unanswered")
    return value


# -- Exercise 0: the environment ---------------------------------------------


def test_0_the_environment_is_ready():
    """Always passes once the install worked. Everything below is your work."""
    assert np.__version__, "numpy is importable"
    assert math.isclose(np.linalg.norm([3, 4]), 5.0), "numpy agrees that 3-4-5 works"


# -- Exercise 1: your similarity toolkit -------------------------------------


def test_1_1_dot_is_the_sum_of_products():
    assert written(dot, [1, 2, 3], [4, 5, 6]) == pytest.approx(32.0, abs=TOL)
    assert dot([9, 0, 1, 0], [8, 0, 2, 0]) == pytest.approx(74.0, abs=TOL)


def test_1_1_dot_matches_numpy_on_every_catalogue_pair():
    written(dot, [1], [1])
    for first, a in CATALOGUE.items():
        for second, b in CATALOGUE.items():
            assert dot(a, b) == pytest.approx(float(np.dot(a, b)), abs=TOL), (
                first,
                second,
            )


def test_1_1_dot_refuses_mismatched_lengths():
    written(dot, [1], [1])
    with pytest.raises(ValueError):
        dot([1, 2, 3], [1, 2])


def test_1_2_l2_norm():
    assert written(l2_norm, [3, 4]) == pytest.approx(5.0, abs=TOL)
    assert l2_norm([9, 0, 1, 0]) == pytest.approx(math.sqrt(82), abs=TOL)


def test_1_2_l2_norm_matches_numpy():
    written(l2_norm, [1])
    for label, vector in CATALOGUE.items():
        assert l2_norm(vector) == pytest.approx(
            float(np.linalg.norm(vector)), abs=TOL
        ), label


def test_1_3_normalise_gives_length_one():
    assert written(normalise, [3, 4]) == pytest.approx([0.6, 0.8], abs=TOL)
    for label, vector in CATALOGUE.items():
        assert l2_norm(normalise(vector)) == pytest.approx(1.0, abs=TOL), label


def test_1_3_normalise_does_not_modify_its_argument():
    vector = [3, 4]
    written(normalise, vector)
    assert vector == [3, 4], "normalise must return a NEW list"


def test_1_3_normalise_refuses_the_zero_vector():
    written(normalise, [3, 4])
    with pytest.raises(ValueError):
        normalise([0, 0, 0, 0])


def test_1_4_euclidean_distance():
    assert written(
        euclidean_distance, [9, 0, 1, 0], [8, 0, 2, 0]
    ) == pytest.approx(math.sqrt(2), abs=TOL)
    assert euclidean_distance([0, 0], [3, 4]) == pytest.approx(5.0, abs=TOL)


def test_1_4_euclidean_distance_matches_numpy():
    written(euclidean_distance, [1], [1])
    for first, a in CATALOGUE.items():
        for second, b in CATALOGUE.items():
            expected = float(np.linalg.norm(np.array(a) - np.array(b)))
            assert euclidean_distance(a, b) == pytest.approx(expected, abs=TOL), (
                first,
                second,
            )


def test_1_5_cosine_similarity_basic_cases():
    assert written(cosine_similarity, [1, 0], [1, 0]) == pytest.approx(1.0, abs=TOL)
    assert cosine_similarity([1, 0], [0, 1]) == pytest.approx(0.0, abs=TOL)
    assert cosine_similarity([1, 0], [-1, 0]) == pytest.approx(-1.0, abs=TOL)
    assert cosine_similarity([1, 0], [1, 1]) == pytest.approx(
        1 / math.sqrt(2), abs=TOL
    )


def test_1_5_cosine_similarity_matches_numpy():
    written(cosine_similarity, [1, 0], [1, 0])
    for first, a in CATALOGUE.items():
        for second, b in CATALOGUE.items():
            expected = float(
                np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b))
            )
            assert cosine_similarity(a, b) == pytest.approx(expected, abs=TOL), (
                first,
                second,
            )


@pytest.mark.parametrize("factor", [0.5, 2, 3, 100])
def test_1_5_cosine_ignores_magnitude(factor):
    a, b = CATALOGUE["roast-chicken"], CATALOGUE["race-day-nutrition"]
    base = written(cosine_similarity, a, b)
    assert cosine_similarity([factor * x for x in a], b) == pytest.approx(
        base, abs=TOL
    )
    assert cosine_similarity(a, [factor * x for x in b]) == pytest.approx(
        base, abs=TOL
    )


def test_1_5_cosine_refuses_the_zero_vector():
    written(cosine_similarity, [1, 0], [1, 0])
    with pytest.raises(ValueError):
        cosine_similarity([0, 0, 0, 0], CATALOGUE["roast-chicken"])


def test_1_5_cosine_is_clamped_so_acos_never_raises():
    """The clamp is load-bearing: without it this catalogue breaks acos."""
    written(cosine_similarity, [1, 0], [1, 0])
    for label, vector in CATALOGUE.items():
        value = cosine_similarity(vector, vector)
        assert -1.0 <= value <= 1.0, label
        math.acos(value)  # raises ValueError if the clamp is missing


def test_1_6_cosine_distance():
    assert written(cosine_distance, [1, 0], [1, 0]) == pytest.approx(0.0, abs=TOL)
    assert cosine_distance([1, 0], [0, 1]) == pytest.approx(1.0, abs=TOL)
    assert cosine_distance([1, 0], [-1, 0]) == pytest.approx(2.0, abs=TOL)


def test_1_7_rank_by_cosine_orders_best_first():
    ranked = written(rank_by_cosine, QUERY_ROAST, CATALOGUE)
    assert [label for label, _ in ranked][:2] == [
        "roast-chicken",
        "slow-cooker-stew",
    ]
    scores = [score for _, score in ranked]
    assert scores == sorted(scores, reverse=True)


def test_1_7_rank_by_cosine_breaks_ties_alphabetically():
    ranked = written(rank_by_cosine, QUERY_ROAST, CATALOGUE)
    zeros = [label for label, score in ranked if abs(score) < TOL]
    assert zeros == ["marathon-plan", "storm-bulletin"]


def test_1_7_rank_by_cosine_returns_every_item():
    ranked = written(rank_by_cosine, QUERY_TRAINING, CATALOGUE)
    assert sorted(label for label, _ in ranked) == sorted(CATALOGUE)


# -- Exercise 2: the length confound -----------------------------------------


def test_2_1_distance_to_the_doubled_copy():
    assert predicted("DISTANCE_TO_DOUBLED_COPY") == pytest.approx(
        math.sqrt(82), abs=1e-4
    )


def test_2_2_distance_to_race_day():
    assert predicted("DISTANCE_TO_RACE_DAY") == pytest.approx(math.sqrt(65), abs=1e-4)


def test_2_3_the_doubled_copy_really_is_further():
    assert predicted("DOUBLED_COPY_IS_FURTHER") is True


def test_2_4_cosine_to_the_doubled_copy():
    assert predicted("COSINE_TO_DOUBLED_COPY") == pytest.approx(1.0, abs=1e-4)


def test_2_5_the_general_fact():
    assert predicted("DISTANCE_BETWEEN_V_AND_2V") == "|v|"


def test_2_the_predictions_match_your_own_code():
    """Your predictions and your implementation must agree with each other."""
    written(euclidean_distance, [1], [1])
    written(cosine_similarity, [1, 0], [1, 0])
    short = CATALOGUE["roast-chicken"]
    assert euclidean_distance(short, LONG_ROAST_CHICKEN) == pytest.approx(
        predicted("DISTANCE_TO_DOUBLED_COPY"), abs=1e-4
    )
    assert cosine_similarity(short, LONG_ROAST_CHICKEN) == pytest.approx(
        predicted("COSINE_TO_DOUBLED_COPY"), abs=1e-4
    )


# -- Exercise 3: the sign ----------------------------------------------------


def test_3_1_same_direction():
    assert predicted("DOT_SAME_DIRECTION") == pytest.approx(18.0, abs=TOL)


def test_3_2_perpendicular():
    assert predicted("DOT_PERPENDICULAR") == pytest.approx(0.0, abs=TOL)


def test_3_3_opposite():
    assert predicted("DOT_OPPOSITE") == pytest.approx(-18.0, abs=TOL)


def test_3_4_the_45_degree_case():
    assert predicted("ANGLE_45_CASE") == pytest.approx(45.0, abs=0.5)


def test_3_5_orthogonal_to_storm_bulletin():
    assert predicted("ORTHOGONAL_TO_STORM_BULLETIN") == [
        "household-budget",
        "roast-chicken",
        "slow-cooker-stew",
    ]


# -- Exercise 4: not a metric ------------------------------------------------


def test_4_1_cosine_distance_a_to_b():
    assert predicted("D_A_TO_B") == pytest.approx(1 - 1 / math.sqrt(2), abs=1e-4)


def test_4_2_cosine_distance_a_to_c():
    assert predicted("D_A_TO_C") == pytest.approx(1.0, abs=1e-4)


def test_4_3_the_triangle_inequality_fails_for_cosine():
    assert predicted("TRIANGLE_HOLDS_FOR_COSINE") is False


def test_4_4_the_triangle_inequality_holds_for_euclidean():
    assert predicted("TRIANGLE_HOLDS_FOR_EUCLIDEAN") is True


def test_4_your_own_code_reproduces_the_failure():
    written(cosine_distance, [1, 0], [1, 0])
    ab = cosine_distance(TRIANGLE_A, TRIANGLE_B)
    bc = cosine_distance(TRIANGLE_B, TRIANGLE_C)
    ac = cosine_distance(TRIANGLE_A, TRIANGLE_C)
    assert ac > ab + bc, "cosine distance should fail the triangle inequality here"


# -- Exercise 5: the same ranking on the sphere ------------------------------


def test_5_1_the_identity():
    assert predicted("UNIT_DISTANCE_FORMULA") == "2 - 2cos"


def test_5_2_perpendicular_unit_vectors():
    assert predicted(
        "DISTANCE_BETWEEN_PERPENDICULAR_UNIT_VECTORS"
    ) == pytest.approx(math.sqrt(2), abs=1e-4)


def test_5_3_opposite_unit_vectors():
    assert predicted("DISTANCE_BETWEEN_OPPOSITE_UNIT_VECTORS") == pytest.approx(
        2.0, abs=1e-4
    )


def test_5_4_normalised_rankings_match():
    assert predicted("NORMALISED_RANKINGS_MATCH") is True


def test_5_5_raw_rankings_do_not():
    assert predicted("RAW_RANKINGS_MATCH") is False


def test_5_your_own_code_proves_the_ranking_equivalence():
    written(normalise, [3, 4])
    written(cosine_similarity, [1, 0], [1, 0])
    written(euclidean_distance, [1], [1])
    units = {label: normalise(v) for label, v in CATALOGUE.items()}
    query = units["roast-chicken"]
    by_cosine = sorted(units, key=lambda k: (-cosine_similarity(query, units[k]), k))
    by_euclid = sorted(units, key=lambda k: (euclidean_distance(query, units[k]), k))
    assert by_cosine == by_euclid


# -- Exercise 6: the search, and the curse -----------------------------------


def test_6_1_top_hit_for_the_cooking_note():
    assert predicted("TOP_HIT_FOR_ROAST_IT") == "roast-chicken"


def test_6_2_raw_euclidean_picks_a_different_article():
    assert predicted("NEAREST_BY_RAW_EUCLIDEAN_FOR_ROAST_IT") == "slow-cooker-stew"


def test_6_3_top_hit_for_the_training_query():
    assert predicted("TOP_HIT_FOR_TRAINING") == "race-day-nutrition"


def test_6_4_scaling_the_query_changes_nothing():
    assert predicted("SCALING_THE_QUERY_CHANGES_THE_RANKING") is False


def test_6_5_high_dimensional_cosine_tends_to_zero():
    assert predicted("MEAN_ABS_COSINE_TENDS_TOWARDS") == 0


def test_6_your_own_search_finds_the_predicted_articles():
    ranked = written(rank_by_cosine, QUERY_ROAST, CATALOGUE)
    assert ranked[0][0] == predicted("TOP_HIT_FOR_ROAST_IT")
    training = rank_by_cosine(QUERY_TRAINING, CATALOGUE)
    assert training[0][0] == predicted("TOP_HIT_FOR_TRAINING")


def test_6_your_own_code_measures_the_curse():
    """Generate random pairs at growing dimension and watch |cos| collapse."""
    written(cosine_similarity, [1, 0], [1, 0])
    rng = np.random.default_rng(103)
    previous = None
    for dimension in (2, 32, 512):
        values = [
            abs(
                cosine_similarity(
                    rng.standard_normal(dimension).tolist(),
                    rng.standard_normal(dimension).tolist(),
                )
            )
            for _ in range(200)
        ]
        mean = sum(values) / len(values)
        if previous is not None:
            assert mean < previous, dimension
        previous = mean
    assert previous < 0.1

#!/usr/bin/env bash
# Tests for the Day 103 lab. Run from the lab directory:
#   bash tests/run_tests.sh
#
# The harness proves seven specific claims the lesson makes, and it proves each
# one by running code and reading real values rather than by reading source:
#
#   * Euclidean distance calls an article's own doubled copy FURTHER away than
#     a different article is, while cosine similarity calls it identical —
#     the day's motivating failure, computed, not asserted;
#   * the from-scratch dot product, cosine similarity and cosine distance
#     agree with NumPy on every pair in the catalogue, to a stated tolerance;
#   * the sign of the dot product tracks the angle: positive under 90 degrees,
#     zero at exactly 90, negative above;
#   * on NORMALISED vectors, ranking by cosine and ranking by Euclidean
#     distance produce the identical order — and on raw vectors they do not;
#   * cosine distance fails the triangle inequality on a concrete triple;
#   * the semantic search returns the expected top hit for two queries, and
#     the query's own magnitude changes nothing;
#   * mean absolute cosine similarity between random vectors falls towards
#     zero as the dimension grows, from a seeded generator.
#
# Everything runs offline. Nothing binds a port, nothing writes outside the
# lab, nothing needs a key. Deterministic, non-interactive, 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
}

check_eq() {
  # check_eq <label> <expected> <actual>
  if [ "$2" = "$3" ]; then
    check "$1" "yes"
  else
    check "$1 (expected [$2], got [$3])" "no"
  fi
}

# Resolve pytest: an explicit override, then this lab's .venv, then PATH.
# Fails loudly with instructions rather than silently skipping checks.
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
}

pytest_bin="$(resolve_tool pytest "${PYTEST:-}")" || {
  echo "FAIL: pytest not found." >&2
  echo "  Install the 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 pytest:" >&2
  echo "    PYTEST=/path/to/pytest bash tests/run_tests.sh" >&2
  exit 1
}

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

if ! "${python_bin}" -c "import numpy" >/dev/null 2>&1; then
  echo "FAIL: numpy is not importable from ${python_bin}." >&2
  echo "  Install the lab's dependencies with:" >&2
  echo "    python3 -m venv .venv" >&2
  echo "    .venv/bin/pip install -r requirements/requirements.txt" >&2
  exit 1
fi

echo "Day 103 — Which Question Are You Asking?"
echo

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

versions="$("${python_bin}" - <<'PY'
import platform
import sys
from importlib.metadata import version

print(f"python   {platform.python_version()}")
for name in ("numpy", "pytest"):
    print(f"{name:<8} {version(name)}")
print(f"platform {platform.platform()}")
print(f"exe      {sys.executable.rsplit('/', 3)[-1]}")
PY
)"
echo "${versions}" | sed 's/^/  /'

pinned_numpy="$(grep -E '^numpy==' "${lab_dir}/requirements/requirements.txt" | cut -d= -f3)"
installed_numpy="$("${python_bin}" -c "from importlib.metadata import version; print(version('numpy'))")"
check_eq "installed numpy matches requirements.txt" "${pinned_numpy}" "${installed_numpy}"

major="$("${python_bin}" -c "import numpy; print(numpy.__version__.split('.')[0])")"
check_eq "numpy is version 2 or later (numpy.random.default_rng and the 2.x repr)" "2" "${major}"

# --------------------------------------------------------------------------
echo
echo "2. Every reference script runs and every assertion inside it holds"
# --------------------------------------------------------------------------

for script in 01_the_length_confound 02_dot_product_and_sign \
              03_from_scratch_vs_numpy 04_same_ranking_on_the_sphere \
              05_not_a_metric 06_semantic_search 07_curse_of_dimensionality; do
  out="$(cd "${lab_dir}/examples" && "${python_bin}" "${script}.py" 2>&1)"
  status=$?
  if [ "${status}" -ne 0 ]; then
    check "${script}.py exits 0" "no"
    echo "${out}" | tail -5 | sed 's/^/      /'
  else
    check "${script}.py exits 0" "yes"
  fi
  case "${out}" in
    *"${script}.py: every assertion held."*)
      check "${script}.py reports every assertion held" "yes" ;;
    *) check "${script}.py reports every assertion held" "no" ;;
  esac
done

# --------------------------------------------------------------------------
echo
echo "3. The reference pytest suite: real values, real rankings"
# --------------------------------------------------------------------------

ref_out="$(cd "${lab_dir}" && "${pytest_bin}" examples -q -p no:cacheprovider 2>&1)"
ref_status=$?
echo "${ref_out}" | tail -3 | sed 's/^/  /'
if [ "${ref_status}" -eq 0 ]; then
  check "pytest examples exits 0" "yes"
else
  check "pytest examples exits 0" "no"
fi
case "${ref_out}" in
  *" failed"*) check "no test in the reference suite failed" "no" ;;
  *)           check "no test in the reference suite failed" "yes" ;;
esac
ref_passed="$(printf '%s\n' "${ref_out}" | grep -o '[0-9][0-9]* passed' | head -1 | cut -d' ' -f1)"
if [ "${ref_passed:-0}" -ge 70 ]; then
  check "the reference suite ran at least 70 tests (ran ${ref_passed})" "yes"
else
  check "the reference suite ran at least 70 tests (ran ${ref_passed:-0})" "no"
fi

# --------------------------------------------------------------------------
echo
echo "4. The starter suite skips unattempted work instead of failing it"
# --------------------------------------------------------------------------

start_out="$(cd "${lab_dir}" && "${pytest_bin}" starter -q -p no:cacheprovider 2>&1)"
start_status=$?
echo "${start_out}" | tail -3 | sed 's/^/  /'
if [ "${start_status}" -eq 0 ]; then
  check "pytest starter exits 0 on an untouched checkout" "yes"
else
  check "pytest starter exits 0 on an untouched checkout" "no"
fi
case "${start_out}" in
  *" failed"*) check "the starter suite reports no failures" "no" ;;
  *)           check "the starter suite reports no failures" "yes" ;;
esac
case "${start_out}" in
  *skipped*) check "unwritten exercises are reported as skipped, not passed" "yes" ;;
  *) check "unwritten exercises are reported as skipped, not passed" "no" ;;
esac

# The import guard. Both directories contain a module called `similarity`, and
# pytest imports test files by putting their directory on sys.path — so
# collecting both suites at once would otherwise let the starter tests import
# the REFERENCE solution and report unwritten exercises as passing. Each
# directory's conftest.py prevents that. This check proves it still does:
# across both suites, the skip count must be unchanged.
both_out="$(cd "${lab_dir}" && "${pytest_bin}" -q -p no:cacheprovider 2>&1)"
start_skipped="$(printf '%s\n' "${start_out}" | grep -o '[0-9][0-9]* skipped' | head -1 | cut -d' ' -f1)"
both_skipped="$(printf '%s\n' "${both_out}" | grep -o '[0-9][0-9]* skipped' | head -1 | cut -d' ' -f1)"
check_eq "collecting both suites at once does not turn skips into passes" \
  "${start_skipped:-none}" "${both_skipped:-none}"

# --------------------------------------------------------------------------
echo
echo "5. The lesson's claims, checked one value at a time"
# --------------------------------------------------------------------------

facts="$(cd "${lab_dir}/examples" && "${python_bin}" - <<'PY'
import math

import numpy as np

from catalogue import CATALOGUE, LONG_ROAST_CHICKEN, QUERIES, TRIANGLE_A, TRIANGLE_B, TRIANGLE_C
from similarity import (
    angle_degrees,
    cosine_distance,
    cosine_similarity,
    dot,
    euclidean_distance,
    normalise,
    normalise_all,
    rank_by_cosine,
    rank_by_euclidean,
)

short = CATALOGUE["roast-chicken"]
rival = CATALOGUE["race-day-nutrition"]

# The confound.
print("dist_to_doubled", f"{euclidean_distance(short, LONG_ROAST_CHICKEN):.4f}")
print("dist_to_rival", f"{euclidean_distance(short, rival):.4f}")
print("confound", euclidean_distance(short, LONG_ROAST_CHICKEN) > euclidean_distance(short, rival))
print("cos_to_doubled", f"{cosine_similarity(short, LONG_ROAST_CHICKEN):.10f}")

# Agreement with NumPy across every pair.
worst = 0.0
for a in CATALOGUE.values():
    for b in CATALOGUE.values():
        theirs = float(np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b)))
        worst = max(worst, abs(cosine_similarity(a, b) - theirs))
print("numpy_agreement", worst < 1e-12)

# The signs.
print("signs", int(dot([3, 0], [6, 0])), int(dot([3, 0], [0, 5])), int(dot([3, 0], [-6, 0])))
print("angles", f"{angle_degrees([3, 0], [1, 1]):.2f}", f"{angle_degrees([3, 0], [-2, 2]):.2f}")

# The ranking equivalence.
units = normalise_all(CATALOGUE)
q = units["roast-chicken"]
by_cos = [k for k, _ in rank_by_cosine(q, units)]
by_euc = [k for k, _ in rank_by_euclidean(q, units)]
print("normalised_orders_match", by_cos == by_euc)

raw = dict(CATALOGUE)
raw["roast-chicken (2x)"] = LONG_ROAST_CHICKEN
raw_cos = [k for k, _ in rank_by_cosine(short, raw)]
raw_euc = [k for k, _ in rank_by_euclidean(short, raw)]
print("raw_orders_match", raw_cos == raw_euc)

# The identity behind it.
u, v = units["roast-chicken"], units["marathon-plan"]
print("sphere_identity", abs(euclidean_distance(u, v) - math.sqrt(2 - 2 * cosine_similarity(u, v))) < 1e-9)

# The triangle inequality.
ab = cosine_distance(TRIANGLE_A, TRIANGLE_B)
bc = cosine_distance(TRIANGLE_B, TRIANGLE_C)
ac = cosine_distance(TRIANGLE_A, TRIANGLE_C)
print("triangle_cosine_fails", ac > ab + bc, f"{ab + bc:.6f}", f"{ac:.6f}")
ea = euclidean_distance(TRIANGLE_A, TRIANGLE_B) + euclidean_distance(TRIANGLE_B, TRIANGLE_C)
print("triangle_euclid_holds", euclidean_distance(TRIANGLE_A, TRIANGLE_C) <= ea + 1e-12)

# The search.
r1 = rank_by_cosine(QUERIES["roast it"], CATALOGUE)
r2 = rank_by_cosine(QUERIES["training for a race and what to eat"], CATALOGUE)
print("search_top1", r1[0][0], f"{r1[0][1]:.6f}")
print("search_top2", r2[0][0], f"{r2[0][1]:.6f}")
print("euclid_top1", rank_by_euclidean(QUERIES["roast it"], CATALOGUE)[0][0])
scaled = [100 * x for x in QUERIES["roast it"]]
print("scale_invariant", [k for k, _ in rank_by_cosine(scaled, CATALOGUE)] == [k for k, _ in r1])

# The zero vector is refused rather than returning NaN.
try:
    cosine_similarity([0, 0, 0, 0], short)
except ValueError:
    print("zero_vector", "ValueError")
else:
    print("zero_vector", "NOTHING_RAISED")

# The clamp: at least one article rounds above 1.0 through the naive formula.
above = 0
for vec in CATALOGUE.values():
    length = math.sqrt(sum(x * x for x in vec))
    if sum(x * y for x, y in zip(vec, vec)) / (length * length) > 1.0:
        above += 1
print("rounds_above_one", above >= 1, all(cosine_similarity(v, v) <= 1.0 for v in CATALOGUE.values()))

# The curse, seeded so it is reproducible.
rng = np.random.default_rng(103)
means = []
for dimension in (2, 32, 512, 8192):
    a = rng.standard_normal((2000, dimension))
    b = rng.standard_normal((2000, dimension))
    num = np.einsum("ij,ij->i", a, b)
    den = np.linalg.norm(a, axis=1) * np.linalg.norm(b, axis=1)
    means.append(float(np.mean(np.abs(num / den))))
print("curse_monotone", all(y < x for x, y in zip(means, means[1:])))
print("curse_values", " ".join(f"{m:.4f}" for m in means))
PY
)"

get() { printf '%s\n' "${facts}" | grep "^$1 " | cut -d' ' -f2-; }

check_eq "the doubled copy is 9.0554 away, which is the article's own length" \
  "9.0554" "$(get dist_to_doubled)"
check_eq "race-day-nutrition is only 8.0623 away" "8.0623" "$(get dist_to_rival)"
check_eq "so Euclidean puts the doubled copy FURTHER than a different article" \
  "True" "$(get confound)"
check_eq "cosine calls the doubled copy identical" "1.0000000000" "$(get cos_to_doubled)"
check_eq "every from-scratch cosine agrees with NumPy inside 1e-12" \
  "True" "$(get numpy_agreement)"
check_eq "the three sign cases give 18, 0 and -18" "18 0 -18" "$(get signs)"
check_eq "the 45 and 135 degree cases measure 45.00 and 135.00" \
  "45.00 135.00" "$(get angles)"
# Section 6 re-runs this script with D103_SELF_TEST=1, which swaps ONE
# expectation below for a deliberately wrong one. That is how the harness
# proves it can fail rather than merely asserting that it could.
expected_normalised="True"
if [ -n "${D103_SELF_TEST:-}" ]; then
  expected_normalised="False"   # deliberately wrong here
fi
check_eq "on normalised vectors the two rankings are identical" \
  "${expected_normalised}" "$(get normalised_orders_match)"
check_eq "on raw vectors with the doubled copy they are NOT" \
  "False" "$(get raw_orders_match)"
check_eq "the unit-sphere identity sqrt(2 - 2cos) matches the measured distance" \
  "True" "$(get sphere_identity)"
check_eq "cosine distance fails the triangle inequality (0.585786 < 1.000000)" \
  "True 0.585786 1.000000" "$(get triangle_cosine_fails)"
check_eq "Euclidean distance holds it on the same triple" \
  "True" "$(get triangle_euclid_holds)"
check_eq "the cooking note retrieves roast-chicken" \
  "roast-chicken 0.993884" "$(get search_top1)"
check_eq "the training query retrieves race-day-nutrition" \
  "race-day-nutrition 0.903482" "$(get search_top2)"
check_eq "raw Euclidean gets the cooking note wrong" \
  "slow-cooker-stew" "$(get euclid_top1)"
check_eq "scaling the query by 100 changes nothing" "True" "$(get scale_invariant)"
check_eq "the zero vector raises rather than returning NaN" \
  "ValueError" "$(get zero_vector)"
check_eq "the naive formula rounds above 1.0 and the clamp catches it" \
  "True True" "$(get rounds_above_one)"
check_eq "mean absolute cosine falls at every step up in dimension" \
  "True" "$(get curse_monotone)"
check_eq "and the measured values are reproducible from seed 103" \
  "0.6435 0.1440 0.0353 0.0088" "$(get curse_values)"

# --------------------------------------------------------------------------
echo
echo "6. The harness can actually fail"
# --------------------------------------------------------------------------

# A green test suite proves nothing until you have watched it go red. This
# section re-runs the whole script with one expectation deliberately swapped
# for the WRONG answer, and asserts that the re-run reports the failure and
# exits non-zero. If this section passes, section 5 is not decorative.
if [ -z "${D103_SELF_TEST:-}" ]; then
  self_out="$(D103_SELF_TEST=1 bash "${BASH_SOURCE[0]}" 2>&1)"
  self_status=$?
  if [ "${self_status}" -ne 0 ]; then
    check "a deliberately wrong expectation makes the harness exit non-zero (${self_status})" "yes"
  else
    check "a deliberately wrong expectation makes the harness exit non-zero" "no"
  fi
  case "${self_out}" in
    *"FAIL: on normalised vectors the two rankings are identical"*)
      check "the failing check is named in the output with both values" "yes" ;;
    *) check "the failing check is named in the output with both values" "no" ;;
  esac
  case "${self_out}" in
    *", 1 failure(s)."*)
      check "the summary line counts exactly one failure" "yes" ;;
    *) check "the summary line counts exactly one failure" "no" ;;
  esac
else
  echo "  (self-test run: section 6 does not recurse)"
fi

# --------------------------------------------------------------------------
echo
echo "7. Nothing was left behind"
# --------------------------------------------------------------------------

# `.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__ directory anywhere under the lab after a full run" "no"
else
  check "no __pycache__ directory anywhere under the lab after a full run" "yes"
fi

if find "${lab_dir}" -name '.venv' -prune -o -type d -name '.pytest_cache' -print -quit 2>/dev/null | grep -q .; then
  check "no .pytest_cache directory left under the lab" "no"
else
  check "no .pytest_cache directory left under the lab" "yes"
fi

if grep -rqE 'urlopen|requests\.|socket\.|http://|https://' \
     "${lab_dir}/examples" "${lab_dir}/starter" 2>/dev/null; then
  check "no lab source opens a network connection" "no"
else
  check "no lab source opens a network connection" "yes"
fi

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