Generate text the way a Markov model does: start from a word and keep sampling the next one.
What to build
A program that learns a bigram model and generates text by sampling, using given random numbers.
Requirements
- The text starts with the start word, which counts towards the length.
- To add a word: list the current word's successors alphabetically with their probabilities, take the next draw r, and choose the first successor whose running total is greater than r.
- Stop after adding
., when the current word has no successors, or when the text has n words. Print the text.
Input
Line 1: the training text. Line 2: the start word and n. Line 3: the draws (there are always enough).
Output
One line.
Constraints
1 to 10,000 training words; 1 ≤ n ≤ 100.
Example
Input:
the cat sat on the mat . the cat ate the fish . the dog sat on the log .
the 8
0.1 0.9 0.3 0.5 0.6 0.2 0.95
Output:
the cat sat on the fish .
Why it works
Each step samples from the bigram distribution of the current word, so the text follows pairs seen in training while the random draws decide between alternatives.
Examples
the cat sat on the mat . the cat ate the fish . the dog sat on the log . the 8 0.1 0.9 0.3 0.5 0.6 0.2 0.95
the cat sat on the fish .
a b a 5 0.5 0.5
a b
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Learn the next-word counts first; for each word, list its successors in alphabetical order.
Hint 2
For each new word, take the next draw r and choose the first successor whose running total of probabilities is greater than r.
Hint 3
Stop at `.`, at a word with no successors, or when the text has n words.
Solution
Show one correct solution (try it yourself first)
words = input().split()
start, n = input().split()
n = int(n)
draws = list(map(float, input().split()))
following = {}
for a, b in zip(words, words[1:]):
following.setdefault(a, {})
following[a][b] = following[a].get(b, 0) + 1
text = [start]
used = 0
while len(text) < n and text[-1] != "." and text[-1] in following:
options = following[text[-1]]
total = sum(options.values())
r = draws[used]
used += 1
running = 0.0
pick = sorted(options)[-1]
for w in sorted(options):
running += options[w] / total
if r < running:
pick = w
break
text.append(pick)
print(" ".join(text))