A simple baseline for search: represent texts by their word counts and rank documents by cosine similarity to the query.
What to build
A program that ranks documents against a query by the cosine similarity of their word-count vectors.
Requirements
- Each text is a vector of word counts; compare the query with each document by cosine similarity (0 if they share no words).
- Print the k best as
D: S, D the document number from 1 and S to 3 decimal places, highest first; equal scores by document number.
Input
Line 1: n. Then n documents, one per line. Then the query, then k.
Output
k lines.
Constraints
1 ≤ k ≤ n ≤ 1000; texts are lower-case words.
Example
Input:
3
the cat sat
the dog barked
a cat and a dog
cat dog
2
Output:
3: 0.535
1: 0.408
Why it works
Counting words turns texts into vectors, and cosine similarity rewards shared words while ignoring how long each text is.
Examples
3 the cat sat the dog barked a cat and a dog cat dog 2
3: 0.535 1: 0.408
2 x y y 2
2: 1.000 1: 0.000
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Turn each text into a dictionary of word counts.
Hint 2
Cosine similarity: the sum over shared words of count × count, divided by the two vectors' lengths.
Hint 3
Sort by score from highest to lowest, then by document number.
Solution
Show one correct solution (try it yourself first)
import math
n = int(input())
docs = [input().split() for _ in range(n)]
query = input().split()
k = int(input())
def counts(words):
c = {}
for w in words:
c[w] = c.get(w, 0) + 1
return c
def cosine(a, b):
dot = sum(a[w] * b.get(w, 0) for w in a)
return dot / (math.sqrt(sum(v * v for v in a.values())) * math.sqrt(sum(v * v for v in b.values())))
q = counts(query)
scores = sorted(((-cosine(q, counts(d)), i + 1) for i, d in enumerate(docs)))
for s, i in scores[:k]:
print(f"{i}: {-s:.3f}")