Exercise ex-minhash — MinHash: estimate Jaccard similarity without ever computing it

What you're building

• shingles(text, k=5) -> set[str] — the set of distinct, overlapping character k-grams of text (not word n-grams: "the quick brown" shingled by word would treat a one-letter typo as a totally different token, exactly the failure MinHash is here to survive). len(text) < k returns {text} as a single shingle.
• minhash(shingle_set, n_hashes, seed) -> np.ndarray — a length- n_hashes signature. Seed a random-number generator once from seed, draw n_hashes distinct hash functions from it (one independent permutation per output position, not one function reused n_hashes times), and for each hash function record the minimum value it produces over every shingle in shingle_set. Two documents that share more shingles are more likely to share the shingle that minimizes any one given hash function — that single fact is the entire algorithm.
• jaccard_estimate(sig_a, sig_b) -> float — the fraction of positions where the two equal-length signatures agree. That fraction's expected value is the true Jaccard similarity of the two shingle sets; more hash functions narrow the estimate around it.
• find_contaminated(train, evalset, threshold=0.8) -> list[tuple[int, int]] — shingle and sign every document in both lists, and return every (train_idx, eval_idx) pair whose estimate is strictly greater than threshold — a pair sitting exactly on the line is not flagged.

Check 3 quotes a real pair of near-duplicate sentences and their exact true Jaccard similarity (55 shared 5-grams over 75 total, computed directly from the sets, no hashing involved) so you have a ground truth to hold the estimate to. Check 4 averages the estimate's error over 20 seeds, because a single seed can get lucky with 8 hashes: the claim "more hashes → less error" is about the mean, and it holds for any correct hash scheme, not just the one the hint suggests. Check 7 signs a shingle set 50 different ways and demands the 50 outputs are not all the same number — the single most common wrong minhash draws one hash function and copies it into every slot.

If you get stuck

• shingles — {text[i:i+k] for i in range(len(text) - k + 1)}. It is a set, so a repeated substring ("banana"'s 3-grams "ban", "ana", "nan", "ana" again) collapses to 3 distinct entries, not 4.
• minhash, the hash functions — you need n_hashes functions that behave independently, not one. The standard trick: draw n_hashes pairs (a_i, b_i) from np.random.default_rng(seed) and hash a shingle s under function i as (a_i * h(s) + b_i) % PRIME, where h(s) is any deterministic integer hash of the string (Python's built-in hash() is randomized per-process by default — use hashlib.md5(s.encode()).hexdigest() turned into an int instead, or the result changes every run) and PRIME is a large prime, e.g. 2**61 - 1. Use plain Python ints for the multiply-mod, not a fixed-width NumPy dtype — a_i * h(s) overflows a 64-bit integer long before the modulus brings it back down.
• minhash, the minimum — for each of the n_hashes functions, track the smallest value seen across every shingle in the set, starting from +inf (or PRIME). Build the final np.ndarray once, at the end, from a plain Python list — do not try to vectorize the multiply-mod across shingles with NumPy's fixed-width integers for the same overflow reason.
• jaccard_estimate — float(np.mean(sig_a == sig_b)). That is the whole function; the cleverness already happened inside minhash.
• find_contaminated — sign every train doc once and every eval doc once (don't re-shingle an eval doc once per train doc), then compare every pair. The trap that fails "nothing else": using >= instead of > against threshold flags a pair that lands exactly on the boundary — the check plants one on purpose (an exact copy scores exactly 1.0, and threshold=1.0 must not flag it).