import random
from dataclasses import dataclass

@dataclass(frozen=True)
class Transition:
    next_state: str
    prob: float

@dataclass(frozen=True)
class ActionModel:
    transitions: list[Transition]

class TinyMDP:
    def __init__(self):
        self.states = ["A", "B", "C"]
        self.actions = ["alpha", "beta"]

        # Transition model: P(s' | s, a)
        self.T: dict[tuple[str, str], ActionModel] = {
            ("A", "alpha"): ActionModel([
                Transition("A", 0.1),
                Transition("B", 0.6),
                Transition("C", 0.3),
            ]),
            ("A", "beta"): ActionModel([
                Transition("A", 0.7),
                Transition("B", 0.2),
                Transition("C", 0.1),
            ]),
            ("B", "alpha"): ActionModel([
                Transition("A", 0.4),
                Transition("B", 0.4),
                Transition("C", 0.2),
            ]),
            ("B", "beta"): ActionModel([
                Transition("B", 0.8),
                Transition("C", 0.2),
            ]),
            ("C", "alpha"): ActionModel([
                Transition("C", 1.0),
            ]),
            ("C", "beta"): ActionModel([
                Transition("A", 0.25),
                Transition("C", 0.75),
            ]),
        }

        # Reward/utility model
        self.state_utility = {"A": 2.0, "B": 4.0, "C": 9.0}
        self.action_cost = {"alpha": 0.6, "beta": 0.2}

    def expected_utility_one_step(self, state: str, action: str) -> float:
        model = self.T[(state, action)]
        exp_u = 0.0
        for tr in model.transitions:
            exp_u += tr.prob * self.state_utility[tr.next_state]
        exp_u -= self.action_cost[action]
        return exp_u

    def greedy_policy(self, state: str) -> str:
        best_action = None
        best_value = float("-inf")
        for a in self.actions:
            val = self.expected_utility_one_step(state, a)
            if val > best_value:
                best_value = val
                best_action = a
        return best_action

    def sample_next_state(self, state: str, action: str, rng: random.Random) -> str:
        r = rng.random()
        cumulative = 0.0
        outcomes = self.T[(state, action)].transitions
        for tr in outcomes:
            cumulative += tr.prob
            if r <= cumulative:
                return tr.next_state
        return outcomes[-1].next_state

if __name__ == "__main__":
    mdp = TinyMDP()
    rng = random.Random(7)

    state = "A"
    action = mdp.greedy_policy(state)
    next_state = mdp.sample_next_state(state, action, rng)

    eu_alpha = mdp.expected_utility_one_step("A", "alpha")
    eu_beta = mdp.expected_utility_one_step("A", "beta")

    print("state=", state, "greedy_action=", action, "sampled_next_state=", next_state)
    print("expected_utility(alpha)=", eu_alpha)
    print("expected_utility(beta)=", eu_beta)

from dataclasses import dataclass

@dataclass(frozen=True)
class Transition:
    next_state: str
    prob: float

@dataclass(frozen=True)
class ActionModel:
    transitions: list[Transition]

class DiscountedMDP:
    def __init__(self):
        self.states = ["X", "Y", "Z"]
        self.actions = ["left", "right"]

        # Transition model: P(s' | s, a)
        self.T: dict[tuple[str, str], ActionModel] = {
            ("X", "left"): ActionModel([
                Transition("X", 0.5),
                Transition("Y", 0.5),
            ]),
            ("X", "right"): ActionModel([
                Transition("Y", 0.2),
                Transition("Z", 0.8),
            ]),
            ("Y", "left"): ActionModel([
                Transition("X", 0.3),
                Transition("Y", 0.7),
            ]),
            ("Y", "right"): ActionModel([
                Transition("Y", 0.4),
                Transition("Z", 0.6),
            ]),
            ("Z", "left"): ActionModel([
                Transition("X", 0.6),
                Transition("Z", 0.4),
            ]),
            ("Z", "right"): ActionModel([
                Transition("Z", 1.0),
            ]),
        }

        # Action costs
        self.action_cost = {"left": 0.3, "right": 0.1}

        # Provided initial value estimate V0
        self.V0 = {"X": 1.0, "Y": 2.0, "Z": 3.0}

    def expected_utility_one_step(self, state: str, action: str, V: dict[str, float], discount: float) -> float:
        model = self.T[(state, action)]
        exp_u = 0.0
        for tr in model.transitions:
            exp_u += tr.prob * (discount * V[tr.next_state])
        exp_u -= self.action_cost[action]
        return exp_u

    def greedy_policy(self, state: str, V: dict[str, float], discount: float) -> str:
        best_action = None
        best_value = float("-inf")
        for a in self.actions:
            val = self.expected_utility_one_step(state, a, V, discount)
            if val > best_value:
                best_value = val
                best_action = a
        return best_action

    def update_values(self, iterations: int, discount: float) -> dict[str, float]:
        V = dict(self.V0)
        for _ in range(iterations):
            V_new = {}
            for s in self.states:
                best_val = float("-inf")
                for a in self.actions:
                    val = self.expected_utility_one_step(s, a, V, discount)
                    if val > best_val:
                        best_val = val
                V_new[s] = best_val
            V = V_new
        return V

if __name__ == "__main__":
    mdp = DiscountedMDP()
    discount = 0.9
    iterations = 3

    V = mdp.update_values(iterations=iterations, discount=discount)

    # Print values in a stable order
    for s in mdp.states:
        print("V[", s, "]=", round(V[s], 6))

    # Print greedy action per state
    for s in mdp.states:
        a = mdp.greedy_policy(s, V, discount)
        print("greedy_action_for(", s, ")=", a)

import math
import random


def sigmoid(x: float) -> float:
    return 1.0 / (1.0 + math.exp(-x))


def loss_and_grads(w: float, b: float, data: list[tuple[float, int]]):
    loss = 0.0
    dw = 0.0
    db = 0.0
    eps = 1e-12

    for x, y in data:
        z = w * x + b
        p = sigmoid(z)
        loss += -(y * math.log(p + eps) + (1 - y) * math.log(1 - p + eps))
        dz = p - y
        dw += dz * x
        db += dz

    n = len(data)
    return loss / n, dw / n, db / n


def main():
    random.seed(1)

    data = []
    for _ in range(60):
        x = random.uniform(-2.5, 2.5)
        # Ground-truth rule with noise: y=1 when x + noise > 0
        y = 1 if x + random.uniform(-0.3, 0.3) > 0 else 0
        data.append((x, y))

    w = random.uniform(-1.0, 1.0)
    b = random.uniform(-1.0, 1.0)

    lr = 0.7
    steps = 30

    for t in range(steps):
        L, dw, db = loss_and_grads(w, b, data)
        w -= lr * dw
        b -= lr * db
        if t % 6 == 0:
            print(f"step={t} loss={L:.4f} w={w:.3f} b={b:.3f}")

    correct = 0
    for x, y in data:
        p = sigmoid(w * x + b)
        pred = 1 if p >= 0.5 else 0
        correct += (pred == y)

    acc = correct / len(data)
    print(f"accuracy={acc:.4f}")


if __name__ == "__main__":
    main()

import math
import random


def sigmoid(x: float) -> float:
    return 1.0 / (1.0 + math.exp(-x))


def loss_and_grads(w: float, b: float, data: list[tuple[float, int]]):
    loss = 0.0
    dw = 0.0
    db = 0.0
    eps = 1e-12

    for x, y in data:
        z = w * x + b
        p = sigmoid(z)
        loss += -(y * math.log(p + eps) + (1 - y) * math.log(1 - p + eps))
        dz = p - y
        dw += dz * x
        db += dz

    n = len(data)
    return loss / n, dw / n, db / n


def loss_only(w: float, b: float, data: list[tuple[float, int]]):
    eps = 1e-12
    loss = 0.0
    for x, y in data:
        z = w * x + b
        p = sigmoid(z)
        loss += -(y * math.log(p + eps) + (1 - y) * math.log(1 - p + eps))
    return loss / len(data)


def main():
    random.seed(2)

    # Create dataset
    all_data = []
    for _ in range(120):
        x = random.uniform(-3.0, 3.0)
        y = 1 if x + random.uniform(-0.35, 0.35) > 0 else 0
        all_data.append((x, y))

    # Deterministic shuffle and split
    random.shuffle(all_data)
    split = int(0.75 * len(all_data))
    train_data = all_data[:split]
    val_data = all_data[split:]

    # Initialize parameters
    w = random.uniform(-1.0, 1.0)
    b = random.uniform(-1.0, 1.0)

    lr = 0.6
    max_steps = 200
    print_every = 20

    patience = 12
    min_delta = 1e-4

    best_val_loss = float("inf")
    best_step = -1
    patience_left = patience

    for t in range(max_steps):
        train_loss, dw, db = loss_and_grads(w, b, train_data)
        val_loss = loss_only(w, b, val_data)

        if val_loss < best_val_loss - min_delta:
            best_val_loss = val_loss
            best_step = t
            patience_left = patience
        else:
            patience_left -= 1

        if t % print_every == 0:
            print(
                f"step={t} train_loss={train_loss:.4f} val_loss={val_loss:.4f} "
                f"w={w:.3f} b={b:.3f}"
            )

        # Early stopping check
        if patience_left == 0:
            break

        # Gradient descent update
        w -= lr * dw
        b -= lr * db

    print(f"best_val_loss={best_val_loss:.4f} best_step={best_step}")


if __name__ == "__main__":
    main()

import math
import re
from collections import Counter


def tokenize(text: str) -> list[str]:
    return re.findall(r"[a-zA-Z]+", text.lower())


class TfidfEmbedder:
    def __init__(self):
        self.idf: dict[str, float] = {}
        self.vocab: list[str] = []

    def fit(self, docs: list[str]) -> None:
        tokenized = [tokenize(d) for d in docs]
        df = Counter()
        for toks in tokenized:
            for t in set(toks):
                df[t] += 1

        n = len(docs)
        self.vocab = sorted(df.keys())
        self.idf = {t: math.log((n + 1) / (df[t] + 1)) + 1.0 for t in self.vocab}

    def vectorize(self, text: str) -> list[float]:
        toks = tokenize(text)
        tf = Counter(toks)
        vec: list[float] = []
        for t in self.vocab:
            vec.append(tf.get(t, 0) * self.idf[t])
        return vec


def cosine_similarity(a: list[float], b: list[float]) -> float:
    dot = sum(x * y for x, y in zip(a, b))
    na = math.sqrt(sum(x * x for x in a))
    nb = math.sqrt(sum(y * y for y in b))
    if na == 0.0 or nb == 0.0:
        return 0.0
    return dot / (na * nb)


# Micro-world documents
docs = [
    "Robots navigate using sensor fusion and localization.",
    "Computer vision detects edges and shapes in images.",
    "Reinforcement learning trains agents with rewards.",
    "Planning under uncertainty uses expected utility.",
    "Natural language processing maps text to meaning vectors.",
]

question = "How do agents learn from rewards?"

embedder = TfidfEmbedder()
embedder.fit(docs)

qv = embedder.vectorize(question)

scores = []
for i, d in enumerate(docs):
    dv = embedder.vectorize(d)
    scores.append((cosine_similarity(qv, dv), i, d))

scores.sort(key=lambda x: x[0], reverse=True)

print("Top 2 matches:")
for s, i, d in scores[:2]:
    print(f"score={s:.3f} doc_index={i} text={d}")

import math
import re
from collections import Counter


def tokenize(text: str) -> list[str]:
    return re.findall(r"[a-zA-Z]+", text.lower())


class TfidfEmbedder:
    def __init__(self):
        self.idf: dict[str, float] = {}
        self.vocab: list[str] = []

    def fit(self, docs: list[str]) -> None:
        tokenized = [tokenize(d) for d in docs]
        df = Counter()
        for toks in tokenized:
            for t in set(toks):
                df[t] += 1

        n = len(docs)
        self.vocab = sorted(df.keys())
        self.idf = {t: math.log((n + 1) / (df[t] + 1)) + 1.0 for t in self.vocab}

    def vectorize(self, text: str) -> list[float]:
        toks = tokenize(text)
        tf = Counter(toks)
        return [tf.get(t, 0) * self.idf[t] for t in self.vocab]


def cosine_similarity(a: list[float], b: list[float]) -> float:
    dot = sum(x * y for x, y in zip(a, b))
    na = math.sqrt(sum(x * x for x in a))
    nb = math.sqrt(sum(y * y for y in b))
    if na == 0.0 or nb == 0.0:
        return 0.0
    return dot / (na * nb)


def expand_query(question: str, synonyms: dict[str, list[str]]) -> str:
    q_tokens = tokenize(question)
    expanded = list(q_tokens)
    for tok in q_tokens:
        if tok in synonyms:
            expanded.extend(synonyms[tok])
    return " ".join(expanded)


# Micro-world documents
# Note: vocabulary is learned from docs only.
docs = [
    "Reinforcement learning uses rewards to train agents.",
    "Supervised learning trains models using labeled examples.",
    "Planning under uncertainty uses expected utility.",
    "Machine translation converts text between languages.",
    "Incentives and rewards can shape agent behavior.",
]

synonyms = {
    "reward": ["rewards", "incentive", "incentives"],
    "rewards": ["reward", "incentives"],
    "agent": ["agents"],
    "agents": ["agent"],
}

question = "How do agents learn from reward signals?"
expanded_question = expand_query(question, synonyms)

embedder = TfidfEmbedder()
embedder.fit(docs)

qv = embedder.vectorize(expanded_question)

scores = []
for i, d in enumerate(docs):
    dv = embedder.vectorize(d)
    scores.append((cosine_similarity(qv, dv), i, d))

# Tie-break by smaller doc_index when scores are equal.
scores.sort(key=lambda x: (-x[0], x[1]))

print("Expanded query:", expanded_question)
print("Top 3 matches:")
for s, i, d in scores[:3]:
    print(f"score={s:.3f} doc_index={i} text={d}")