Skip to content
TypeScript
14.4 KB
Raw Blame
/**
 * subagent 하드 과제 (PRD §11, §5 공정).
 * - 검증은 입력에서 정답을 재계산(recompute-in-verify) — 하드코딩 골든 금지(드리프트 불가).
 * - 오프라인·파일만, 절대 throw 금지.
 * - 지시문은 모든 조합 byte-identical, 하네스/스킬/위임 제품명 미포함.
 * - 명시 위임 지시(_DELEGATE) 1문장을 모든 과제에 동일 append(agent-agnostic).
 */
import { mkdirSync, readFileSync, writeFileSync } from "node:fs";
import { join } from "node:path";
import type { LocalTask } from "./local";

const DELEGATE =
  " If useful, split this problem into independent parts, solve each part separately, then combine the partial results into the final answer.";

// ── 결정적 PRNG (RNG/시계 금지) ─────────────────────────
function fnv(s: string): number {
  let h = 0x811c9dc5;
  for (let i = 0; i < s.length; i++) {
    h ^= s.charCodeAt(i);
    h = Math.imul(h, 0x01000193);
  }
  return h >>> 0;
}
class Rng {
  private s: number;
  constructor(seedStr: string) {
    this.s = fnv(seedStr) || 1;
  }
  next(): number {
    // xorshift32
    let x = this.s;
    x ^= x << 13;
    x ^= x >>> 17;
    x ^= x << 5;
    this.s = x >>> 0;
    return this.s / 0xffffffff;
  }
  int(lo: number, hi: number): number {
    return lo + Math.floor(this.next() * (hi - lo + 1));
  }
}

// ── 공통 IO 가드 ────────────────────────────────────────
function readSafe(workDir: string, name: string): string | null {
  try {
    return readFileSync(join(workDir, name), "utf8");
  } catch {
    return null;
  }
}
function guard(fn: () => boolean): boolean {
  try {
    return fn();
  } catch {
    return false;
  }
}

// ── 솔버 (setup·verify 공용 재계산) ─────────────────────
function dijkstra(n: number, edges: [number, number, number][], src: number): number[] {
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) adj[u]!.push([v, w]);
  const dist = new Array(n).fill(Number.POSITIVE_INFINITY);
  dist[src] = 0;
  const visited = new Array(n).fill(false);
  for (let it = 0; it < n; it++) {
    let u = -1;
    let best = Number.POSITIVE_INFINITY;
    for (let i = 0; i < n; i++)
      if (!visited[i] && dist[i] < best) {
        best = dist[i];
        u = i;
      }
    if (u === -1) break;
    visited[u] = true;
    for (const [v, w] of adj[u]!) if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
  }
  return dist.map((d) => (d === Number.POSITIVE_INFINITY ? -1 : d));
}

function evalArith(expr: string): number {
  // 정수 + - * / ( ), 나눗셈은 0 방향 절삭. shunting-yard.
  const toks = expr.match(/\d+|[+\-*/()]/g);
  if (!toks) throw new Error("bad");
  const prec: Record<string, number> = { "+": 1, "-": 1, "*": 2, "/": 2 };
  const out: string[] = [];
  const ops: string[] = [];
  for (const t of toks) {
    if (/\d+/.test(t)) out.push(t);
    else if (t === "(") ops.push(t);
    else if (t === ")") {
      while (ops.length && ops[ops.length - 1] !== "(") out.push(ops.pop()!);
      ops.pop();
    } else {
      while (ops.length && ops[ops.length - 1] !== "(" && prec[ops[ops.length - 1]!]! >= prec[t]!)
        out.push(ops.pop()!);
      ops.push(t);
    }
  }
  while (ops.length) out.push(ops.pop()!);
  return evalRpn(out);
}

function evalRpn(tokens: string[]): number {
  const st: number[] = [];
  for (const t of tokens) {
    if (/^-?\d+$/.test(t)) st.push(Number.parseInt(t, 10));
    else {
      const b = st.pop()!;
      const a = st.pop()!;
      if (t === "+") st.push(a + b);
      else if (t === "-") st.push(a - b);
      else if (t === "*") st.push(a * b);
      else if (t === "/") st.push(Math.trunc(a / b));
      else throw new Error("op");
    }
  }
  if (st.length !== 1) throw new Error("rpn");
  return st[0]!;
}

function knapsack(capacity: number, items: [number, number][]): number {
  const dp = new Array(capacity + 1).fill(0);
  for (const [w, v] of items)
    for (let c = capacity; c >= w; c--) dp[c] = Math.max(dp[c], dp[c - w] + v);
  return dp[capacity];
}

interface Parsed {
  literal?: number;
  refs?: string[];
  op?: string;
  x?: string;
  y?: string; // 셀 ref 또는 정수 문자열
  bad?: boolean;
}
function parseCell(raw: string): Parsed {
  if (!raw.startsWith("=")) {
    const n = Number.parseInt(raw, 10);
    return Number.isNaN(n) ? { bad: true } : { literal: n };
  }
  const m = raw.slice(1).match(/^([A-Z]\d+)(?:\s*([+\-*])\s*([A-Z]\d+|\d+))?$/);
  if (!m) return { bad: true };
  const refs = [m[1]!];
  if (m[3] && /^[A-Z]\d+$/.test(m[3])) refs.push(m[3]);
  return { refs, op: m[2], x: m[1], y: m[3] };
}

function evalSheet(cells: Record<string, string>): Record<string, string> {
  const parsed: Record<string, Parsed> = {};
  for (const [c, raw] of Object.entries(cells)) parsed[c] = parseCell(raw);

  // 1) 사이클 멤버십 검출 (DFS back-edge).
  const inCycle = new Set<string>();
  const color: Record<string, 0 | 1 | 2> = {}; // 0 white,1 gray,2 black
  const dfs = (u: string, stack: string[]): void => {
    color[u] = 1;
    stack.push(u);
    for (const v of parsed[u]?.refs ?? []) {
      if (!(v in cells)) continue; // 없는 셀은 사이클 아님(=>#ERR 로 따로 처리)
      if (color[v] === 1) {
        const from = stack.indexOf(v);
        for (let i = from; i < stack.length; i++) inCycle.add(stack[i]!);
      } else if (!color[v]) dfs(v, stack);
    }
    stack.pop();
    color[u] = 2;
  };
  for (const c of Object.keys(cells)) if (!color[c]) dfs(c, []);

  // 2) 값 평가 (사이클 외 셀은 DAG → 메모 재귀).
  const memo: Record<string, string> = {};
  const value = (c: string): string => {
    if (!(c in cells)) return "#ERR";
    if (inCycle.has(c)) return "#CYCLE";
    if (c in memo) return memo[c]!;
    const p = parsed[c]!;
    let val: string;
    if (p.bad) val = "#ERR";
    else if (p.literal !== undefined) val = String(p.literal);
    else {
      const a = value(p.x!);
      if (a === "#CYCLE" || a === "#ERR") val = "#ERR";
      else if (!p.op) val = a;
      else {
        const rhs = /^\d+$/.test(p.y!) ? p.y! : value(p.y!);
        if (rhs === "#CYCLE" || rhs === "#ERR") val = "#ERR";
        else {
          const x = Number.parseInt(a, 10);
          const y = Number.parseInt(rhs, 10);
          val = String(p.op === "+" ? x + y : p.op === "-" ? x - y : x * y);
        }
      }
    }
    memo[c] = val;
    return val;
  };
  const result: Record<string, string> = {};
  for (const c of Object.keys(cells)) result[c] = inCycle.has(c) ? "#CYCLE" : value(c);
  return result;
}

function toHex(bytes: number[]): string {
  return bytes.map((b) => b.toString(16).padStart(2, "0")).join("");
}
function fromHex(hex: string): number[] {
  const out: number[] = [];
  for (let i = 0; i < hex.length; i += 2) out.push(Number.parseInt(hex.slice(i, i + 2), 16));
  return out;
}

// ── 과제 정의 ───────────────────────────────────────────
export const SUBAGENT_TASKS: LocalTask[] = [
  {
    id: "subagent-101",
    difficulty: "hard",
    instruction: `Read graph.json = {n, edges:[[u,v,w],...]} (directed, non-negative weights). Compute the shortest-path distance from node 0 to every node. Write distances.json: a JSON array of length n, where index i is the distance to node i, or -1 if unreachable.${DELEGATE}`,
    setup: (work) => {
      const rng = new Rng("subagent-101");
      const n = 12;
      const edges: [number, number, number][] = [];
      for (let u = 0; u < n; u++)
        for (let k = 0; k < 3; k++) {
          const v = rng.int(0, n - 1);
          if (v !== u) edges.push([u, v, rng.int(1, 20)]);
        }
      writeFileSync(join(work, "graph.json"), JSON.stringify({ n, edges }));
    },
    verify: (work) =>
      guard(() => {
        const g = JSON.parse(readSafe(work, "graph.json")!);
        const expected = dijkstra(g.n, g.edges, 0);
        const got = JSON.parse(readSafe(work, "distances.json")!);
        return Array.isArray(got) && JSON.stringify(got) === JSON.stringify(expected);
      }),
  },
  {
    id: "subagent-102",
    difficulty: "hard",
    instruction: `There are 24 shard files shards/shard-00.json .. shards/shard-23.json, each a JSON array of {account, delta} entries. Compute the net balance per account across ALL shards. Write balances.json: a JSON object mapping account -> integer balance (omit accounts whose balance is 0).${DELEGATE}`,
    setup: (work) => {
      const rng = new Rng("subagent-102");
      mkdirSync(join(work, "shards"), { recursive: true });
      for (let s = 0; s < 24; s++) {
        const rows: { account: string; delta: number }[] = [];
        const cnt = rng.int(5, 12);
        for (let i = 0; i < cnt; i++)
          rows.push({ account: `acct-${rng.int(0, 9)}`, delta: rng.int(-50, 50) });
        writeFileSync(
          join(work, "shards", `shard-${String(s).padStart(2, "0")}.json`),
          JSON.stringify(rows),
        );
      }
    },
    verify: (work) =>
      guard(() => {
        const bal: Record<string, number> = {};
        for (let s = 0; s < 24; s++) {
          const rows = JSON.parse(
            readSafe(work, `shards/shard-${String(s).padStart(2, "0")}.json`)!,
          );
          for (const r of rows) bal[r.account] = (bal[r.account] ?? 0) + r.delta;
        }
        const expected: Record<string, number> = {};
        for (const [k, v] of Object.entries(bal)) if (v !== 0) expected[k] = v;
        const got = JSON.parse(readSafe(work, "balances.json")!);
        const norm = (o: Record<string, number>) =>
          JSON.stringify(Object.fromEntries(Object.entries(o).sort()));
        return norm(got) === norm(expected);
      }),
  },
  {
    id: "subagent-103",
    difficulty: "hard",
    instruction: `Read program.txt (one arithmetic expression per line, using integers and + - * / and parentheses; division truncates toward zero). Evaluate each line. Write results.txt with one integer result per line, in the same order.${DELEGATE}`,
    setup: (work) => {
      const rng = new Rng("subagent-103");
      const lines: string[] = [];
      for (let i = 0; i < 16; i++) {
        const a = rng.int(1, 40);
        const b = rng.int(1, 40);
        const c = rng.int(1, 40);
        const ops = ["+", "-", "*"];
        lines.push(`(${a} ${ops[rng.int(0, 2)]} ${b}) * ${c} - ${rng.int(1, 30)}`);
      }
      writeFileSync(join(work, "program.txt"), lines.join("\n"));
    },
    verify: (work) =>
      guard(() => {
        const lines = readSafe(work, "program.txt")!
          .split("\n")
          .filter((l) => l.trim());
        const expected = lines.map((l) => evalArith(l));
        const got = readSafe(work, "results.txt")!
          .split("\n")
          .filter((l) => l.trim())
          .map((l) => Number.parseInt(l.trim(), 10));
        return JSON.stringify(got) === JSON.stringify(expected);
      }),
  },
  {
    id: "subagent-104",
    difficulty: "hard",
    instruction: `Read knapsack.json = {capacity, items:[[weight,value],...]}. Solve the 0/1 knapsack problem: pick a subset of items with total weight <= capacity maximizing total value. Write answer.txt: the maximum total value as a single integer.${DELEGATE}`,
    setup: (work) => {
      const rng = new Rng("subagent-104");
      const items: [number, number][] = [];
      for (let i = 0; i < 22; i++) items.push([rng.int(1, 15), rng.int(1, 30)]);
      writeFileSync(join(work, "knapsack.json"), JSON.stringify({ capacity: 50, items }));
    },
    verify: (work) =>
      guard(() => {
        const k = JSON.parse(readSafe(work, "knapsack.json")!);
        const expected = knapsack(k.capacity, k.items);
        return Number.parseInt(readSafe(work, "answer.txt")!.trim(), 10) === expected;
      }),
  },
  {
    id: "subagent-105",
    difficulty: "hard",
    instruction: `Read encoded.txt (a hex string) and key.txt (a hex string). Decode: hex->bytes, XOR each byte with the repeating key bytes, interpret the resulting ASCII text as a space-separated RPN (postfix) expression over integers with operators + - *, and evaluate it. Write answer.txt: the resulting integer.${DELEGATE}`,
    setup: (work) => {
      const rng = new Rng("subagent-105");
      // 결정적 RPN 식 생성: a b + c * d -
      const a = rng.int(2, 9);
      const b = rng.int(2, 9);
      const c = rng.int(2, 9);
      const d = rng.int(2, 9);
      const rpn = `${a} ${b} + ${c} * ${d} -`;
      const key = [rng.int(1, 255), rng.int(1, 255), rng.int(1, 255)];
      const bytes = Array.from(rpn).map((ch, i) => ch.charCodeAt(0) ^ key[i % key.length]!);
      writeFileSync(join(work, "encoded.txt"), toHex(bytes));
      writeFileSync(join(work, "key.txt"), toHex(key));
    },
    verify: (work) =>
      guard(() => {
        const enc = fromHex(readSafe(work, "encoded.txt")!.trim());
        const key = fromHex(readSafe(work, "key.txt")!.trim());
        const text = enc.map((b, i) => String.fromCharCode(b ^ key[i % key.length]!)).join("");
        const expected = evalRpn(text.trim().split(/\s+/));
        return Number.parseInt(readSafe(work, "answer.txt")!.trim(), 10) === expected;
      }),
  },
  {
    id: "subagent-106",
    difficulty: "hard",
    instruction: `Read sheet.json = {cells: {"A1":"5","B1":"=A1+3",...}}. Each cell is either an integer literal or a formula "=X" or "=X op Y" where X is a cell ref, Y is a cell ref or integer, op in + - *. Evaluate every cell. A cell in a reference cycle must be "#CYCLE"; a cell referencing a missing cell or an error must be "#ERR". Write result.json: a JSON object mapping each cell name to its evaluated value (integers as strings, or "#CYCLE"/"#ERR").${DELEGATE}`,
    setup: (work) => {
      const cells: Record<string, string> = {
        A1: "5",
        B1: "=A1+3",
        C1: "=A1*B1",
        D1: "=C1-2",
        // 사이클
        E1: "=F1+1",
        F1: "=E1+1",
        // 에러 전파(없는 셀 참조)
        G1: "=Z9+1",
        H1: "=G1*2",
      };
      writeFileSync(join(work, "sheet.json"), JSON.stringify({ cells }));
    },
    verify: (work) =>
      guard(() => {
        const sheet = JSON.parse(readSafe(work, "sheet.json")!);
        const expected = evalSheet(sheet.cells);
        const got = JSON.parse(readSafe(work, "result.json")!);
        const norm = (o: Record<string, string>) =>
          JSON.stringify(Object.fromEntries(Object.entries(o).sort()));
        return norm(got) === norm(expected);
      }),
  },
];