Implement the token filters an LLM uses before it picks its next word.
What to build
A program that prints the greedy choice and the renormalized top-k and top-p sets of a next-token distribution.
Requirements
- Order the tokens by probability, highest first; equal probabilities keep their input order.
- Print
greedy: token(the first in that order), thentop-k: ...with the first k tokens, thentop-p P: ...with the shortest prefix of the order whose probabilities add up to at least P (P as written in the input). - In both lists, print each kept token followed by its probability divided by the kept total, to three decimal places, in that order.
Input
Line 1: tokens. Line 2: their probabilities (adding up to 1). Line 3: k. Line 4: p.
Output
Three lines.
Constraints
At most 1,000 tokens; 1 ≤ k ≤ number of tokens; 0 < p ≤ 1.
Example
Input:
mat floor sofa moon
0.5 0.2 0.2 0.1
2
0.8
Output:
greedy: mat
top-2: mat 0.714 floor 0.286
top-p 0.8: mat 0.556 floor 0.222 sofa 0.222
Why it works
Both filters cut off the unlikely tail of the distribution; top-k keeps a fixed number of tokens, while top-p keeps however many are needed to cover p of the probability, and renormalizing turns the kept part into a distribution again.
Examples
mat floor sofa moon 0.5 0.2 0.2 0.1 2 0.8
greedy: mat top-2: mat 0.714 floor 0.286 top-p 0.8: mat 0.556 floor 0.222 sofa 0.222
a b c 0.2 0.7 0.1 1 0.5
greedy: b top-1: b 1.000 top-p 0.5: b 1.000
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
`sorted(range(n), key=lambda i: -probs[i])` orders token positions by probability and keeps input order for ties.
Hint 2
For top-p, add tokens in that order until the running total reaches p; compare with a small tolerance, `total >= p - 1e-9`.
Solution
Show one correct solution (try it yourself first)
tokens = input().split()
probs = [float(x) for x in input().split()]
k = int(input())
p_text = input().strip()
p = float(p_text)
order = sorted(range(len(tokens)), key=lambda i: -probs[i])
def show(kept):
total = sum(probs[i] for i in kept)
return " ".join(f"{tokens[i]} {probs[i] / total:.3f}" for i in kept)
print("greedy:", tokens[order[0]])
print(f"top-{k}:", show(order[:k]))
kept, running = [], 0.0
for i in order:
kept.append(i)
running += probs[i]
if running >= p - 1e-9:
break
print(f"top-p {p_text}:", show(kept))