Score a retriever's ranking when its scores tie

Your agent's retriever scores documents for each query, and the eval grades its ranking with NDCG at k (normalized discounted cumulative gain, defined below). The scores are rounded, so ties are common. The old harness broke ties by input order, so a retriever looked better or worse depending on how the documents happened to arrive. The fix is to grade the expected NDCG over every order the tied documents could take.

Write expected_ndcg(queries, k) that returns the mean of that score over all queries.

• queries: a list of queries. Each query is a list of documents [score, gain]: the retriever's score, a whole number, and how relevant the document really is, a whole number, 0 or more. A query has at most 200 documents.
• k: a whole number, at least 1.
• Return a float. The tests accept any value within 0.000001 of the exact one.

Rules:

1. The ranking sorts a query's documents by score, highest first. Documents with equal scores come in random order, and every order of them is equally likely.
2. A document at position p, counting from 1, adds gain / log2(p + 1) when p <= k and nothing when p > k. The DCG of a ranking is the total over its documents.
3. The ideal DCG is the DCG of the same documents sorted by gain, highest first. NDCG is DCG divided by the ideal DCG. A query whose ideal DCG is 0 scores 0.
4. A query's score is its expected NDCG under rule 1. Return the mean over all queries, or 0.0 when there are none.