# Words by the Numbers 5, Exercise 2: how often does each order have a real choice?
import random, re
from collections import defaultdict
from pydoc_data.topics import topics

def tokens(text):
    return re.findall(r"[a-z]+(?:'[a-z]+)?", text.lower())

docs = [tokens(d) for d in topics.values()]

def build(order):
    chain = defaultdict(list)
    for w in docs:
        for i in range(len(w) - order):
            chain[tuple(w[i:i + order])].append(w[i + order])
    return chain

for order in (1, 2, 3):
    chain = build(order)
    rng = random.Random(5)
    keys = list(chain)
    state = rng.choice(keys)
    steps = jumps = choices = 0
    while steps < 2000:
        if state not in chain:
            jumps += 1
            state = rng.choice(keys)
            continue
        options = chain[state]
        choices += len(set(options)) > 1
        word = rng.choice(options)
        state = state[1:] + (word,)
        steps += 1
    print(f"order {order}: dead-end jumps {jumps:3d} | steps with a real choice {choices / steps:4.0%} | mean followers per context {sum(map(len, chain.values())) / len(chain):.2f}")

# Output when run (Python 3.14; the documentation-text figures depend on the Python version):
# order 1: dead-end jumps   0 | steps with a real choice  97% | mean followers per context 22.65
# order 2: dead-end jumps   3 | steps with a real choice  61% | mean followers per context 2.71
# order 3: dead-end jumps   1 | steps with a real choice  24% | mean followers per context 1.58