import random

# Step 1: Initialize a list of words
word_list = [
    "the", "cat", "in", "the", "hat", "the", "cat", "on", "the", "mat",
    "the", "dog", "and", "the", "cat", "the", "cat", "and", "the", "hat"
]

# Step 2: Calculate the transition probabilities
transitions = {}

# Populate the transitions dictionary with counts
for i in range(len(word_list) - 1):
    current_word = word_list[i]
    next_word = word_list[i + 1]
    if current_word not in transitions:
        transitions[current_word] = {}
    if next_word not in transitions[current_word]:
        transitions[current_word][next_word] = 0
    transitions[current_word][next_word] += 1

# Convert counts to probabilities
for current_word, next_words in transitions.items():
    total = sum(next_words.values())
    for next_word in next_words:
        transitions[current_word][next_word] /= total

# Step 3: Implement the function to generate the next word
def next_word(current_word):
    if current_word not in transitions:
        return random.choice(list(transitions.keys()))
    probabilities = transitions[current_word]
    next_words = list(probabilities.keys())
    probabilities = list(probabilities.values())
    return random.choices(next_words, probabilities)[0]

# Step 4: Generate a sequence of words
def generate_sequence(start_word, length):
    sequence = [start_word]
    current_word = start_word
    for _ in range(length - 1):
        current_word = next_word(current_word)
        sequence.append(current_word)
    return sequence

# Example usage
start_word = "the"
length = 20
sequence = generate_sequence(start_word, length)
print("Generated sequence:", sequence)