Count word pairs

Training a bigram model is counting neighbouring word pairs. Count them.

What to build

A program that counts every pair of neighbouring words in a text.

Requirements

  • Print each different pair once as FIRST SECOND COUNT, sorted by the first word and then the second.
  • If the text has fewer than two words, print no pairs.

Input

One line of words separated by spaces.

Output

One line per pair.

Constraints

1 to 10,000 words.

Example

Input:

the cat sat on the mat

Output:

cat sat 1
on the 1
sat on 1
the cat 1
the mat 1

Why it works

Each count says how often the second word followed the first, which is exactly what the model needs to predict next words.

Examples

Example 1 · Input
the cat sat on the mat
Expected output
cat sat 1
on the 1
sat on 1
the cat 1
the mat 1
Example 2 · Input
a a a
Expected output
a a 2

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

Hints

Hint 1

Pair each word with the next one using `zip(words, words[1:])`.

Hint 2

Sort the pairs alphabetically by first word, then second word.

Solution

Show one correct solution (try it yourself first)
words = input().split()
counts = {}
for pair in zip(words, words[1:]):
    counts[pair] = counts.get(pair, 0) + 1
if not counts:
    print("no pairs")
for (a, b) in sorted(counts):
    print(a, b, counts[(a, b)])

Lesson: Generating text with a Markov model →