What is a token, and why is AI priced per token?

"""Byte-level byte pair encoding (BPE), small enough to read in one sitting.

Ids 0 to 255 are the 256 possible bytes. Training adds one new id per merge: merge number k
(counting from 0) makes id 256 + k out of a pair of existing ids. Encoding then applies the
same merges to new text, so any string can be written as ids and read back exactly.

The widget in ../widget.html runs the same rules in JavaScript. Two things must stay identical in
both: the splitting pattern PIECE and the tie-break rule in train_counted().
"""
import re
from collections import Counter
from pathlib import Path

# Split text into pieces first, so a merge never joins across a word and the punctuation after it.
# Letters, digits, punctuation and whitespace each form their own runs; a single leading space
# stays with the word that follows, so " the" and "the" are different pieces. Any character
# outside ASCII counts as a letter. The six alternatives cover every character exactly once.
PIECE = re.compile(
    r" ?[A-Za-z\u0080-\U0010ffff]+"
    r"| ?[0-9]+"
    r"| ?[!-/:-@\[-`{-~]+"
    r"|[ \t\r\n]+(?![^ \t\r\n])"
    r"|[ \t\r\n]+"
    r"|[\x00-\x1f\x7f]"
)

MIN_COUNT = 2  # a pair seen only once is not worth a vocabulary slot
NUM_MERGES = 512  # the lesson's vocabulary: 256 bytes + 512 merges = 768 ids
CORPUS_PATH = Path(__file__).with_name("corpus.txt")


def load_corpus():
    """The training text: written for this lesson, about 15 KB of prose, code, numbers and Korean."""
    return CORPUS_PATH.read_text(encoding="utf-8")


def pieces(text):
    """Split text into the pieces that BPE works inside. Joined back together they equal the text."""
    return PIECE.findall(text)


def train_counted(text, num_merges=NUM_MERGES, min_count=MIN_COUNT):
    """Learn up to num_merges merges. Returns a list of ((left_id, right_id), count) in order.

    Each round counts every adjacent pair of ids inside every piece and merges the most frequent
    one. A tie goes to the smaller (left_id, right_id), so training is deterministic. Training
    stops early when the best pair appears fewer than min_count times.
    """
    words = Counter(tuple(p.encode("utf-8")) for p in pieces(text))
    learned = []
    for _ in range(num_merges):
        pairs = Counter()
        for word, freq in words.items():
            for pair in zip(word, word[1:]):
                pairs[pair] += freq
        if not pairs:
            break
        best = min(pairs, key=lambda pair: (-pairs[pair], pair))
        if pairs[best] < min_count:
            break
        learned.append((best, pairs[best]))
        words = _merge_words(words, best, 255 + len(learned))
    return learned


def train(text, num_merges=NUM_MERGES, min_count=MIN_COUNT):
    """Like train_counted, keeping only the pairs."""
    return [pair for pair, _ in train_counted(text, num_merges, min_count)]


def _apply(word, pair, new_id):
    """Replace every left-to-right occurrence of pair in a tuple of ids with new_id."""
    out = []
    i = 0
    while i < len(word):
        if i + 1 < len(word) and (word[i], word[i + 1]) == pair:
            out.append(new_id)
            i += 2
        else:
            out.append(word[i])
            i += 1
    return tuple(out)


def _merge_words(words, pair, new_id):
    merged = Counter()
    for word, freq in words.items():
        merged[_apply(word, pair, new_id)] += freq
    return merged


def vocab_bytes(merges):
    """The bytes each id stands for: 256 single bytes, then one entry per merge."""
    table = [bytes([b]) for b in range(256)]
    for left, right in merges:
        table.append(table[left] + table[right])
    return table


def encode(text, merges):
    """Turn text into ids. Within a piece, always apply the earliest-learned merge that is present."""
    rank = {pair: k for k, pair in enumerate(merges)}
    cache = {}
    ids = []
    for piece in pieces(text):
        if piece not in cache:
            word = list(piece.encode("utf-8"))
            while len(word) > 1:
                best = min(zip(word, word[1:]), key=lambda pair: rank.get(pair, len(rank)))
                if best not in rank:
                    break
                word = list(_apply(word, best, 256 + rank[best]))
            cache[piece] = word
        ids.extend(cache[piece])
    return ids


def decode(ids, merges):
    """Turn ids back into text. Bytes that are not valid UTF-8 become the replacement character."""
    table = vocab_bytes(merges)
    return b"".join(table[i] for i in ids).decode("utf-8", errors="replace")

"""Count the same four samples with three published tokenizers and with the toy.

Needs the tiktoken package (pip install tiktoken). The first run of each encoding downloads its
vocabulary file, so it needs network access once; later runs use the cache. Run it from this folder:
python3 compare_tiktoken.py
"""
import sys

from bpe import NUM_MERGES, encode, load_corpus, train
from samples import SAMPLES

try:
    import tiktoken
except ImportError:
    print("tiktoken is not installed: pip install tiktoken, then run this again.")
    sys.exit(0)

ENCODINGS = ("gpt2", "cl100k_base", "o200k_base")
GROUPS_OF_3 = r"\p{N}{1,3}"  # the digit rule in the splitting pattern of cl100k_base and o200k_base

toy = train(load_corpus())
published = {}
counters = {f"toy ({NUM_MERGES} merges)": lambda text: len(encode(text, toy))}
for name in ENCODINGS:
    try:
        enc = tiktoken.get_encoding(name)
    except Exception as err:  # first use downloads the vocabulary; no network means no encoding
        print(f"skipped {name}: {type(err).__name__}")
        continue
    published[name] = enc
    counters[f"{name} ({enc.n_vocab:,} ids)"] = lambda text, enc=enc: len(enc.encode(text))
    assert enc.decode(enc.encode(SAMPLES["Korean"])) == SAMPLES["Korean"]

print("== Tokens for each sample (fewer is shorter)")
print(f"  {'tokenizer':26}" + "".join(f"{n:>9}" for n in SAMPLES))
for label, count in counters.items():
    print(f"  {label:26}" + "".join(f"{count(t):>9}" for t in SAMPLES.values()))

print("\n== Bytes per token")
print(f"  {'tokenizer':26}" + "".join(f"{n:>9}" for n in SAMPLES))
for label, count in counters.items():
    print(f"  {label:26}" + "".join(f"{len(t.encode()) / count(t):>9.2f}" for t in SAMPLES.values()))

print("\n== Tokens per word (a word is a run of non-space characters)")
print(f"  {'tokenizer':26}" + "".join(f"{n:>9}" for n in SAMPLES))
for label, count in counters.items():
    print(f"  {label:26}" + "".join(f"{count(t) / len(t.split()):>9.2f}" for t in SAMPLES.values()))

print("\n== Korean sample tokens divided by English sample tokens (two different texts, not translations)")
for label, count in counters.items():
    ratio = count(SAMPLES["Korean"]) / count(SAMPLES["English"])
    print(f"  {label:26}{ratio:>6.2f}")

print("\n== Digits: most in one token on the Numbers sample, and whether the splitting pattern cuts digit runs into groups of at most 3")
for name, enc in published.items():
    pieces = [enc.decode([i]) for i in enc.encode(SAMPLES["Numbers"])]
    most = max(sum(c.isdigit() for c in piece) for piece in pieces)
    print(f"  {name:26}{most:>3}   {GROUPS_OF_3 in getattr(enc, '_pat_str', '')}")

print("\n== The first 12 tokens of each sample under cl100k_base (one repr per token)")
if "cl100k_base" in {label.split(" ")[0] for label in counters}:
    enc = tiktoken.get_encoding("cl100k_base")
    for name, text in SAMPLES.items():
        print(f"  {name:8}", [enc.decode([i]) for i in enc.encode(text)[:12]])

The harbour town had one bakery, one bridge and one clock that was always five minutes slow. Every morning the baker opened the shutters before the first ferry arrived, and the smell of warm bread drifted down the hill to the water. People who lived there said that you could tell the season by the loaves in the window: dark rye in the winter, seeded rolls in the spring, and flat bread with olives when the tourists came.

A small team can build a useful product when it keeps the work simple. Start with the problem that a real person has today, write down what they need to finish, and build only the part that gets them there. Then measure what happens. If the numbers are good, add the next feature. If the numbers are bad, find out why before writing more code. Most of the time, the answer is boring: a button was hard to find, a page was slow, or a message did not say what to do next.

The library on the hill closes at six in the evening, but the reading room stays open for another hour. Students sit at the long tables with their laptops and their notebooks, and the librarian walks past every ten minutes to turn down the lights near the windows. In the corner there is a shelf of maps, and on the top shelf there is a globe that nobody is allowed to spin.

When you read a recipe, check the time before you check the ingredients. A stew that needs three hours is not a dinner for a Tuesday. Chop the onions, the carrots and the celery into pieces of the same size so that they cook at the same speed. Add the salt early, add the herbs late, and taste the pot before you serve it. If the sauce is too thin, let it simmer with the lid off. If it is too thick, add a little water and stir.

Computers do not read letters. They read numbers, and a program that works with text must first decide how to turn the text into numbers. The simplest choice is to give every character its own number. That works, but it makes the sequences long, and long sequences cost time and memory. A better choice is to give common groups of characters their own numbers, so that a word like the or and takes one step instead of three. These groups are called tokens, and the list of all of them is called the vocabulary.

The tokenizer is a separate program from the model. It is built before the model is trained, from a large pile of text, and then it is frozen. After that, the model only ever sees the numbers that the tokenizer produces. If a word is common in the pile, it gets a token of its own. If a word is rare, it is cut into smaller pieces that the tokenizer already knows. Because the smallest pieces are single bytes, any text at all can be written down, even a word that nobody has used before.

The trade is easy to state. A bigger vocabulary means shorter sequences, but every token needs a row in the tables that the model keeps, and rare tokens are seen so seldom that the model learns little about them. A smaller vocabulary means longer sequences, which cost more at every step. Teams pick a size between the two, test it, and keep it for the whole life of the model.

Engineers measure a tokenizer with a few simple ratios. How many tokens does a page of English need? How many does a page of code need? How many does a page of numbers need? The answers differ, and they differ for a reason: the tokenizer saw some kinds of text far more often than others, and those kinds got the longest and most useful pieces. Text that looks different from the training pile is cut into more and smaller pieces, and the same idea costs more tokens.

Weather in the mountains changes faster than weather on the coast. In the morning the valley is clear, by noon a cloud sits on the ridge, and by evening the wind turns and brings rain from the west. Hikers who start early can finish before the rain, and hikers who start late should carry a coat. The hut at the top has a stove, a kettle and twelve beds, and the keeper writes the temperature on a board by the door.

Please read the notes below before you run the script. The first line sets the name of the project. The second line sets the folder where the files will be written. If the folder does not exist, the script creates it. If the folder already has files in it, the script stops and asks you what to do, because it never deletes anything without being told to.

Rivers carry stones from the mountains to the sea. A stone that starts the size of a fist is the size of a coin when it reaches the delta, and it is the size of a grain of sand by the time the tide takes it. Nothing is lost along the way. The stone is only cut into smaller and smaller pieces, and each piece goes where the water takes it.

Every spring the village holds a market on the square, and every spring it rains for the first hour. The farmers put up their canvas roofs, the children run between the stalls, and the old man who sells honey tells anyone who will listen that the rain is good for the flowers. By noon the sun comes out, the roofs are folded away, and the square fills with people who have walked in from the hills.

Good notes are short. Write the date, write what you decided, and write why you decided it. A month later you will not remember the reason, and the reason is the part you will need. If you wrote down only the decision, you will have to guess, and you might guess wrong. If you wrote down the reason, you can check whether it is still true and change the decision when it is not.

The train to the coast leaves from the third platform, and it is usually on time. It stops at every small station, so the journey takes almost two hours, but nobody minds because the window seats look out over the fields. A woman with a basket of apples sits across from a student with a thick book, and neither of them says a word until the conductor comes by to check the tickets.

Before you change a program, read it. Find the function that does the work, find the tests that cover it, and run the tests to see that they pass. Then make one small change and run the tests again. If a test fails, the change is the first thing to suspect, because the code was working a minute ago. Small steps make mistakes easy to find, and large steps hide them.

Our neighbour keeps bees on the roof of the garage. In summer the air above the garden hums, and in winter the hives are wrapped in old blankets and left alone. He sells the honey to the corner shop, and he gives a jar to anyone who helps him carry the boxes in the autumn. Last year he gave away forty jars and kept six for himself.

A cache is a place where you keep something you will need again, so that you do not have to go and fetch it a second time. A cook keeps salt next to the stove. A programmer keeps the result of a slow calculation in memory. A library keeps the most popular books near the door. The idea is always the same: pay the cost of the first trip once, and make the later trips cheap.

The price of a service usually follows the cost of providing it. A shop pays for its shelves and its staff, so it charges for the goods. A railway pays for its tracks and its engines, so it charges for the distance. A web service pays for its machines and its power, so it charges for the work the machines do. When the work can be counted, the bill can be counted too, and a bill that can be counted can be checked.

On the last night of the festival the whole town walks down to the river with paper lanterns. Each lantern has a name written on it, and the names are of people who are far away or no longer here. The lanterns float slowly toward the bridge, and the crowd goes quiet. Then someone starts to sing, and one by one the others join in, until the song fills the valley.

If you cannot explain an idea in plain words, you probably do not understand it yet. Try it on a friend who has never heard of the subject. Watch where their face changes, because that is where you skipped a step. Go back, add the step, and try again. After three or four rounds the explanation is shorter than the first draft, and you understand the idea better than you did when you started.

Language models read and write tokens. A request to a model is cut into tokens, the model reads all of them, and then it writes its answer one token at a time. Each new token depends on everything that came before it, so the answer cannot be written in parallel. This is why a long answer takes longer than a short one, and why a service that charges by the amount of work charges more for the tokens it writes than for the tokens it reads.

The engineer who counts tokens before shipping a product is the engineer who is not surprised by the bill. Count the tokens in the longest prompt, count the tokens in a typical answer, and multiply by the number of requests you expect. Then change one thing at a time. Shorten the instructions, keep the beginning of the prompt the same on every request, and ask for the answer in the form that needs the fewest words.

def count_words(text):
    counts = {}
    for word in text.split():
        word = word.lower().strip(".,;:!?")
        if word:
            counts[word] = counts.get(word, 0) + 1
    return counts


def top_words(text, limit=10):
    counts = count_words(text)
    ranked = sorted(counts.items(), key=lambda item: (-item[1], item[0]))
    return ranked[:limit]


class Counter:
    def __init__(self, start=0):
        self.value = start

    def increment(self, amount=1):
        self.value += amount
        return self.value

    def reset(self):
        self.value = 0


def read_lines(path):
    with open(path, "r", encoding="utf-8") as handle:
        for line in handle:
            line = line.rstrip("\n")
            if line:
                yield line


def parse_row(line):
    parts = line.split(",")
    if len(parts) != 3:
        raise ValueError("expected three fields, got " + str(len(parts)))
    name, count, price = parts
    return {"name": name, "count": int(count), "price": float(price)}


def total(rows):
    result = 0.0
    for row in rows:
        result += row["count"] * row["price"]
    return result


if __name__ == "__main__":
    rows = [parse_row(line) for line in read_lines("orders.csv")]
    print("total:", total(rows))

function sumPrices(items) {
  let total = 0;
  for (const item of items) {
    if (typeof item.price === "number") {
      total += item.price * item.count;
    }
  }
  return total;
}

const items = [
  { name: "tea", price: 3.5, count: 2 },
  { name: "bread", price: 2.25, count: 4 },
];
console.log(sumPrices(items));

async function loadJson(url) {
  const response = await fetch(url);
  if (!response.ok) {
    throw new Error("request failed: " + response.status);
  }
  return response.json();
}

SELECT name, count(*) AS orders, sum(price) AS revenue
FROM orders
WHERE created_at >= '2026-01-01'
GROUP BY name
HAVING count(*) > 10
ORDER BY revenue DESC
LIMIT 20;

{"name": "tea", "price": 3.5, "tags": ["drink", "hot"], "stock": 120}
{"name": "bread", "price": 2.25, "tags": ["food", "fresh"], "stock": 48}
{"name": "jam", "price": 4.0, "tags": ["food", "sweet"], "stock": 0}

for file in *.txt; do
  echo "$file: $(wc -l < "$file") lines"
done

if (value == null) {
    return defaultValue;
}
for (int i = 0; i < length; i++) {
    sum += values[i];
}

def moving_average(values, window):
    if window <= 0:
        raise ValueError("window must be positive")
    result = []
    for i in range(len(values)):
        start = max(0, i - window + 1)
        chunk = values[start:i + 1]
        result.append(sum(chunk) / len(chunk))
    return result


def merge_dicts(first, second):
    merged = dict(first)
    for key, value in second.items():
        if key in merged and isinstance(merged[key], dict) and isinstance(value, dict):
            merged[key] = merge_dicts(merged[key], value)
        else:
            merged[key] = value
    return merged


try:
    value = int(text)
except ValueError:
    value = None
else:
    print("parsed", value)

import json
import os
from pathlib import Path

data = json.loads(Path("config.json").read_text())
print(data["name"], os.getcwd())


Order 1001 shipped on 2026-03-04 with 12 items for a total of 148.50 dollars.
Order 1002 shipped on 2026-03-05 with 3 items for a total of 27.90 dollars.
Order 1003 shipped on 2026-03-05 with 40 items for a total of 512.00 dollars.
Order 1004 shipped on 2026-03-06 with 7 items for a total of 63.25 dollars.

id   year   value      share
101  2019   12345.67   0.125
102  2020   23456.78   0.250
103  2021   34567.89   0.375
104  2022   45678.90   0.500
105  2023   56789.01   0.625
106  2024   67890.12   0.750
107  2025   78901.23   0.875
108  2026   89012.34   1.000

3.14159 2.71828 1.41421 1.61803 0.57721 6.02214 1.38065 9.80665
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 20000 50000 100000
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536
2026-01-15 2026-02-03 2026-03-21 2026-04-09 2026-05-30 2026-06-18
0x00 0x01 0x0f 0x10 0x7f 0x80 0xff 0x1000 0xffff
Total: 1,234,567 units, 98.6 percent complete, 45 minutes left.
Temperatures this week: 12, 14, 9, 7, 15, 18, 21 degrees.
Distances: 0.5 km, 1.2 km, 3.8 km, 12.4 km, 42.195 km.
Version 1.2.3, version 2.0.1, version 10.4.17, build 20260315.

Item 7001 costs 19.99, item 7002 costs 24.50, item 7003 costs 5.00, item 7004 costs 105.75.
Latency: 12 ms, 15 ms, 11 ms, 230 ms, 14 ms, 13 ms, 12 ms, 16 ms (median 13.5 ms).
Counts per day: 120 135 128 142 150 98 77 131 140 146 152 160 101 80.
Prices: 0.15 0.30 0.60 1.25 2.50 5.00 10.00 15.00 per million.
Phone-free sample ids: A100 B200 C300 D400 E500 F600 G700 H800 J900.

한국의 가을은 맑고 시원합니다. 아침에는 공기가 차갑지만 낮에는 햇살이 따뜻해서 산책하기에 좋습니다.
저는 매일 아침 일곱 시에 일어나서 따뜻한 차를 마시고 신문을 읽습니다.
도서관은 오후 여섯 시에 문을 닫지만 열람실은 한 시간 더 열려 있습니다.
학생들은 긴 책상에 앉아서 공부를 하고 사서는 십 분마다 한 번씩 책상 사이를 걸어 다닙니다.
오늘은 친구와 함께 시장에 가서 신선한 채소와 과일을 샀습니다.
빵집 주인은 매일 아침 첫 배가 도착하기 전에 문을 열고 따뜻한 빵을 구웠습니다.
기차는 오 분 늦게 도착했지만 승객들은 아무도 불평하지 않았습니다.
컴퓨터는 글자를 읽지 못하고 숫자만 읽을 수 있기 때문에 글을 숫자로 바꾸는 방법이 필요합니다.
토큰은 글을 잘게 나눈 조각이고 어휘는 그 조각들의 목록입니다.
자주 쓰는 단어는 하나의 조각으로 처리하고 드문 단어는 여러 개의 작은 조각으로 나눕니다.
이 프로그램은 파일을 읽어서 단어의 수를 세고 가장 많이 나온 단어를 보여 줍니다.
비가 오는 날에는 우산을 가지고 가고 집에 돌아오면 젖은 옷을 말립니다.
저녁에는 가족과 함께 밥을 먹고 오늘 있었던 일에 대해서 이야기를 나눕니다.
내일은 일찍 일어나서 강가를 따라 달리고 돌아와서 아침을 먹을 생각입니다.
겨울이 오면 산 위에는 눈이 쌓이고 마을에는 조용한 아침이 찾아옵니다.
시장에서 산 사과는 달고 아삭아삭해서 아이들이 아주 좋아했습니다.
선생님은 칠판에 오늘 배울 내용을 쓰고 학생들에게 차례대로 질문을 했습니다.
버스를 타고 한 시간쯤 가면 바다가 보이는 작은 마을에 도착합니다.
좋은 프로그램은 짧고 읽기 쉬우며 실수가 생기면 금방 찾을 수 있어야 합니다.
모델은 글을 한 번에 읽지만 답은 한 조각씩 차례로 씁니다.

"""What one request costs, and how much sequential work it needs, as functions of token counts.

Money uses Decimal so the cents are exact. The prices in this lesson are examples that you edit:
no real price list is built in.
"""
from decimal import Decimal

PER = Decimal(1_000_000)  # prices are quoted per million tokens


def _dec(value):
    return value if isinstance(value, Decimal) else Decimal(str(value))


def request_cost(uncached_input, cached_input, output, price_input, price_cached, price_output):
    """Dollars for one request, as a Decimal.

    uncached_input are input tokens billed at price_input, cached_input are input tokens read
    from a stored prefix and billed at price_cached, output are generated tokens billed at
    price_output. Counts are whole tokens; prices are dollars per million tokens.
    """
    counts = (uncached_input, cached_input, output)
    prices = tuple(_dec(p) for p in (price_input, price_cached, price_output))
    if min(counts) < 0 or min(prices) < 0:
        raise ValueError("counts and prices cannot be negative")
    total = counts[0] * prices[0] + counts[1] * prices[1] + counts[2] * prices[2]
    return total / PER


def sequential_passes(input_tokens, output_tokens):
    """Passes through the model that cannot overlap in time.

    The whole prompt goes through in one pass, however long it is, and that pass also yields the
    first output token. Every later output token needs a pass of its own, because it depends on
    the one before it.
    """
    if input_tokens < 1 or output_tokens < 0:
        raise ValueError("need at least one input token and a non-negative output length")
    return max(1, output_tokens)


def decode_positions_read(input_tokens, output_tokens):
    """Earlier positions read in total by the decode passes, counting a pass's own token.

    Decode pass j (j = 1 to output_tokens - 1) reads the input_tokens prompt positions plus j
    generated ones. A model of memory traffic in positions, not a measurement in bytes or seconds.
    """
    if input_tokens < 1 or output_tokens < 0:
        raise ValueError("need at least one input token and a non-negative output length")
    passes = max(0, output_tokens - 1)
    return passes * input_tokens + passes * (passes + 1) // 2


def common_prefix_len(first, second):
    """How many leading tokens two prompts share. Only that stored prefix can be read from a cache."""
    n = 0
    for a, b in zip(first, second):
        if a != b:
            break
        n += 1
    return n

"""Keep the copy of the corpus and the sample texts inside ../widget.html equal to the ones here.

    python3 embed_widget.py          rewrite the two data blocks in widget.html
    python3 embed_widget.py --check  exit 1 if widget.html differs (test_widget.py runs the same check)
"""
import json
import re
import sys
from pathlib import Path

from bpe import load_corpus
from samples import SAMPLES

WIDGET = Path(__file__).resolve().parent.parent / "widget.html"
CORPUS_BLOCK = re.compile(r'(<script type="text/plain" id="wtk-corpus">)(.*?)(</script>)', re.S)
PRESETS_BLOCK = re.compile(r'(<script type="application/json" id="wtk-presets">)(.*?)(</script>)', re.S)


def embed(html):
    """html with both data blocks rewritten from corpus.txt and samples.py."""
    corpus = load_corpus()
    if "</script" in corpus.lower() or "<!--" in corpus:
        raise ValueError("the corpus would end or confuse the script element")
    presets = json.dumps(SAMPLES, ensure_ascii=False, indent=1)
    html = CORPUS_BLOCK.sub(lambda m: m.group(1) + corpus + m.group(3), html, count=1)
    return PRESETS_BLOCK.sub(lambda m: m.group(1) + "\n" + presets + "\n" + m.group(3), html, count=1)


if __name__ == "__main__":
    current = WIDGET.read_text(encoding="utf-8")
    updated = embed(current)
    if "--check" in sys.argv:
        sys.exit(0 if updated == current else 1)
    WIDGET.write_text(updated, encoding="utf-8")
    print("widget.html data blocks now match corpus.txt and samples.py")

"""The four sample texts used by show_numbers.py, compare_tiktoken.py and the widget's presets.

None of them appears in corpus.txt, so the toy tokenizer has never seen them. The Korean sample
was written for this lesson and has not been reviewed by a native speaker.
"""
SAMPLES = {
    "English": (
        "The ferry leaves at nine, so we should pack the bags tonight and walk down to the harbour "
        "early. If the weather turns, the keeper at the hut will know before we do. Tell him we are "
        "coming, and ask whether the bridge is open."
    ),
    "Code": (
        "def average(values):\n"
        "    if not values:\n"
        "        return 0.0\n"
        "    total = 0.0\n"
        "    for value in values:\n"
        "        total += value\n"
        "    return total / len(values)\n"
        "\n"
        "\n"
        "print(average([3, 5, 8]))\n"
    ),
    "Numbers": (
        "Invoice 20260418: 3 items, 1,250.75 total, due 2026-05-02. Readings: 7.25 8.5 9.125 "
        "10.0625 11.03125. Powers of two: 4096 8192 16384 32768 65536. Id 9047215."
    ),
    "Korean": (
        "내일 아침에는 기차를 타고 바닷가에 가서 친구들과 함께 맛있는 생선 요리를 먹을 계획입니다. "
        "날씨가 좋으면 해변을 따라 걷고 저녁에는 시장에서 과일을 사 오겠습니다."
    ),
}

"""Print every number the lesson computes. Run it from this folder: python3 show_numbers.py

compare_tiktoken.py prints the numbers that come from a published tokenizer.
"""
from bpe import NUM_MERGES, encode, decode, load_corpus, pieces, train_counted, vocab_bytes
from cost import common_prefix_len, decode_positions_read, request_cost, sequential_passes
from samples import SAMPLES

corpus = load_corpus()
learned = train_counted(corpus)
merges = [pair for pair, _ in learned]
table = vocab_bytes(merges)


def words(text):
    return len(text.split())


print("== Bytes per character in UTF-8")
for ch in ("a", "\u00e9", "\ud55c", "\U0001f600"):
    print(f"  U+{ord(ch):04X} {ch!r}: {len(ch.encode('utf-8'))} bytes {list(ch.encode('utf-8'))}")
print(f"  '한국어' = {len('한국어')} characters, {len('한국어'.encode())} bytes")

print("\n== Worked example: train on the string 'aaabdaaabac' (one piece)")
tiny = train_counted("aaabdaaabac")
for k, (pair, count) in enumerate(tiny):
    tiny_table = vocab_bytes([p for p, _ in tiny[: k + 1]])
    print(f"  merge {k}: id {256 + k} = {pair[0]} + {pair[1]} = {tiny_table[256 + k]!r}, seen {count} times")
tiny_merges = [p for p, _ in tiny]
print(f"  encode -> {encode('aaabdaaabac', tiny_merges)}  (11 bytes become {len(encode('aaabdaaabac', tiny_merges))} tokens)")

print(f"\n== The corpus (corpus.txt, written for this lesson)")
chars, size = len(corpus), len(corpus.encode())
print(f"  {chars:,} characters, {size:,} bytes ({size / 1024:.1f} KiB), {len(pieces(corpus)):,} pieces, {len(set(pieces(corpus))):,} distinct")
hangul = sum(1 for c in corpus if "가" <= c <= "힣")
print(f"  Hangul syllables {hangul:,} = {hangul * 3:,} bytes ({hangul * 3 / size:.1%} of the bytes)")

print(f"\n== Training ({NUM_MERGES} merges asked for, {len(learned)} learned, vocabulary {256 + len(learned)} ids)")
for k in (0, 1, 2, 3, 4, 5, 6, 7, 8, 9):
    pair, count = learned[k]
    print(f"  merge {k}: id {256 + k} = {table[256 + k]!r}, seen {count} times")
for k in (99, 255, 511):
    pair, count = learned[k]
    print(f"  merge {k}: id {256 + k} = {table[256 + k]!r}, seen {count} times")
print(f"  smallest count among the merges: {min(c for _, c in learned)}")
longest = max((t for t in table if t.strip()), key=len)
print(f"  longest entry that is not only whitespace: {len(longest)} bytes {longest!r}")

print("\n== The four samples (none is in the corpus)")
print(f"  {'sample':8} {'chars':>5} {'bytes':>5} {'words':>5}  {'tokens@0':>8} {'tokens@512':>10} {'bytes/token':>11} {'tokens/word':>11}")
for name, text in SAMPLES.items():
    b, n0, n1 = len(text.encode()), len(encode(text, [])), len(encode(text, merges))
    assert decode(encode(text, merges), merges) == text
    print(f"  {name:8} {len(text):>5} {b:>5} {words(text):>5}  {n0:>8} {n1:>10} {b / n1:>11.2f} {n1 / words(text):>11.2f}")

print("\n== Vocabulary size: tokens needed at 0, 64, 128, 256 and 512 merges")
ks = (0, 64, 128, 256, 512)
print(f"  {'text':16} " + " ".join(f"{k:>6}" for k in ks))
rows = {**{f'{n} sample': t for n, t in SAMPLES.items()}, "the corpus": corpus}
for name, text in rows.items():
    print(f"  {name:16} " + " ".join(f"{len(encode(text, merges[:k])):>6}" for k in ks))
print("  tokens saved per extra merge, between steps (corpus | all four samples together):")
joined = "".join(SAMPLES.values())
for a, b in zip(ks, ks[1:]):
    s_corpus = len(encode(corpus, merges[:a])) - len(encode(corpus, merges[:b]))
    s_held = len(encode(joined, merges[:a])) - len(encode(joined, merges[:b]))
    print(f"    {a:>3} to {b:>3}: {s_corpus / (b - a):6.2f} | {s_held / (b - a):5.2f}")
corpus_counts = [len(encode(corpus, merges[:k])) for k in range(len(merges) + 1)]
saved = [a - b for a, b in zip(corpus_counts, corpus_counts[1:])]
short = [k for k, ((left, right), count) in enumerate(learned) if saved[k] != count]
rises = [k for k in range(1, len(saved)) if saved[k] > saved[k - 1]]
print(f"  merge counts never rise: {all(a[1] >= b[1] for a, b in zip(learned, learned[1:]))}")
print(f"  merges that save fewer tokens than their count: {len(short)}; each joins a pair with itself: "
      f"{all(learned[k][0][0] == learned[k][0][1] for k in short)}")
print(f"  a merge saves more than the one before it in {len(rises)} of {len(saved) - 1} steps; "
      f"each follows a merge that saved less than its count: {all(k - 1 in short for k in rises)}")
print("  example embedding-table size at width 4096 (an example width, not any model's):")
for name, vocab in (("this toy", 256 + len(learned)), ("50,257 ids", 50_257), ("100,277 ids", 100_277), ("200,019 ids", 200_019)):
    print(f"    {name:12}: {vocab:>7,} rows x 4096 = {vocab * 4096:>13,} numbers")

print("\n== One request (example prices, dollars per million tokens: input 2, cached input 0.2, output 10)")
cost = request_cost(500, 1500, 400, 2, "0.2", 10)
plain = request_cost(2000, 0, 400, 2, "0.2", 10)
print(f"  500 new + 1,500 cached input + 400 output tokens: {cost} dollars")
print(f"    parts: input {request_cost(500, 0, 0, 2, 0, 0)}, cached {request_cost(0, 1500, 0, 0, '0.2', 0)}, output {request_cost(0, 0, 400, 0, 0, 10)}")
print(f"    output share of the cost: {request_cost(0, 0, 400, 0, 0, 10) / cost:.1%}")
print(f"    output share of the tokens: {400 / (500 + 1500 + 400):.1%} ({400} of {500 + 1500 + 400})")
print(f"  same request, nothing cached: {plain} dollars (cost {plain / cost:.2f}x as much)")
print(f"  1,000 requests: {cost * 1000:.2f} dollars vs {plain * 1000:.2f} dollars")
print(f"  output tokens cost {10 / 2:g}x input tokens at these prices, so 1 output token = 5 input tokens")
print(f"  2,000 input + 400 output tokens: {sequential_passes(2000, 400)} sequential passes, "
      f"{decode_positions_read(2000, 400):,} positions read by the decode passes")
print(f"  400 input + 2,000 output tokens: {sequential_passes(400, 2000)} sequential passes, "
      f"{decode_positions_read(400, 2000):,} positions read by the decode passes")

print("\n== Cache prefix: how much of a prompt two requests share (toy tokenizer, 512 merges)")
SYSTEM = ("You are a support assistant for a small bakery. Answer in two sentences. "
          "Opening hours are 7 to 18 on weekdays and 8 to 14 on Saturdays. Prices are in dollars.\n")
questions = ("Do you sell rye bread?", "Is the shop open on Sunday?")
stamps = ("2026-10-18 09:14:02", "2026-10-18 09:14:09")
layouts = {
    "stable text first, then time and question": lambda q, t: SYSTEM + f"Time: {t}\nQuestion: {q}\n",
    "time first": lambda q, t: f"Time: {t}\n" + SYSTEM + f"Question: {q}\n",
}
for name, build in layouts.items():
    a, b = (encode(build(q, t), merges) for q, t in zip(questions, stamps))
    shared = common_prefix_len(a, b)
    print(f"  {name}: prompts of {len(a)} and {len(b)} tokens share {shared} ({shared / len(a):.0%} of the first)")

print("\n== Check yourself: the worked answers")
learned = train_counted("ababab")
print(f"  'ababab' merges {learned}, encodes to {encode('ababab', [p for p, _ in learned])}")
print(f"  2,000 new + 6,000 cached input + 500 output at 2 / 0.2 / 10: {request_cost(2000, 6000, 500, 2, '0.2', 10)} dollars; "
      f"nothing cached: {request_cost(8000, 0, 500, 2, '0.2', 10)} dollars")
print(f"  1,000 input + 1,000 output: {sequential_passes(1000, 1000)} passes, {decode_positions_read(1000, 1000):,} positions; "
      f"2,000 input + 1,000 output: {sequential_passes(2000, 1000)} passes, {decode_positions_read(2000, 1000):,} positions")

"""Follow one short text through the tokenizer, then price a request. Run it from this folder: python3 trace.py

It uses the lesson's own functions and adds no rules of its own. For each piece of the text it calls
encode() with one more merge allowed each time and prints what changed. The bill and the passes come
from cost.py.
"""
from bpe import encode, load_corpus, pieces, train, vocab_bytes
from cost import decode_positions_read, request_cost, sequential_passes

TEXT = "The ferry leaves at nine"
USE_MERGES = 512  # how many of the learned merges the tokenizer may use

merges = train(load_corpus())[:USE_MERGES]
table = vocab_bytes(merges)


def show(token_id):
    """The text a token stands for, or its raw bytes when it is only part of a character."""
    try:
        return table[token_id].decode("utf-8")
    except UnicodeDecodeError:
        return table[token_id]


n_pieces = len(pieces(TEXT))
print(f"text {TEXT!r}: {len(TEXT.encode('utf-8'))} bytes, {n_pieces} piece{'' if n_pieces == 1 else 's'}, {len(merges)} merges allowed")
ids = []
for piece in pieces(TEXT):
    state = encode(piece, [])
    print(f"\npiece {piece!r}: bytes {state}")
    for k in range(len(merges)):
        now = encode(piece, merges[: k + 1])
        if now != state:
            left, right = merges[k]
            print(f"  merge {k}: {left} + {right} -> {256 + k} {table[256 + k]!r}, now {now}")
            state = now
    ids.extend(state)
print(f"\ntokens: {len(ids)}, from {len(TEXT.encode('utf-8'))} bytes")
print("blocks: " + " ".join(repr(show(i)) for i in ids))

print("\nprice per million tokens (examples): new input 2, cached input 0.2, output 10 dollars")
new, cached, out = 500, 1500, 400
parts = (request_cost(new, 0, 0, 2, 0, 0), request_cost(0, cached, 0, 0, "0.2", 0), request_cost(0, 0, out, 0, 0, 10))
total = request_cost(new, cached, out, 2, "0.2", 10)
print(f"  {new:>5,} new input     at  2   = {parts[0]} dollars")
print(f"  {cached:>5,} cached input  at  0.2 = {parts[1]} dollars")
print(f"  {out:>5,} output        at 10   = {parts[2]} dollars")
print(f"  total {total} dollars; with nothing cached {request_cost(new + cached, 0, out, 2, '0.2', 10)} dollars")

print("\nsequential passes (the same 2,400 tokens, split two ways)")
for n_in, n_out in ((2000, 400), (400, 2000)):
    print(f"  {n_in:,} in + {n_out:,} out: {sequential_passes(n_in, n_out):,} passes in a row, "
          f"{decode_positions_read(n_in, n_out):,} positions read")

import random

import pytest

from bpe import (MIN_COUNT, NUM_MERGES, PIECE, _apply, decode, encode, load_corpus, pieces, train,
                 train_counted, vocab_bytes)
from samples import SAMPLES

CORPUS = load_corpus()
MERGES = train(CORPUS)


def test_worked_example_by_hand():
    """The lesson's 11-byte string. 'aa' is seen 4 times (positions 0-1, 1-2, 5-6, 6-7), so it is
    merge 0 (id 256). The string is now aa a b d aa a b a c; 'ab' is seen twice and the pair
    ('aa', 'a') twice too, and (97, 98) is the smaller tuple, so 'ab' is merge 1 (id 257). Then
    ('aa', 'ab') is seen twice: 'aaab' is merge 2 (id 258). Nothing is left that is seen twice."""
    learned = train_counted("aaabdaaabac")
    assert learned == [((97, 97), 4), ((97, 98), 2), ((256, 257), 2)]
    merges = [pair for pair, _ in learned]
    assert encode("aaabdaaabac", merges) == [258, 100, 258, 97, 99]
    assert vocab_bytes(merges)[256:] == [b"aa", b"ab", b"aaab"]


def test_check_yourself_example():
    """The quiz answer in the lesson. 'ababab' has 'ab' three times, so merge 0 is ab (id 256). The
    string is now 256 256 256, where (256, 256) is seen twice: merge 1 (id 257), applied left to
    right, leaves [257, 256]. The pair (257, 256) is seen once, so training stops."""
    assert train_counted("ababab") == [((97, 98), 3), ((256, 256), 2)]
    assert encode("ababab", train("ababab")) == [257, 256]


def test_tie_goes_to_the_smaller_pair_not_to_first_seen():
    """Guards a tie-break that depends on dict order: the widget and the code would disagree.
    In 'ba ab' the pairs (98, 97), (32, 97) and (97, 98) are each seen once."""
    assert train_counted("ba ab", 1, min_count=1) == [((32, 97), 1)]


def test_training_stops_when_no_pair_is_seen_min_count_times():
    assert train("abcd", 10) == []                       # every pair once
    assert len(train("abab", 10)) == 1                   # 'ab' twice, then ('ab', 'ab') once
    assert train("abcd", 10, min_count=1) != []          # the same text, a lower bar


def test_a_pair_run_is_merged_left_to_right():
    """'aaa' with the merge (97, 97) is [aa, a], never [a, aa]."""
    assert encode("aaa", [(97, 97)]) == [256, 97]


def test_pieces_cover_every_character_once():
    """Guards a gap or overlap in the six alternatives, which would drop or repeat text."""
    rng = random.Random(7)
    alphabet = list("abcXYZ 019,.;!?\t\r\n\x00\x1f\x7f") + ["é", "한", "\U0001f600", " ", "
"]
    texts = ["".join(rng.choice(alphabet) for _ in range(rng.randint(0, 40))) for _ in range(300)]
    texts += [CORPUS] + list(SAMPLES.values())
    assert all("".join(pieces(t)) == t for t in texts)
    assert any(len(pieces(t)) > 3 for t in texts)        # non-vacuous: texts do split


@pytest.mark.parametrize("text, expected", [
    ("the cat", ["the", " cat"]),
    ("a  b", ["a", " ", " b"]),                           # a run of spaces leaves one for the next word
    ("end  \n", ["end", "  \n"]),                         # trailing whitespace stays together
    ("x=12.5", ["x", "=", "12", ".", "5"]),
    ("한국어 ok", ["한국어", " ok"]),
])
def test_piece_examples(text, expected):
    assert pieces(text) == expected


def test_the_corpus_gives_all_the_merges_asked_for():
    """If the corpus shrinks below this, the lesson's '512 merges' and the widget's slider lie."""
    learned = train_counted(CORPUS)
    assert len(learned) == NUM_MERGES
    counts = [c for _, c in learned]
    assert min(counts) >= MIN_COUNT
    assert counts == sorted(counts, reverse=True)         # a merge cannot create a pair more common than itself


def test_round_trip_is_lossless_for_any_text():
    rng = random.Random(2026)
    alphabet = list("abcdefgh ,.0123456789\n\t") + ["é", "한", "국", "\U0001f600", "\x00", "\x7f"]
    texts = ["".join(rng.choice(alphabet) for _ in range(rng.randint(0, 60))) for _ in range(300)]
    texts += list(SAMPLES.values()) + [CORPUS[i:i + 400] for i in range(0, 4000, 800)]
    shorter = 0
    for t in texts:
        ids = encode(t, MERGES)
        assert decode(ids, MERGES) == t
        shorter += len(ids) < len(t.encode())
    assert shorter > 100                                  # non-vacuous: merges really fire


def test_lowest_rank_first_equals_replaying_the_merges_in_order():
    """The lesson says the two are the same thing; this is the check."""
    rng = random.Random(5)
    alphabet = list("the cat sat on a mat 0123,.\n") + ["\ud55c"]
    for _ in range(200):
        text = "".join(rng.choice(alphabet) for _ in range(rng.randint(1, 30)))
        replayed = []
        for piece in pieces(text):
            word = tuple(piece.encode("utf-8"))
            for k, pair in enumerate(MERGES):
                word = _apply(word, pair, 256 + k)
            replayed.extend(word)
        assert encode(text, MERGES) == replayed


def test_fewer_merges_never_make_text_shorter():
    sample = SAMPLES["English"] + SAMPLES["Code"]
    lengths = [len(encode(sample, MERGES[:k])) for k in (0, 64, 128, 256, 512)]
    assert lengths == sorted(lengths, reverse=True) and lengths[0] == len(sample.encode()) > lengths[-1]


def test_cut_bytes_decode_to_a_replacement_character_not_an_error():
    """A Korean syllable is 3 bytes. A token boundary can fall inside it."""
    assert decode([237, 149], []) == "�"
    assert decode([237, 149, 156], []) == "한"


def test_vocab_bytes_by_hand():
    table = vocab_bytes([(97, 98), (256, 99)])
    assert len(table) == 258 and table[97] == b"a" and table[256] == b"ab" and table[257] == b"abc"


def test_samples_are_not_in_the_corpus():
    """A sample the toy trained on would make the held-out counts look better than they are."""
    for name, text in SAMPLES.items():
        windows = {text[i:i + 30] for i in range(len(text) - 29)}
        assert windows and not any(w in CORPUS for w in windows), name


def test_piece_pattern_is_the_one_the_widget_expects():
    assert PIECE.pattern.count("|") == 5                  # six alternatives, as bpe.py and the widget say

from decimal import Decimal

import pytest

from cost import common_prefix_len, decode_positions_read, request_cost, sequential_passes


def test_cost_by_hand():
    """1,000 input tokens at 3 dollars per million is 0.003 dollars. 2,000 at 3 plus 500 out at 15
    is 0.006 + 0.0075 = 0.0135."""
    assert request_cost(1000, 0, 0, "3", "0.3", "15") == Decimal("0.003")
    assert request_cost(2000, 0, 500, "3", "0.3", "15") == Decimal("0.0135")


def test_cached_tokens_use_their_own_rate():
    assert request_cost(0, 1_000_000, 0, 3, "0.3", 15) == Decimal("0.3")
    assert request_cost(500, 1500, 400, 2, "0.2", 10) == Decimal("0.0053")


def test_check_yourself_values():
    """The quiz answers in the lesson: 2,000 x 2 + 6,000 x 0.2 + 500 x 10 = 4,000 + 1,200 + 5,000
    = 10,200 millionths of a dollar; with no cache 8,000 x 2 + 5,000 = 21,000."""
    assert request_cost(2000, 6000, 500, 2, "0.2", 10) == Decimal("0.0102")
    assert request_cost(8000, 0, 500, 2, "0.2", 10) == Decimal("0.021")
    assert decode_positions_read(1000, 1000) == 999 * 1000 + 999 * 1000 // 2 == 1_498_500
    assert decode_positions_read(2000, 1000) == 2_497_500
    assert sequential_passes(1000, 1000) == sequential_passes(2000, 1000) == 1000


def test_money_is_exact_where_float_is_not():
    """Guards a float sum: 0.1 + 0.2 is not 0.3 in binary, and a bill should not carry that."""
    assert request_cost(1_000_000, 1_000_000, 0, "0.1", "0.2", 0) == Decimal("0.3")


@pytest.mark.parametrize("counts, prices", [((-1, 0, 0), (1, 1, 1)), ((0, 0, 0), (1, -1, 1))])
def test_negative_input_is_refused(counts, prices):
    with pytest.raises(ValueError):
        request_cost(*counts, *prices)


def test_passes_one_per_output_token_and_the_prompt_is_one_pass():
    assert sequential_passes(2000, 500) == 500
    assert sequential_passes(5, 1) == 1
    assert sequential_passes(5, 0) == 1                   # the prompt pass still happens
    assert sequential_passes(50_000, 3) == sequential_passes(5, 3)   # prompt length does not add passes


def test_decode_positions_by_hand():
    """3 prompt tokens, 4 output tokens: decode passes 1, 2, 3 read 3+1, 3+2, 3+3 = 4 + 5 + 6 = 15."""
    assert decode_positions_read(3, 4) == 15
    assert decode_positions_read(2000, 500) == 499 * 2000 + 499 * 500 // 2 == 1_122_750
    assert decode_positions_read(7, 0) == decode_positions_read(7, 1) == 0


def test_decode_positions_grow_faster_than_output_length():
    """Doubling the output more than doubles the reading: the reason long outputs are costly."""
    assert decode_positions_read(100, 2000) > 2 * decode_positions_read(100, 1000)


def test_common_prefix_len():
    assert common_prefix_len([1, 2, 3, 4], [1, 2, 9, 4]) == 2
    assert common_prefix_len([1, 2], [1, 2, 3]) == 2
    assert common_prefix_len([], [1]) == 0

"""Guards for ../widget.html: its data blocks, its size, and that its tokenizer counts like bpe.py."""
import json
import random
import re
import subprocess
from pathlib import Path

from bpe import NUM_MERGES, encode, load_corpus, train_counted
from cost import decode_positions_read, request_cost, sequential_passes
import embed_widget
from embed_widget import WIDGET, embed
from samples import SAMPLES

HTML = WIDGET.read_text(encoding="utf-8")

# Reads the tokenizer and bill code out of the widget between its marker comments, runs it with
# stub elements, and compares with the numbers Python wrote into the fixture.
PARITY = r"""
import fs from 'node:fs';
const [fixture, widget] = process.argv.slice(2);
const fx = JSON.parse(fs.readFileSync(fixture, 'utf8'));
const html = fs.readFileSync(widget, 'utf8');
const corpus = html.match(/<script type="text\/plain" id="wtk-corpus">([\s\S]*?)<\/script>/)[1];
const presets = html.match(/<script type="application\/json" id="wtk-presets">([\s\S]*?)<\/script>/)[1];
const js = html.slice(html.indexOf('/* ---------- the tokenizer'), html.indexOf('/* ---------- state'));
const make = new Function('$', 'document', "'use strict';" + js + '; return {train, encode, decode, learned, bill, passes, positions};');
const data = (id) => ({ textContent: id === 'wtk-corpus' ? corpus : presets });
const api = make(data, { getElementById: data });
api.train();
const bad = [];
if (JSON.stringify(api.learned) !== JSON.stringify(fx.merges)) bad.push('merges differ');
let checks = 0;
fx.texts.forEach((t, i) => {
  for (const k of fx.ks) {
    checks++;
    if (JSON.stringify(api.encode(t, k)) !== JSON.stringify(fx.expected[i][String(k)])) bad.push(['encode', t, k]);
  }
  if (api.decode(api.encode(t, fx.ks[fx.ks.length - 1])) !== t) bad.push(['round trip', t]);
});
fx.bills.forEach((b) => {
  const r = api.bill({ nin: b.nin, ncache: b.ncache, nout: b.nout, pin: b.p[0], pcache: b.p[1], pout: b.p[2] });
  if (Math.abs(r.total - Number(b.cost)) > 1e-12) bad.push(['bill', b]);
  if (api.passes(b.nout) !== b.passes) bad.push(['passes', b]);
  if (api.positions(b.nin + b.ncache, b.nout) !== b.positions) bad.push(['positions', b]);
});
console.log(JSON.stringify({ checks, bad: bad.slice(0, 5) }));
process.exit(bad.length ? 1 : 0);
"""


def test_widget_data_blocks_match_corpus_and_samples():
    """Guards a corpus or sample edit that was not copied into the widget (run embed_widget.py)."""
    assert embed(HTML) == HTML


def test_every_element_the_script_looks_up_exists_where_it_looks():
    """Guards a widget that never starts: the parity harness stubs $, so a lookup of an element
    outside .wtk-root (the data blocks sit after it) passed here and threw in the browser."""
    root = HTML[HTML.index('<div class="wtk-root">'):HTML.index("<script")]
    script = HTML[HTML.index("<script>"):]
    lookups = set(re.findall(r"\$\('([\w-]+)'\)", script))
    assert lookups and all(f'id="{i}"' in root for i in lookups), sorted(i for i in lookups if f'id="{i}"' not in root)
    assert "$('wtk-corpus')" not in script and "$('wtk-presets')" not in script


def test_corpus_is_safe_to_embed_in_a_script_element():
    corpus = load_corpus()
    assert "\r" not in corpus and "</script" not in corpus.lower() and "<!--" not in corpus


def test_widget_is_small_and_asks_for_nothing_online():
    """The corpus holds a code sample that mentions fetch(), so look at the page without its data blocks."""
    assert len(HTML.encode("utf-8")) < 120 * 1024
    page = embed_widget.CORPUS_BLOCK.sub("", embed_widget.PRESETS_BLOCK.sub("", HTML))
    for banned in ("http://", "https://", "fetch(", "XMLHttpRequest", "WebSocket", "sendBeacon", "import("):
        assert banned not in page, banned
    assert " src=" not in page and "@import" not in page


def test_widget_tokenizer_and_bill_match_the_python_code(tmp_path):
    """Guards the widget's JavaScript drifting from bpe.py and cost.py: its counts must be the lesson's."""
    corpus = load_corpus()
    learned = train_counted(corpus)
    merges = [pair for pair, _ in learned]
    assert len(merges) == NUM_MERGES
    rng = random.Random(11)
    alphabet = list("abc the 0123456789,.;\n\t  ") + ["é", "한", "국", "\U0001f600", "\x00", "\x7f", " "]
    texts = list(SAMPLES.values()) + [corpus[i:i + 300] for i in range(0, 3000, 500)]
    texts += ["", " ", "\n\n", "a  b", "end  \n", "한국어 ok"]
    # The page's text box turns CRLF into LF and stops at 4,000 UTF-16 units, but the tokenizer itself must
    # agree with bpe.py on CRLF, combining marks, decomposed Hangul and 4,000 characters as they are.
    texts += ["one\r\ntwo\r\n\r\nthree", "a\r\n", "e\u0301 cafe\u0301", "\u1112\u1161\u11ab\u1100\u1173\u11af", corpus[:4000]]
    texts += ["".join(rng.choice(alphabet) for _ in range(rng.randint(1, 50))) for _ in range(80)]
    ks = [0, 1, 100, 300, NUM_MERGES]
    bills = []
    for nin, ncache, nout in [(500, 1500, 400), (0, 0, 0), (1, 0, 1), (123456, 7, 99999)]:
        p = ["2", "0.2", "10"]
        cost = request_cost(nin, ncache, nout, *p)
        allin = max(1, nin + ncache)
        bills.append({"nin": nin, "ncache": ncache, "nout": nout, "p": [float(x) for x in p], "cost": str(cost),
                      "passes": sequential_passes(allin, nout), "positions": decode_positions_read(allin, nout)})
    fixture = {"merges": [[l, r, n] for (l, r), n in learned], "texts": texts, "ks": ks, "bills": bills,
               "expected": [{str(k): encode(t, merges[:k]) for k in ks} for t in texts]}
    (tmp_path / "fixture.json").write_text(json.dumps(fixture), encoding="utf-8")
    (tmp_path / "parity.mjs").write_text(PARITY, encoding="utf-8")
    run = subprocess.run(["node", str(tmp_path / "parity.mjs"), str(tmp_path / "fixture.json"), str(WIDGET)],
                         capture_output=True, text=True, timeout=120)
    assert run.returncode == 0, run.stdout + run.stderr
    assert json.loads(run.stdout)["checks"] == len(texts) * len(ks) >= 400