Generate text from next-token probabilities in two ways and compare them.
What to build
A program that decodes the most likely sequence from a next-token table with greedy search and with beam search.
Requirements
- The table gives, for each token, the probability of each possible next token. Generation starts after the token START and ends at END or after M tokens. A sequence's probability is the product of its steps' probabilities. Beam search keeps B candidates per step as described in the hints; when no unfinished candidates remain or M tokens have been generated, the answer is the most probable kept sequence (ties: alphabetical).
- Print
greedy: TOKENS (P)andbeam: TOKENS (P), tokens without START and probabilities with four decimal places.
Input
Line 1: B and M. Line 2: r. Then r lines TOKEN NEXT1 P1 NEXT2 P2 ….
Output
Two lines.
Constraints
B ≤ 10; M ≤ 20; at most 50 tokens.
Example
Input:
2 5
6
START a 0.6 b 0.4
a c 0.5 d 0.5
b e 0.9 c 0.1
c END 1.0
d END 1.0
e END 1.0
Output:
greedy: a c END (0.3000)
beam: b e END (0.3600)
Why it works
Greedy search commits to the best single step and can miss a better whole sequence; beam search keeps several partial sequences alive, so a weaker first step that leads to stronger continuations can still win.
Examples
2 5 6 START a 0.6 b 0.4 a c 0.5 d 0.5 b e 0.9 c 0.1 c END 1.0 d END 1.0 e END 1.0
greedy: a c END (0.3000) beam: b e END (0.3600)
1 5 6 START a 0.6 b 0.4 a c 0.5 d 0.5 b e 0.9 c 0.1 c END 1.0 d END 1.0 e END 1.0
greedy: a c END (0.3000) beam: a c END (0.3000)
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Greedy: from START, repeatedly take the most likely next token (ties: alphabetical) until END or M tokens.
Hint 2
Beam: at each step extend every unfinished sequence by every possible next token, rank all candidates by probability (ties: by token sequence, alphabetically), keep the best B, and set aside those ending in END.
Solution
Show one correct solution (try it yourself first)
B, M = map(int, input().split())
table = {}
for _ in range(int(input())):
token, *rest = input().split()
table[token] = {rest[i]: float(rest[i + 1]) for i in range(0, len(rest), 2)}
seq, prob, word = [], 1.0, "START"
while len(seq) < M and table.get(word):
word, p = min(table[word].items(), key=lambda item: (-item[1], item[0]))
seq.append(word)
prob *= p
if word == "END":
break
beams, finished = [((), 1.0)], []
for _ in range(M):
candidates = []
for s, p in beams:
last = s[-1] if s else "START"
for token, q in table.get(last, {}).items():
candidates.append((s + (token,), p * q))
if not candidates:
break
candidates.sort(key=lambda c: (-c[1], c[0]))
kept = candidates[:B]
finished += [c for c in kept if c[0][-1] == "END"]
beams = [c for c in kept if c[0][-1] != "END"]
if not beams:
break
best = min(finished + beams, key=lambda c: (-c[1], c[0]))
print(f"greedy: {' '.join(seq)} ({prob:.4f})")
print(f"beam: {' '.join(best[0])} ({best[1]:.4f})")