#!/usr/bin/env python3
"""Router Gauntlet task generator.

Every task is procedurally generated from SEED, so none of them can exist in any
model's training data. Each has a deterministic gold answer or hidden test suite.
Tiers: easy (a router should send these somewhere cheap), medium, hard.
Writes tasks.json (public prompts + private gold) next to this file.
"""
import heapq, itertools, json, random, sys
from pathlib import Path

SEED = int(sys.argv[1]) if len(sys.argv) > 1 else 20261006
R = random.Random(SEED)
ANS = "\n\nThink as long as you need, then give ONLY the final answer inside <answer></answer> tags."
CODE = "\n\nReply with a single ```python code block containing the complete function (stdlib only, no I/O, no tests)."
tasks = []

def add(tid, tier, kind, prompt, gold):
    tasks.append({"id": tid, "tier": tier, "kind": kind, "prompt": prompt, "gold": gold})

# ---------------------------------------------------------------- EASY
# E1 extraction
vendor = R.choice(["Quillfern Supply", "Ostrava Kettleworks", "Brindlemoor Labs", "Pellucid Ferry Co."])
items = [(R.choice(["bolts", "gaskets", "lanterns", "rope", "sealant", "hinges"]), R.randint(2, 9), R.randint(3, 40)) for _ in range(3)]
total = sum(q * p for _, q, p in items)
due = f"2026-{R.randint(10, 12):02d}-{R.randint(10, 28):02d}"
lines = "\n".join(f"  {q} x {n} @ ${p}.00" for n, q, p in items)
add("E1", "easy", "json",
    f"From this note, extract vendor, total (integer dollars, compute it), and due date (YYYY-MM-DD).\n\n"
    f"\"Hey, got the bill from {vendor} today. Lines:\n{lines}\nNo tax. They want it paid by {due}.\"\n\n"
    'Answer as JSON {"vendor": str, "total": int, "due": str}.' + ANS,
    {"vendor": vendor, "total": total, "due": due})

# E2 classification into invented categories
cats = {"GLINT": "anything about being charged money", "MOSS": "login or password trouble",
        "TARN": "a physical item arrived damaged", "WREN": "a feature request"}
pool = [("I was billed twice this month.", "GLINT"), ("Reset link never arrives in my inbox.", "MOSS"),
        ("The mug came cracked in the box.", "TARN"), ("Could you add a dark mode?", "WREN"),
        ("Why is there a $4 fee on my statement?", "GLINT"), ("2FA code keeps getting rejected.", "MOSS"),
        ("Box was crushed and the lamp shade is bent.", "TARN"), ("Please let me export to CSV.", "WREN")]
R.shuffle(pool); pick = pool[:6]
add("E2", "easy", "list",
    "Categories:\n" + "\n".join(f"- {k}: {v}" for k, v in cats.items()) +
    "\n\nLabel each ticket in order:\n" + "\n".join(f"{i+1}. {t}" for i, (t, _) in enumerate(pick)) +
    "\n\nAnswer as a comma-separated list of labels, e.g. GLINT,MOSS,..." + ANS,
    [c for _, c in pick])

# E3 arithmetic word problem
a, b, c = R.randint(12, 60), R.randint(3, 9), R.randint(5, 25)
add("E3", "easy", "int",
    f"A ferry carries {a} crates per trip and makes {b} trips a day. On the last day of a 4-day week it skips "
    f"the final trip, and {c} crates are rejected at inspection over the whole week. How many crates passed inspection that week?" + ANS,
    a * b * 4 - a - c)

# E4 sort by invented rule
words = R.sample(["harbor", "quiver", "lintel", "mosaic", "fjord", "ember", "tundra", "velvet", "cobalt", "saffron"], 6)
gold = sorted(words, key=lambda w: (w[-1], len(w), w))
add("E4", "easy", "list",
    f"Sort these words by their LAST letter (a→z); break ties by length (shorter first), then alphabetically: {', '.join(words)}."
    " Answer as a comma-separated list." + ANS, gold)

# ---------------------------------------------------------------- GLYPH (invented stack language)
GLYPH_SPEC = """GLYPH is a stack language over Python integers. Tokens run left to right:
- an integer literal: push it
- dup: copy top | drop: pop top | swap: swap top two | over: copy second-from-top to top
- rot: (a b c -> b c a)  i.e. third-from-top moves to top
- add, sub, mul: pop b then a, push a+b / a-b / a*b
- mod: pop b then a, push a mod b using floored modulo (Python %), b is never 0
- zig: pop a; push a*3+1 if a is odd, else a//2 (floor division)
- rep N [ ... ]: run the bracketed body N times
- ifz [ ... ]: pop a; run the body only if a == 0
The program starts with an empty stack."""

def glyph_run(toks):
    st = []
    def run(ts):
        i = 0
        while i < len(ts):
            t = ts[i]
            if isinstance(t, tuple):
                if t[0] == "rep":
                    for _ in range(t[1]): run(t[2])
                else:
                    if st.pop() == 0: run(t[1])
            elif isinstance(t, int): st.append(t)
            elif t == "dup": st.append(st[-1])
            elif t == "drop": st.pop()
            elif t == "swap": st[-1], st[-2] = st[-2], st[-1]
            elif t == "over": st.append(st[-2])
            elif t == "rot": st.append(st.pop(-3))
            elif t == "zig": x = st.pop(); st.append(x * 3 + 1 if x % 2 else x // 2)
            else:
                y = st.pop(); x = st.pop()
                st.append({"add": x + y, "sub": x - y, "mul": x * y, "mod": x % y}[t])
            if st and abs(st[-1]) > 10**6: raise OverflowError
            i += 1
    run(toks); return st

def glyph_fmt(toks):
    out = []
    for t in toks:
        if isinstance(t, tuple):
            out.append(f"rep {t[1]} [ {glyph_fmt(t[2])} ]" if t[0] == "rep" else f"ifz [ {glyph_fmt(t[1])} ]")
        else: out.append(str(t))
    return " ".join(out)

def glyph_gen(n, nested):
    while True:
        def body(n, depth):
            ts = []
            for _ in range(n):
                r = R.random()
                if nested and depth == 0 and r < 0.15:
                    ts.append(("rep", R.randint(2, 4), body(R.randint(2, 4), 1)))
                elif nested and depth == 0 and r < 0.25:
                    ts.append(R.randint(0, 2)); ts.append(("ifz", body(R.randint(1, 3), 1)))
                elif r < 0.45: ts.append(R.randint(1, 12))
                else: ts.append(R.choice(["dup", "swap", "over", "rot", "add", "sub", "mul", "mod", "zig", "drop"]))
            return ts
        toks = [R.randint(2, 9), R.randint(2, 9), R.randint(2, 9)] + body(n, 0)
        try:
            st = glyph_run(toks)
            if st and len(st) <= 6 and len(glyph_fmt(toks).split()) >= n:
                if "mod" in glyph_fmt(toks) and all(not (isinstance(t, int) and t == 0) for t in []):
                    return toks, st
        except (IndexError, OverflowError, ZeroDivisionError):
            pass

for tid, tier, n, nested in [("M1", "medium", 14, False), ("H1", "hard", 22, True)]:
    toks, st = glyph_gen(n, nested)
    add(tid, tier, "intlist", GLYPH_SPEC + f"\n\nProgram:\n{glyph_fmt(toks)}\n\nWhat is the final stack, bottom to top? "
        "Answer as a comma-separated list of integers." + ANS, st)

# ---------------------------------------------------------------- M2 code: ripple
def ripple(xs):
    n = len(xs)
    if not n: return []
    out = []
    for i in range(n):
        d = next((j - i for j in range(i + 1, n) if xs[j] >= xs[i]), 0)
        out.append(xs[i] + d)
    k = sum(xs) % n
    return out[k:] + out[:k]
cases = [[], [5], [3, 3], [1, 2, 3], [3, 2, 1], [-4, 7, -1, 0], [0, 0, 0, 0, 0]]
cases += [[R.randint(-20, 20) for _ in range(R.randint(1, 12))] for _ in range(30)]
add("M2", "medium", "code",
    "Write `ripple(xs: list[int]) -> list[int]`:\n"
    "1. For each index i, let d be (j - i) for the smallest j > i with xs[j] >= xs[i], or 0 if no such j. Set out[i] = xs[i] + d.\n"
    "2. Let k = sum(xs) mod len(xs) (Python floored modulo). Return out rotated LEFT by k positions.\n"
    "An empty list returns []." + CODE,
    {"func": "ripple", "cases": [[c, ripple(c)] for c in cases]})

# ---------------------------------------------------------------- M3 invented calendar
MONTHS = [("Ashen", 31), ("Brine", 28), ("Cinder", 30), ("Dross", 33), ("Ember", 29), ("Fallow", 31), ("Gale", 30)]
def leap(y): return y % 5 == 0 and y % 40 != 0
def mlen(m, y): return MONTHS[m][1] + (2 if m == 1 and leap(y) else 0)
d0, m0, y0, N = R.randint(1, 28), R.randrange(7), R.randint(1100, 1130), R.randint(900, 2600)
d, m, y = d0, m0, y0
for _ in range(N):
    d += 1
    if d > mlen(m, y):
        d, m = 1, m + 1
        if m == 7: m, y = 0, y + 1
add("M3", "medium", "str",
    "The Veltrine calendar has 7 months in order: " + ", ".join(f"{n} ({l} days)" for n, l in MONTHS) +
    ". In a leap year Brine has 30 days instead of 28. A year is leap if divisible by 5 but not by 40.\n"
    f"What date is {N} days after {d0} {MONTHS[m0][0]} {y0}? Answer in the form `<day> <Month> <year>`, e.g. 4 Cinder 1112." + ANS,
    f"{d} {MONTHS[m][0]} {y}")

# ---------------------------------------------------------------- logic grids
def grid(tid, tier, n):
    names = R.sample(["Ilsa", "Bram", "Corin", "Dagny", "Evander", "Fenna", "Gideon"], n)
    colors = R.sample(["teal", "ochre", "plum", "slate", "coral", "olive"], n)
    drinks = R.sample(["kvass", "mate", "lassi", "horchata", "sbiten", "chicha"], n)
    sol = (tuple(R.sample(names, n)), tuple(R.sample(colors, n)), tuple(R.sample(drinks, n)))  # index = house-1
    def pos(assign, cat, v): return assign[cat].index(v)
    def make():
        k = R.randrange(6); cat = R.randrange(3); cat2 = R.randrange(3)
        v = R.choice(sol[cat]); w = R.choice(sol[cat2]); hv = sol[cat].index(v); hw = sol[cat2].index(w)
        lab = ["", "the {} house", "the {} drinker"]
        def L(c, x): return x if c == 0 else lab[c].format(x)
        if k == 0 and R.random() < 0.8: return None
        if k == 0: return (f"{L(cat, v)} is in house {hv+1}.", lambda a, c=cat, v=v, h=hv: pos(a, c, v) == h)
        if k == 1 and hv + 1 == hw: return (f"{L(cat, v)} is immediately left of {L(cat2, w)}.", lambda a, c=cat, v=v, c2=cat2, w=w: pos(a, c, v) + 1 == pos(a, c2, w))
        if k == 2 and hv < hw: return (f"{L(cat, v)} is somewhere left of {L(cat2, w)}.", lambda a, c=cat, v=v, c2=cat2, w=w: pos(a, c, v) < pos(a, c2, w))
        if k == 3 and hv != hw: return (f"{L(cat, v)} is not the same house as {L(cat2, w)}.", lambda a, c=cat, v=v, c2=cat2, w=w: pos(a, c, v) != pos(a, c2, w))
        if k == 4 and hv == hw and cat != cat2: return (f"{L(cat, v)} is the same house as {L(cat2, w)}.", lambda a, c=cat, v=v, c2=cat2, w=w: pos(a, c, v) == pos(a, c2, w))
        if k == 5 and abs(hv - hw) == 1: return (f"{L(cat, v)} is next to {L(cat2, w)}.", lambda a, c=cat, v=v, c2=cat2, w=w: abs(pos(a, c, v) - pos(a, c2, w)) == 1)
        return None
    cands = [(p, q, r) for p in itertools.permutations(names) for q in itertools.permutations(colors) for r in itertools.permutations(drinks)]
    clues = []
    while len(cands) > 1:
        c = make()
        if not c: continue
        nc = [a for a in cands if c[1](a)]
        if len(nc) < len(cands): clues.append(c); cands = nc
    # drop redundant clues (direct "in house k" giveaways first) so it needs real deduction
    allc = [(p, q, r) for p in itertools.permutations(names) for q in itertools.permutations(colors) for r in itertools.permutations(drinks)]
    for c in sorted(clues, key=lambda c: " is in house " not in c[0]):
        rest = [x for x in clues if x is not c]
        left = allc
        for x in rest:
            left = [a for a in left if x[1](a)]
            if len(left) <= 1: break
        if len(left) == 1: clues = rest
    assert cands[0] == sol
    R.shuffle(clues)
    gold = {str(h + 1): {"name": sol[0][h], "color": sol[1][h], "drink": sol[2][h]} for h in range(n)}
    add(tid, tier, "grid",
        f"{n} houses stand in a row, numbered 1 (left) to {n} (right). Each has one resident (names: {', '.join(sorted(names))}), "
        f"one color ({', '.join(sorted(colors))}), and the resident drinks one drink ({', '.join(sorted(drinks))}); all distinct.\n\nClues:\n" +
        "\n".join(f"{i+1}. {c[0][0].upper() + c[0][1:]}" for i, c in enumerate(clues)) +
        '\n\nThere is exactly one solution. Answer as JSON {"1": {"name":..,"color":..,"drink":..}, "2": ...}.' + ANS, gold)
grid("M4", "medium", 4)
grid("H4", "hard", 5)

# ---------------------------------------------------------------- H2 code: vault grid shortest path
def vault(grid):
    g = [list(r) for r in grid]; H = len(g); W = len(g[0]) if H else 0
    S = E = None; portals = []
    for r in range(H):
        for c in range(W):
            if g[r][c] == "S": S = (r, c)
            if g[r][c] == "E": E = (r, c)
            if g[r][c] == "*": portals.append((r, c))
    if S is None or E is None: return -1
    dist = {(S, 0): 0}; pq = [(0, S, 0)]
    while pq:
        dcur, p, keys = heapq.heappop(pq)
        if dist.get((p, keys)) != dcur: continue
        if p == E: return dcur
        nbrs = []
        r, c = p
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < H and 0 <= nc < W:
                ch = g[nr][nc]
                if ch == "#": continue
                if ch in "ABC" and not keys & (1 << "ABC".index(ch)): continue
                cost = 1 + (int(ch) if ch.isdigit() else 0)
                nbrs.append(((nr, nc), cost))
        if g[r][c] == "*" and len(portals) == 2:
            nbrs.append((portals[1] if p == portals[0] else portals[0], 0))
        for q, cost in nbrs:
            ch = g[q[0]][q[1]]
            nk = keys | (1 << "abc".index(ch)) if ch in "abc" else keys
            nd = dcur + cost
            if nd < dist.get((q, nk), 1 << 60):
                dist[(q, nk)] = nd; heapq.heappush(pq, (nd, q, nk))
    return -1
def rand_vault():
    H, W = R.randint(4, 9), R.randint(4, 9)
    cells = [["." if R.random() < 0.62 else R.choice("#####123456789") for _ in range(W)] for _ in range(H)]
    free = [(r, c) for r in range(H) for c in range(W)]
    R.shuffle(free)
    specials = ["S", "E"] + R.sample(["a", "A", "b", "B", "c", "C"], R.randint(0, 6)) + (["*", "*"] if R.random() < 0.6 else [])
    for ch, (r, c) in zip(specials, free): cells[r][c] = ch
    return ["".join(row) for row in cells]
vcases = [["S.E"], ["S#E"], ["SA.", "##.", "a.E"], ["S9E"], ["S.#.E"], ["*#####", "S#..E*"]]
vcases += [rand_vault() for _ in range(40)]
add("H2", "hard", "code",
    "Write `vault(grid: list[str]) -> int`: minimum total cost to walk from 'S' to 'E', or -1 if impossible.\n"
    "Rules: move up/down/left/right, one cell at a time, staying in the grid. '#' is a wall. Entering any cell costs 1, "
    "plus d extra if the cell is a digit d (1-9). Lowercase a/b/c are keys: entering one picks it up permanently. "
    "Uppercase A/B/C are doors: you may enter only if you already hold the matching lowercase key. "
    "If there are exactly two '*' cells they are linked portals: while standing on one you may jump to the other at cost 0 "
    "(you may also just walk over them; with any other number of '*' they are plain floor). 'S', 'E', '.' are plain floor. "
    "Reaching E ends the walk. Grids are rectangular and may be up to 9x9." + CODE,
    {"func": "vault", "cases": [[[c], vault(c)] for c in vcases]})

# ---------------------------------------------------------------- H3 scheduling with an invented exclusion resource
J = 8
while True:
  dur = {f"J{i}": R.randint(1, 6) for i in range(1, J + 1)}
  jobs = list(dur)
  prec = set()
  while len(prec) < 7:
      a, b = sorted(R.sample(range(J), 2)); prec.add((jobs[a], jobs[b]))
  hot = set(R.sample(jobs, 3))
  def sgs(order):
      start = {}
      for j in order:
          t = max([start[a] + dur[a] for a, b in prec if b == j and a in start] + [0])
          while True:
              ok = all(sum(1 for k in start if start[k] <= tt < start[k] + dur[k]) < 2 and
                       not (j in hot and any(k in hot and start[k] <= tt < start[k] + dur[k] for k in start))
                       for tt in range(t, t + dur[j]))
              if ok: break
              t += 1
          start[j] = t
      return start
  best = None
  for order in itertools.permutations(jobs):
      pos = {j: i for i, j in enumerate(order)}
      if any(pos[a] > pos[b] for a, b in prec): continue
      s = sgs(order); ms = max(s[j] + dur[j] for j in jobs)
      if best is None or ms < best: best = ms
  if best > -(-sum(dur.values()) // 2) + 1: break
add("H3", "hard", "sched",
    f"Schedule {J} jobs on 2 identical machines (each machine runs one job at a time; jobs run without interruption; times are integers starting at 0).\n"
    "Durations: " + ", ".join(f"{j}={d}" for j, d in dur.items()) + ".\n"
    "Precedence (X before Y means Y starts no earlier than X finishes): " + ", ".join(f"{a} before {b}" for a, b in sorted(prec)) + ".\n"
    f"Heat rule: the 'hot' jobs {', '.join(sorted(hot))} may never run at the same time as each other.\n"
    'Minimize the makespan (latest finish time). Answer as JSON mapping each job to its start time, e.g. {"J1": 0, ...}.' + ANS,
    {"dur": dur, "prec": sorted(prec), "hot": sorted(hot), "machines": 2, "optimal": best})

# ================================================================ EXTREME tier (added after the first run hit a ceiling)
# X1 long GLYPH with nesting
toks, st = glyph_gen(48, True)
add("X1", "extreme", "intlist", GLYPH_SPEC + f"\n\nProgram:\n{glyph_fmt(toks)}\n\nWhat is the final stack, bottom to top? "
    "Answer as a comma-separated list of integers." + ANS, st)

# X2 calendar + 9-day week, large offset
WEEK = ["Ord", "Pell", "Quist", "Rhee", "Sorn", "Tavi", "Ulm", "Vane", "Wick"]
d0, m0, y0 = R.randint(1, 28), R.randrange(7), R.randint(1210, 1240)
N = R.randint(30000, 45000)
wd0 = R.randrange(9)
d, m, y = d0, m0, y0
for _ in range(N):
    d += 1
    if d > mlen(m, y):
        d, m = 1, m + 1
        if m == 7: m, y = 0, y + 1
add("X2", "extreme", "str",
    "The Veltrine calendar has 7 months in order: " + ", ".join(f"{n} ({l} days)" for n, l in MONTHS) +
    ". In a leap year Brine has 30 days instead of 28. A year is leap if divisible by 5 but not by 40. "
    "Veltrine weeks have 9 days in order: " + ", ".join(WEEK) + f" (then back to {WEEK[0]}).\n"
    f"{d0} {MONTHS[m0][0]} {y0} was a {WEEK[wd0]}. What are the date and weekday {N} days later? "
    "Answer in the form `<Weekday> <day> <Month> <year>`, e.g. Rhee 4 Cinder 1112." + ANS,
    f"{WEEK[(wd0 + N) % 9]} {d} {MONTHS[m][0]} {y}")

# X3 code: vault with consumable keys and single-use key cells
def vault2(grid):
    g = grid; H = len(g); W = len(g[0]) if H else 0
    cells = {(r, c): g[r][c] for r in range(H) for c in range(W)}
    S = next((p for p, ch in cells.items() if ch == "S"), None); E = next((p for p, ch in cells.items() if ch == "E"), None)
    if S is None or E is None: return -1
    keys = sorted(p for p, ch in cells.items() if ch in "abc"); doors = sorted(p for p, ch in cells.items() if ch in "ABC")
    kid = {p: i for i, p in enumerate(keys)}; did = {p: i for i, p in enumerate(doors)}
    def held(pk, od, L):
        return sum(1 for p in keys if pk >> kid[p] & 1 and cells[p] == L) - sum(1 for p in doors if od >> did[p] & 1 and cells[p] == L.upper())
    start = (S, 0, 0); dist = {start: 0}; pq = [(0, S, 0, 0)]
    while pq:
        dc, p, pk, od = heapq.heappop(pq)
        if dist.get((p, pk, od)) != dc: continue
        if p == E: return dc
        for dr, dd in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            q = (p[0] + dr, p[1] + dd); ch = cells.get(q)
            if ch is None or ch == "#": continue
            npk, nod = pk, od
            if ch in "ABC" and not (od >> did[q] & 1):
                if held(pk, od, ch.lower()) <= 0: continue
                nod = od | 1 << did[q]
            if ch in "abc": npk = pk | 1 << kid[q]
            cost = 1 + (int(ch) if ch.isdigit() else 0)
            st = (q, npk, nod); nd = dc + cost
            if nd < dist.get(st, 1 << 60): dist[st] = nd; heapq.heappush(pq, (nd, q, npk, nod))
    return -1
def rand_vault2():
    H, W = R.randint(5, 10), R.randint(5, 10)
    cells = [["." if R.random() < 0.6 else R.choice("####123456789") for _ in range(W)] for _ in range(H)]
    free = [(r, c) for r in range(H) for c in range(W)]; R.shuffle(free)
    specials = ["S", "E"] + [R.choice("abc") for _ in range(R.randint(1, 4))] + [R.choice("ABC") for _ in range(R.randint(1, 4))]
    for ch, (r, c) in zip(specials, free): cells[r][c] = ch
    return ["".join(row) for row in cells]
v2 = [["SaAAE"], ["SaaAAE"], ["SA", "aE"], ["aSAbBE"], ["S.a", "#A#", "EA."], ["Sa.", "AAE"]]
diff, same = [], []
while len(diff) < 34 or len(same) < 26:
    gv = rand_vault2(); a2 = vault2(gv); a1 = vault(gv)
    if a2 != a1 and len(diff) < 34: diff.append(gv)
    elif a2 == a1 and a2 != -1 and len(same) < 26: same.append(gv)
v2 += diff + same  # 'diff' cases only pass if keys are really consumed / key cells single-use
add("X3", "extreme", "code",
    "Write `vault2(grid: list[str]) -> int`: minimum total cost to walk from 'S' to 'E', or -1 if impossible.\n"
    "Rules: move up/down/left/right one cell at a time inside the grid. '#' is a wall. Entering any cell costs 1, plus d extra if the cell is a digit d (1-9); "
    "re-entering a digit cell costs the same again.\n"
    "Lowercase a/b/c are key cells. The FIRST time you enter a given key cell you pick up one key of that letter; that cell gives nothing on later visits "
    "(it then acts as plain floor). You can carry any number of keys.\n"
    "Uppercase A/B/C are doors. The first time you enter a given door cell you must spend (consume) one matching key you are carrying; if you have none you cannot enter. "
    "Once a particular door cell has been opened it stays open and can be re-entered for free (no key). Each door cell is opened separately.\n"
    "'S', 'E', '.' are plain floor. Reaching E ends the walk. Grids are rectangular, up to 10x10, with at most 4 key cells and 4 door cells." + CODE,
    {"func": "vault2", "cases": [[[c], vault2(c)] for c in v2]})

# X4 bigger schedule: 9 jobs, 2 machines, hot rule, release times
while True:
    dur = {f"J{i}": R.randint(1, 7) for i in range(1, 10)}; jobs = list(dur)
    prec = set()
    while len(prec) < 8:
        a, b = sorted(R.sample(range(9), 2)); prec.add((jobs[a], jobs[b]))
    hot = set(R.sample(jobs, 3)); rel = {j: (R.choice([0, 0, 0, 2, 4, 6]) ) for j in jobs}
    def sgs(order):
        start = {}
        for j in order:
            t = max([start[a] + dur[a] for a, b in prec if b == j and a in start] + [rel[j]])
            while not all(sum(1 for k in start if start[k] <= tt < start[k] + dur[k]) < 2 and
                          not (j in hot and any(k in hot and start[k] <= tt < start[k] + dur[k] for k in start))
                          for tt in range(t, t + dur[j])): t += 1
            start[j] = t
        return start
    best = None
    for order in itertools.permutations(jobs):
        pos = {j: i for i, j in enumerate(order)}
        if any(pos[a] > pos[b] for a, b in prec): continue
        s_ = sgs(order); ms = max(s_[j] + dur[j] for j in jobs)
        if best is None or ms < best: best = ms
    lb = max(-(-sum(dur.values()) // 2), sum(dur[j] for j in hot))
    if best > lb: break
add("X4", "extreme", "sched",
    "Schedule 9 jobs on 2 identical machines (each machine runs one job at a time; jobs run without interruption; times are integers starting at 0).\n"
    "Durations: " + ", ".join(f"{j}={d}" for j, d in dur.items()) + ".\n"
    "Release times (a job may not start before this): " + ", ".join(f"{j}={r}" for j, r in rel.items() if r) + " (all others 0).\n"
    "Precedence (X before Y means Y starts no earlier than X finishes): " + ", ".join(f"{a} before {b}" for a, b in sorted(prec)) + ".\n"
    f"Heat rule: the 'hot' jobs {', '.join(sorted(hot))} may never run at the same time as each other.\n"
    'Minimize the makespan (latest finish time). Answer as JSON mapping each job to its start time, e.g. {"J1": 0, ...}.' + ANS,
    {"dur": dur, "prec": sorted(prec), "hot": sorted(hot), "rel": rel, "machines": 2, "optimal": best})

out = Path(__file__).with_name("tasks.json")
out.write_text(json.dumps({"seed": SEED, "tasks": tasks}, indent=1))
print(f"wrote {len(tasks)} tasks, seed {SEED}")
for t in tasks: print(t["id"], t["tier"], t["kind"], len(t["prompt"]), "chars")