import random
from collections import defaultdict

def build_bigram_model(text):
    """Build a bigram language model from text"""
    words = text.lower().split()
    model = defaultdict(list)
    
    for i in range(len(words) - 1):
        model[words[i]].append(words[i + 1])
    
    return model

def generate_text(model, start_word, length=10):
    """Generate text using the bigram model"""
    current = start_word
    output = [current]
    
    for _ in range(length - 1):
        if current not in model:
            break
        next_word = random.choice(model[current])
        output.append(next_word)
        current = next_word
    
    return " ".join(output)

# Train on example text
corpus = """
the cat sat on the mat the cat ate the fish
the dog sat on the floor the dog ate the bone
cats love fish dogs love bones
the fish swam in the water
"""

model = build_bigram_model(corpus)

# Generate some text
random.seed(42)
for _ in range(3):
    print(generate_text(model, start_word="the", length=8))

from collections import defaultdict, Counter

def build_trigram_model(text):
    """Build a trigram language model"""
    words = ['<START>'] + text.lower().split() + ['<END>']
    model = defaultdict(Counter)
    
    for i in range(len(words) - 2):
        context = (words[i], words[i+1])
        next_word = words[i+2]
        model[context][next_word] += 1
    
    return model

def trigram_predict(model, word1, word2, top_n=3):
    """Predict top N likely next words given two previous words"""
    context = (word1, word2)
    if context not in model:
        return []
    
    total = sum(model[context].values())
    predictions = [(w, c/total) for w, c in model[context].most_common(top_n)]
    return predictions

# Example
corpus = """
i love cats and i love dogs and i love pizza
cats love fish and dogs love bones
she loves to eat pizza and he loves to eat pasta
"""

model = build_trigram_model(corpus)
print("After 'i love':", trigram_predict(model, "i", "love"))
print("After 'love to':", trigram_predict(model, "love", "to"))

import math

def sentence_probability(model_probs, sentence):
    """
    Calculate log probability of a sentence using bigram model.
    Using log to avoid numerical underflow with many multiplications.
    """
    words = ['<START>'] + sentence.lower().split() + ['<END>']
    log_prob = 0.0
    
    for i in range(len(words) - 1):
        bigram = (words[i], words[i+1])
        prob = model_probs.get(bigram, 1e-10)  # tiny prob for unseen bigrams
        log_prob += math.log(prob)
    
    return log_prob

# Example bigram probabilities (hand-crafted for illustration)
probs = {
    ('<START>', 'i'): 0.5,
    ('i', 'love'): 0.67,
    ('love', 'cats'): 0.33,
    ('cats', '<END>'): 1.0,
    ('<START>', 'the'): 0.3,
    ('the', 'dog'): 0.4,
    ('dog', 'ran'): 0.6,
    ('ran', '<END>'): 1.0,
}

s1 = sentence_probability(probs, "i love cats")
s2 = sentence_probability(probs, "the dog ran")

print(f"Log P('i love cats') = {s1:.2f}")
print(f"Log P('the dog ran') = {s2:.2f}")

def laplace_bigram_probability(word1, word2, bigram_counts, unigram_counts, vocab_size):
    """
    Compute P(word2 | word1) with Laplace (add-1) smoothing
    """
    count_bigram = bigram_counts.get((word1, word2), 0)
    count_unigram = unigram_counts.get(word1, 0)
    
    # Add 1 to numerator, add vocab_size to denominator
    return (count_bigram + 1) / (count_unigram + vocab_size)

# Example
bigram_counts = {('I', 'love'): 10, ('I', 'hate'): 3}
unigram_counts = {'I': 13}
vocab_size = 1000

p_love = laplace_bigram_probability('I', 'love', bigram_counts, unigram_counts, vocab_size)
p_never_seen = laplace_bigram_probability('I', 'purple', bigram_counts, unigram_counts, vocab_size)

print(f"P(love | I) = {p_love:.4f}")
print(f"P(purple | I) = {p_never_seen:.6f}  ← small but not zero")

def backoff_probability(word, context, trigram_probs, bigram_probs, unigram_probs,
                        alpha=0.4):
    """
    Stupid backoff: use trigram if available, else bigram, else unigram.
    alpha is a discount factor applied when backing off.
    """
    if len(context) >= 2:
        trigram_key = (context[-2], context[-1], word)
        if trigram_key in trigram_probs:
            return trigram_probs[trigram_key]
    
    if len(context) >= 1:
        bigram_key = (context[-1], word)
        if bigram_key in bigram_probs:
            return alpha * bigram_probs[bigram_key]
    
    return alpha * alpha * unigram_probs.get(word, 1e-10)

def interpolated_probability(word, context, trigram_probs, bigram_probs, unigram_probs,
                             l1=0.6, l2=0.3, l3=0.1):
    """
    Interpolation smoothing: weighted mix of trigram, bigram, unigram.
    l1 + l2 + l3 must equal 1.
    """
    p_tri = trigram_probs.get((context[-2], context[-1], word), 0) if len(context) >= 2 else 0
    p_bi  = bigram_probs.get((context[-1], word), 0) if len(context) >= 1 else 0
    p_uni = unigram_probs.get(word, 1e-10)
    
    return l1 * p_tri + l2 * p_bi + l3 * p_uni

import math

def perplexity(model_probs, test_sentences):
    """
    Calculate perplexity of a language model on test sentences.
    model_probs: dict of bigram → probability
    test_sentences: list of tokenised sentences (lists of words)
    """
    total_log_prob = 0.0
    total_words = 0
    
    for sentence in test_sentences:
        words = ['<START>'] + sentence + ['<END>']
        for i in range(len(words) - 1):
            bigram = (words[i], words[i+1])
            prob = model_probs.get(bigram, 1e-10)
            total_log_prob += math.log2(prob)
            total_words += 1
    
    avg_log_prob = total_log_prob / total_words
    return 2 ** (-avg_log_prob)

# Example: comparing two models on test data
good_model = {
    ('<START>', 'i'): 0.5,   ('i', 'love'): 0.7,
    ('love', 'cats'): 0.5,   ('cats', '<END>'): 1.0,
}

bad_model = {
    ('<START>', 'i'): 0.1,   ('i', 'love'): 0.1,
    ('love', 'cats'): 0.1,   ('cats', '<END>'): 1.0,
}

test = [['i', 'love', 'cats']]

print(f"Good model perplexity: {perplexity(good_model, test):.2f}")
print(f"Bad model perplexity:  {perplexity(bad_model, test):.2f}")
# Good model perplexity: ~1.6   (very confident)
# Bad model perplexity:  ~10.0  (more confused)

import random
from collections import defaultdict, Counter
import re

def train_markov_model(text, order=2):
    """
    Train a Markov chain language model.
    order: how many previous words to use as context (1=bigram, 2=trigram)
    """
    # Clean and tokenise
    words = re.findall(r'\b\w+\b', text.lower())
    model = defaultdict(Counter)
    
    for i in range(len(words) - order):
        context = tuple(words[i:i+order])
        next_word = words[i+order]
        model[context][next_word] += 1
    
    return model

def generate_markov_text(model, order, seed_words, length=30):
    """Generate text using the Markov model"""
    output = list(seed_words)
    context = tuple(seed_words[-order:])
    
    for _ in range(length):
        if context not in model:
            break
        
        # Weighted random choice
        choices = list(model[context].keys())
        weights = list(model[context].values())
        next_word = random.choices(choices, weights=weights, k=1)[0]
        
        output.append(next_word)
        context = tuple(output[-order:])
    
    return ' '.join(output)

# Train on some text
training_text = """
The cat sat on the mat. The cat ate the fish.
The dog ran in the park. The dog chased the cat.
Cats like to eat fish and sleep on mats.
Dogs like to run and play in the park.
The fish swam in the river near the park.
On sunny days, the cat and the dog played together.
"""

model = train_markov_model(training_text, order=2)

print("Generated sentences (order-2 Markov chain):")
print("-" * 50)
random.seed(1)
for i in range(5):
    seed = random.choice(list(model.keys()))
    text = generate_markov_text(model, order=2, seed_words=list(seed), length=12)
    print(f"  {i+1}. {text}")