Score documents by shared words

The simplest retriever: count how many different query words each document contains.

What to build

A program that scores documents by the number of different query words they contain and picks the best.

Requirements

  • Print D: S for every document, D counting from 1.
  • Then print best D, the document with the highest score (the lowest number on a tie).

Input

Line 1: n. Then n documents. Then the query. All lower-case words.

Output

n + 1 lines.

Constraints

1 ≤ n ≤ 1000.

Example

Input:

3
the library opens at nine
the cafe opens at eight
books can be renewed online
when does the library open

Output:

1: 2
2: 1
3: 0
best 1

Why it works

Each query word found in a document is evidence that the document is about the question, and counting different words keeps a repeated word from counting twice.

Examples

Example 1 · Input
3
the library opens at nine
the cafe opens at eight
books can be renewed online
when does the library open
Expected output
1: 2
2: 1
3: 0
best 1
Example 2 · Input
2
a
b
b
Expected output
1: 0
2: 1
best 2

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Take the set of different words in the query.

Hint 2

A document's score is how many of those words appear in it.

Solution

Show one correct solution (try it yourself first)
n = int(input())
docs = [set(input().split()) for _ in range(n)]
query = set(input().split())
scores = [len(query & d) for d in docs]
for i, s in enumerate(scores):
    print(f"{i + 1}: {s}")
print(f"best {scores.index(max(scores)) + 1}")

Lesson: Retrieval-augmented generation (RAG) →