#!/usr/bin/env python3
"""
W6 — The popularity trap: NDCG rises while the product gets worse.  (~40 min)

Miniature of P08. Build four recommenders over a Zipf-distributed catalogue, score
them on accuracy AND on catalogue health, and watch the ranking flip depending on
which metric you report.
"""
import math, random
from collections import Counter
import sys, os
sys.path.insert(0, os.path.join(os.path.dirname(__file__), "..", "tools"))
from metrics import ndcg_at_k, recall_at_k, coverage, novelty, gini

rng = random.Random(11)
N_ITEMS, N_USERS, K = 2000, 1500, 10
ALPHA = 1.0                                    # Zipf exponent of true popularity

# ---- a world where popularity is real but personal taste also exists ----
pop_w = [1 / (r + 1) ** ALPHA for r in range(N_ITEMS)]
tot = sum(pop_w)
pop_p = [w / tot for w in pop_w]
topic = [rng.randrange(8) for _ in range(N_ITEMS)]     # 8 topics
recency = [rng.random() for _ in range(N_ITEMS)]

users = []
for u in range(N_USERS):
    fav = rng.randrange(8)
    liked = set()
    while len(liked) < 12:
        # a user engages with a MIX: mostly their topic, partly whatever is popular
        if rng.random() < 0.65:
            cands = [i for i in range(N_ITEMS) if topic[i] == fav]
            liked.add(rng.choice(cands))
        else:
            liked.add(rng.choices(range(N_ITEMS), weights=pop_p)[0])
    users.append((fav, liked))

def evaluate(name, recommend):
    recs, nd, rc = [], [], []
    for fav, liked in users:
        r = recommend(fav, liked)[:K]
        recs.append(r)
        gains = {i: 1.0 for i in liked}
        nd.append(ndcg_at_k(r, gains, K))
        rc.append(recall_at_k(r, liked, K))
    pc = Counter()
    for r in recs: pc.update(r)
    return dict(name=name,
                ndcg=sum(nd) / len(nd), recall=sum(rc) / len(rc),
                cov=coverage(recs, N_ITEMS), gini=gini(recs),
                nov=novelty(recs, pc))

by_pop = sorted(range(N_ITEMS), key=lambda i: -pop_p[i])

results = [
    evaluate("random",       lambda f, l: rng.sample(range(N_ITEMS), K)),
    evaluate("bestseller",   lambda f, l: by_pop[:K]),
    evaluate("topic-only",   lambda f, l: sorted([i for i in range(N_ITEMS) if topic[i]==f],
                                                 key=lambda i: -recency[i])[:K]),
    evaluate("topic+pop",    lambda f, l: sorted([i for i in range(N_ITEMS) if topic[i]==f],
                                                 key=lambda i: -pop_p[i])[:K]),
]

print(f"{N_USERS} users, {N_ITEMS} items, Zipf(alpha={ALPHA}) popularity, k={K}\n")
print(f"{'recommender':<14}{'NDCG@10':>9}{'recall@10':>11}{'coverage':>10}{'Gini':>8}{'novelty':>9}")
print("-" * 61)
for r in results:
    print(f"{r['name']:<14}{r['ndcg']:>9.4f}{r['recall']:>11.4f}"
          f"{r['cov']:>10.4f}{r['gini']:>8.3f}{r['nov']:>9.2f}")

best_acc = max(results, key=lambda r: r["ndcg"])
best_cov = max(results, key=lambda r: r["cov"])
print(f"\nBest by NDCG:     {best_acc['name']}  (coverage {best_acc['cov']:.4f})")
print(f"Best by coverage: {best_cov['name']}  (NDCG {best_cov['ndcg']:.4f})")

bs = next(r for r in results if r["name"]=="bestseller")
tp = next(r for r in results if r["name"]=="topic+pop")
to = next(r for r in results if r["name"]=="topic-only")
rd = next(r for r in results if r["name"]=="random")

print("\nTHE TRAP, concretely.")
print(f"  'bestseller' wins NDCG outright: {bs['ndcg']:.4f} vs {tp['ndcg']:.4f} for the")
print(f"  best personalised recommender -- {bs['ndcg']/tp['ndcg']:.1f}x better on the metric")
print(f"  most teams put on the dashboard. It achieves this while showing the SAME")
print(f"  {K} items to all {N_USERS} users: coverage {bs['cov']:.4f} ({bs['cov']*N_ITEMS:.0f} of "
      f"{N_ITEMS} items),")
print(f"  novelty {bs['nov']:.2f} bits against {tp['nov']:.2f}.")
print(f"\n  Ship it and the accuracy dashboard is green. The catalogue is dead.")

print("\nA SECOND, subtler observation from the same table.")
print(f"  'topic-only' and 'topic+pop' have IDENTICAL coverage ({to['cov']:.4f}), Gini")
print(f"  ({to['gini']:.3f}) and novelty ({to['nov']:.2f}) despite NDCG differing "
      f"{to['ndcg']:.4f} -> {tp['ndcg']:.4f}")
print(f"  ({(tp['ndcg']/to['ndcg']-1)*100:+.0f}%). They are permutations of the same "
      f"candidate pool, and")
print("  a permutation cannot change which items were shown. Catalogue metrics are")
print("  blind to RANKING; they only see RETRIEVAL. So the popularity trap is sprung")
print("  at the retrieval stage, not the ranking stage -- which is where to look for it.")

print("\nAnd the control that makes the frontier legible:")
print(f"  'random' has near-perfect coverage ({rd['cov']:.4f}) and useless accuracy")
print(f"  ({rd['ndcg']:.4f}). Coverage alone is not a goal either.")
print("\nReport the whole suite for every configuration. With NDCG alone, the")
print("bestseller list is the best system in this table.")