470 lines
17 KiB
TypeScript
470 lines
17 KiB
TypeScript
import path from "path";
|
||
import fs from "fs/promises";
|
||
import os from "os";
|
||
import { executeStandardCode } from "./runner";
|
||
import { createZipFile } from "./zip";
|
||
|
||
const OUTPUT_BASE = path.join(os.tmpdir(), "i-tools-testcase");
|
||
|
||
interface Constraint {
|
||
min: number;
|
||
max: number;
|
||
}
|
||
|
||
function parseConstraint(text: string, variable: string): Constraint | null {
|
||
const escapedVariable = variable.replace(/[.*+?^${}()|[\]\\]/g, "\\$&");
|
||
const patterns = [
|
||
new RegExp(`(-?\\d+(?:\\.\\d+)?)\\s*[≤<=]\\s*${escapedVariable}\\s*[≤<=]\\s*(-?\\d+(?:\\.\\d+)?)`, "i"),
|
||
new RegExp(`(-?\\d+)\\s*[≤<=]\\s*${escapedVariable}\\s*[≤<=]\\s*(-?\\d+)\\s*\\^\\s*(-?\\d+)`, "i"),
|
||
new RegExp(`(-?[\\d,]+)\\s*[≤<=]\\s*${escapedVariable}\\s*[≤<=]\\s*(-?[\\d,]+)`, "i"),
|
||
new RegExp(`${escapedVariable}\\s*[∈∊]\\s*\\[\\s*(-?\\d+(?:\\.\\d+)?)\\s*,\\s*(-?\\d+(?:\\.\\d+)?)\\s*\\]`, "i"),
|
||
new RegExp(`${escapedVariable}.*?(?:范围|取值).*?(-?\\d+(?:\\.\\d+)?).*?(?:到|至|-|~).*?(-?\\d+(?:\\.\\d+)?)`, "i"),
|
||
new RegExp(`(-?\\d+(?:\\.\\d+)?)\\s*[<≤<=]+\\s*${escapedVariable}\\s*[<≤<=]+\\s*(-?\\d+(?:\\.\\d+)?)`, "i"),
|
||
new RegExp(`${escapedVariable}\\s*[≤<=]\\s*(-?\\d+(?:\\.\\d+)?).*?${escapedVariable}\\s*[≥>=]\\s*(-?\\d+(?:\\.\\d+)?)`, "i"),
|
||
];
|
||
for (const pattern of patterns) {
|
||
const match = text.match(pattern);
|
||
if (match) {
|
||
let min: number, max: number;
|
||
if (match.length === 4 && match[3]) {
|
||
min = parseFloat(match[1]);
|
||
max = parseFloat(match[2]) * Math.pow(10, parseFloat(match[3]));
|
||
} else if (pattern.source.includes("≤.*≥")) {
|
||
max = parseFloat(match[1].replace(/,/g, ""));
|
||
min = parseFloat(match[2].replace(/,/g, ""));
|
||
} else {
|
||
min = parseFloat(match[1].replace(/,/g, ""));
|
||
max = parseFloat(match[2].replace(/,/g, ""));
|
||
}
|
||
if (min > max) [min, max] = [max, min];
|
||
return { min: Math.floor(min), max: Math.floor(max) };
|
||
}
|
||
}
|
||
return null;
|
||
}
|
||
|
||
function parseAllConstraints(description: string): Record<string, Constraint> {
|
||
const constraints: Record<string, Constraint> = {};
|
||
const commonVariables = [
|
||
"n", "m", "k", "q", "t", "l", "r", "x", "y", "z",
|
||
"a", "b", "c", "d", "e", "f", "g", "h", "i", "j",
|
||
"a_i", "b_i", "c_i", "A_i", "B_i", "C_i",
|
||
"s", "S", "w", "W", "h", "H",
|
||
"数组长度", "序列长度", "字符串长度",
|
||
"序列中的数", "数组中的数", "元素", "值",
|
||
"权重", "代价", "距离", "时间", "长度", "宽度", "高度",
|
||
];
|
||
for (const variable of commonVariables) {
|
||
const c = parseConstraint(description, variable);
|
||
if (c) constraints[variable] = c;
|
||
}
|
||
const rangePatterns = [
|
||
/(\d+)\s*[≤<=]\s*.*?[≤<=]\s*(\d+)/g,
|
||
/(\d+)\s*到\s*(\d+)/g,
|
||
/(\d+)\s*~\s*(\d+)/g,
|
||
/\[(\d+),\s*(\d+)\]/g,
|
||
];
|
||
for (const pattern of rangePatterns) {
|
||
let match;
|
||
while ((match = pattern.exec(description)) !== null) {
|
||
const min = parseInt(match[1], 10);
|
||
const max = parseInt(match[2], 10);
|
||
if (min < max) {
|
||
const key = `range_${min}_${max}`;
|
||
if (!constraints[key]) constraints[key] = { min, max };
|
||
}
|
||
}
|
||
}
|
||
return constraints;
|
||
}
|
||
|
||
function generateValueInRange(min: number, max: number, caseNumber: number, totalCases = 10): number {
|
||
const range = max - min;
|
||
if (caseNumber === 1) return min;
|
||
if (caseNumber === 2) return min + 1;
|
||
if (caseNumber === totalCases) return max;
|
||
if (caseNumber === totalCases - 1) return max - 1;
|
||
if (caseNumber === 3) return min + Math.floor(range * 0.1);
|
||
if (caseNumber === 4) return min + Math.floor(range * 0.25);
|
||
if (caseNumber === 5) return min + Math.floor(range * 0.5);
|
||
if (caseNumber === 6) return min + Math.floor(range * 0.75);
|
||
if (caseNumber === 7) return min + Math.floor(range * 0.9);
|
||
const segments = [0.05, 0.15, 0.35, 0.65, 0.85, 0.95];
|
||
const seg = segments[caseNumber % segments.length];
|
||
const value = min + Math.floor(range * (seg + (Math.random() * 0.1 - 0.05)));
|
||
return Math.max(min, Math.min(max, value));
|
||
}
|
||
|
||
function generateArrayInput(
|
||
caseNumber: number,
|
||
nConstraint: Constraint | null,
|
||
valueConstraint: Constraint | null,
|
||
totalCases: number
|
||
): string {
|
||
const maxN = nConstraint?.max ?? 1000;
|
||
const minN = nConstraint?.min ?? 1;
|
||
const n = generateValueInRange(minN, maxN, caseNumber, totalCases);
|
||
const maxVal = valueConstraint?.max ?? 1000;
|
||
const minVal = valueConstraint?.min ?? -1000;
|
||
let result = `${n}\n`;
|
||
const values: number[] = [];
|
||
for (let i = 0; i < n; i++) {
|
||
values.push(generateValueInRange(minVal, maxVal, i + 1, n));
|
||
}
|
||
result += values.join(" ");
|
||
return result;
|
||
}
|
||
|
||
function generateGraphInput(
|
||
caseNumber: number,
|
||
nConstraint: Constraint | null,
|
||
totalCases: number
|
||
): string {
|
||
const maxN = Math.min(nConstraint?.max ?? 1000, 1000);
|
||
const minN = nConstraint?.min ?? 3;
|
||
const n = generateValueInRange(minN, maxN, caseNumber, totalCases);
|
||
const m = Math.min(Math.floor((n * (n - 1)) / 2), Math.floor(n * Math.log(n)));
|
||
let result = `${n} ${m}\n`;
|
||
const edges = new Set<string>();
|
||
for (let i = 0; i < m; i++) {
|
||
let u: number, v: number;
|
||
do {
|
||
u = Math.floor(Math.random() * n) + 1;
|
||
v = Math.floor(Math.random() * n) + 1;
|
||
} while (u === v || edges.has(`${Math.min(u, v)}-${Math.max(u, v)}`));
|
||
edges.add(`${Math.min(u, v)}-${Math.max(u, v)}`);
|
||
result += `${u} ${v}\n`;
|
||
}
|
||
return result.trim();
|
||
}
|
||
|
||
function generateStringInput(
|
||
caseNumber: number,
|
||
nConstraint: Constraint | null,
|
||
totalCases: number
|
||
): string {
|
||
const maxN = nConstraint?.max ?? 100;
|
||
const minN = nConstraint?.min ?? 1;
|
||
const n = generateValueInRange(minN, maxN, caseNumber, totalCases);
|
||
const chars = "abcdefghijklmnopqrstuvwxyz";
|
||
let str = "";
|
||
for (let i = 0; i < n; i++) {
|
||
str += chars[Math.floor(Math.random() * chars.length)];
|
||
}
|
||
return str;
|
||
}
|
||
|
||
function generateMatrixInput(
|
||
caseNumber: number,
|
||
nConstraint: Constraint | null,
|
||
valueConstraint: Constraint | null,
|
||
totalCases: number
|
||
): string {
|
||
const maxN = Math.min(nConstraint?.max ?? 100, 100);
|
||
const minN = nConstraint?.min ?? 2;
|
||
const n = generateValueInRange(minN, maxN, caseNumber, totalCases);
|
||
const m = n;
|
||
const maxVal = valueConstraint?.max ?? 100;
|
||
const minVal = valueConstraint?.min ?? 0;
|
||
let result = `${n} ${m}\n`;
|
||
for (let i = 0; i < n; i++) {
|
||
const row: number[] = [];
|
||
for (let j = 0; j < m; j++) {
|
||
row.push(Math.floor(Math.random() * (maxVal - minVal + 1)) + minVal);
|
||
}
|
||
result += row.join(" ") + "\n";
|
||
}
|
||
return result.trim();
|
||
}
|
||
|
||
function generateTreeInput(
|
||
caseNumber: number,
|
||
nConstraint: Constraint | null,
|
||
totalCases: number
|
||
): string {
|
||
const maxN = Math.min(nConstraint?.max ?? 1000, 10000);
|
||
const minN = Math.max(nConstraint?.min ?? 2, 2);
|
||
const n = generateValueInRange(minN, maxN, caseNumber, totalCases);
|
||
let result = `${n}\n`;
|
||
const edges: [number, number][] = [];
|
||
for (let i = 2; i <= n; i++) {
|
||
const parent = Math.floor(Math.random() * (i - 1)) + 1;
|
||
edges.push([parent, i]);
|
||
}
|
||
for (let i = edges.length - 1; i > 0; i--) {
|
||
const j = Math.floor(Math.random() * (i + 1));
|
||
[edges[i], edges[j]] = [edges[j], edges[i]];
|
||
}
|
||
for (const [u, v] of edges) {
|
||
result += `${u} ${v}\n`;
|
||
}
|
||
return result.trim();
|
||
}
|
||
|
||
function generateQueryInput(
|
||
caseNumber: number,
|
||
nConstraint: Constraint | null,
|
||
mConstraint: Constraint | null,
|
||
valueConstraint: Constraint | null,
|
||
totalCases: number
|
||
): string {
|
||
const maxN = nConstraint?.max ?? 1000;
|
||
const minN = nConstraint?.min ?? 1;
|
||
const n = generateValueInRange(minN, maxN, caseNumber, totalCases);
|
||
const maxM = mConstraint?.max ?? 100;
|
||
const minM = mConstraint?.min ?? 1;
|
||
const m = generateValueInRange(minM, maxM, caseNumber, totalCases);
|
||
const maxVal = valueConstraint?.max ?? 1000;
|
||
const minVal = valueConstraint?.min ?? 1;
|
||
let result = `${n} ${m}\n`;
|
||
const values: number[] = [];
|
||
for (let i = 0; i < n; i++) {
|
||
values.push(generateValueInRange(minVal, maxVal, i + 1, n));
|
||
}
|
||
result += values.join(" ") + "\n";
|
||
const queries: number[] = [];
|
||
for (let i = 0; i < m; i++) {
|
||
queries.push(generateValueInRange(minVal, maxVal, i + 1, m));
|
||
}
|
||
result += queries.join(" ");
|
||
return result;
|
||
}
|
||
|
||
function generateBinarySearchInput(
|
||
caseNumber: number,
|
||
description: string,
|
||
totalCases: number
|
||
): string {
|
||
const nConstraint = parseConstraint(description, "n") ?? { min: 5, max: 100 };
|
||
const mConstraint = parseConstraint(description, "m") ?? { min: 1, max: 10 };
|
||
const valueConstraint = parseConstraint(description, "a_i") ?? parseConstraint(description, "q") ?? { min: 0, max: 100 };
|
||
let n: number, m: number;
|
||
switch (caseNumber) {
|
||
case 1:
|
||
n = Math.min(10, nConstraint.max);
|
||
m = Math.min(5, mConstraint.max);
|
||
break;
|
||
case 2:
|
||
n = Math.min(100, Math.floor(nConstraint.max * 0.1));
|
||
m = Math.min(20, Math.floor(mConstraint.max * 0.2));
|
||
break;
|
||
case 3:
|
||
n = nConstraint.min;
|
||
m = mConstraint.min;
|
||
break;
|
||
case 4:
|
||
n = Math.min(1000, nConstraint.max);
|
||
m = Math.min(100, mConstraint.max);
|
||
break;
|
||
default:
|
||
n = generateValueInRange(nConstraint.min, Math.min(500, nConstraint.max), caseNumber, totalCases);
|
||
m = generateValueInRange(mConstraint.min, Math.min(50, mConstraint.max), caseNumber, totalCases);
|
||
}
|
||
const sequence: number[] = [];
|
||
let currentValue = valueConstraint.min;
|
||
for (let i = 0; i < n; i++) {
|
||
if (i > 0 && Math.random() < 0.7) {
|
||
const inc = Math.floor(Math.random() * 5) + 1;
|
||
currentValue = Math.min(currentValue + inc, valueConstraint.max);
|
||
}
|
||
sequence.push(currentValue);
|
||
}
|
||
const queries: number[] = [];
|
||
for (let i = 0; i < m; i++) {
|
||
if (i < m / 2 && sequence.length > 0) {
|
||
queries.push(sequence[Math.floor(Math.random() * sequence.length)]!);
|
||
} else {
|
||
queries.push(
|
||
Math.random() < 0.5 && sequence.length > 0
|
||
? sequence[Math.floor(Math.random() * sequence.length)]!
|
||
: generateValueInRange(valueConstraint.min, valueConstraint.max, i, m)
|
||
);
|
||
}
|
||
}
|
||
return `${n} ${m}\n${sequence.join(" ")}\n${queries.join(" ")}`;
|
||
}
|
||
|
||
function generateMockInput(description: string, caseNumber: number, totalCases = 10): string {
|
||
const desc = description.toLowerCase();
|
||
const allConstraints = parseAllConstraints(description);
|
||
|
||
if (desc.includes("单调不减") && desc.includes("查找") && desc.includes("询问")) {
|
||
return generateBinarySearchInput(caseNumber, description, totalCases);
|
||
}
|
||
|
||
const nConstraint = allConstraints["n"] ?? allConstraints["N"] ?? parseConstraint(description, "n");
|
||
const mConstraint = allConstraints["m"] ?? allConstraints["M"] ?? parseConstraint(description, "m");
|
||
const valueConstraint =
|
||
allConstraints["序列中的数"] ?? allConstraints["数组中的数"] ?? allConstraints["元素"] ?? allConstraints["值"] ??
|
||
parseConstraint(description, "序列中的数") ?? parseConstraint(description, "value");
|
||
|
||
let effectiveN = nConstraint;
|
||
if (!effectiveN) {
|
||
const rangeKeys = Object.keys(allConstraints).filter((k) => k.startsWith("range_"));
|
||
if (rangeKeys.length > 0) {
|
||
const maxRange = rangeKeys.reduce((a, b) =>
|
||
(allConstraints[b]?.max ?? 0) > (allConstraints[a]?.max ?? 0) ? b : a
|
||
);
|
||
effectiveN = allConstraints[maxRange] ?? null;
|
||
}
|
||
}
|
||
|
||
if (desc.includes("序列") || desc.includes("数组") || desc.includes("array")) {
|
||
return generateArrayInput(caseNumber, effectiveN ?? null, valueConstraint ?? null, totalCases);
|
||
}
|
||
if (desc.includes("图") || desc.includes("graph")) {
|
||
return generateGraphInput(caseNumber, effectiveN ?? null, totalCases);
|
||
}
|
||
if (desc.includes("字符串") || desc.includes("string")) {
|
||
return generateStringInput(caseNumber, effectiveN ?? null, totalCases);
|
||
}
|
||
if (desc.includes("矩阵") || desc.includes("matrix")) {
|
||
return generateMatrixInput(caseNumber, effectiveN ?? null, valueConstraint ?? null, totalCases);
|
||
}
|
||
if (desc.includes("树") || desc.includes("tree")) {
|
||
return generateTreeInput(caseNumber, effectiveN ?? null, totalCases);
|
||
}
|
||
if (desc.includes("询问") || desc.includes("query")) {
|
||
return generateQueryInput(caseNumber, effectiveN ?? null, mConstraint ?? null, valueConstraint ?? null, totalCases);
|
||
}
|
||
|
||
const maxN = effectiveN?.max ?? 100;
|
||
const minN = effectiveN?.min ?? 1;
|
||
const n = generateValueInRange(minN, maxN, caseNumber, totalCases);
|
||
const keys = Object.keys(allConstraints);
|
||
if (keys.length > 1) {
|
||
let result = `${n}\n`;
|
||
for (const key of keys.slice(1, 3)) {
|
||
if (key !== "n" && key !== "N" && !key.startsWith("range_")) {
|
||
const c = allConstraints[key];
|
||
if (c) result += `${generateValueInRange(c.min, c.max, caseNumber, totalCases)}\n`;
|
||
}
|
||
}
|
||
return result.trim();
|
||
}
|
||
return `${n}`;
|
||
}
|
||
|
||
const MAX_RETRIES = 2;
|
||
|
||
export interface FallbackParams {
|
||
englishName: string;
|
||
description: string;
|
||
standardCode: string;
|
||
testCaseCount: number;
|
||
}
|
||
|
||
export interface FallbackResult {
|
||
testCases: { input: string; output: string }[];
|
||
outputDirName: string;
|
||
zipFileName: string;
|
||
}
|
||
|
||
export type ProgressCallback = (progress: number, message: string, generatedCount: number) => void;
|
||
|
||
export async function generateFallbackTestCases(
|
||
params: FallbackParams,
|
||
progressCallback?: ProgressCallback
|
||
): Promise<FallbackResult> {
|
||
const randomSuffix = Date.now().toString(36) + "_" + Math.random().toString(36).slice(2, 7);
|
||
const outputDirName = `${params.englishName}_${randomSuffix}`;
|
||
const outputDir = path.join(OUTPUT_BASE, outputDirName);
|
||
await fs.mkdir(outputDir, { recursive: true });
|
||
|
||
const testCases: { input: string; output: string }[] = [];
|
||
|
||
for (let i = 1; i <= params.testCaseCount; i++) {
|
||
if (progressCallback) {
|
||
const progress = 0.3 + (i / params.testCaseCount) * 0.6;
|
||
progressCallback(progress, `正在生成第 ${i}/${params.testCaseCount} 组测试用例...`, i - 1);
|
||
}
|
||
|
||
const inputData = generateMockInput(params.description, i, params.testCaseCount);
|
||
let outputData: string | null = null;
|
||
|
||
for (let retry = 0; retry <= MAX_RETRIES; retry++) {
|
||
try {
|
||
outputData = await executeStandardCode(params.standardCode, inputData);
|
||
break;
|
||
} catch (err) {
|
||
if (retry === MAX_RETRIES) break;
|
||
}
|
||
}
|
||
|
||
if (!outputData) continue;
|
||
|
||
await fs.writeFile(path.join(outputDir, `${params.englishName}${i}.in`), inputData);
|
||
await fs.writeFile(path.join(outputDir, `${params.englishName}${i}.out`), outputData);
|
||
testCases.push({ input: inputData, output: outputData });
|
||
}
|
||
|
||
if (progressCallback) {
|
||
progressCallback(0.9, "正在创建ZIP压缩包...", testCases.length);
|
||
}
|
||
|
||
const zipFileName = `${params.englishName}_${randomSuffix}.zip`;
|
||
const zipPath = path.join(OUTPUT_BASE, zipFileName);
|
||
await createZipFile(outputDir, zipPath, params.englishName);
|
||
|
||
return { testCases, outputDirName, zipFileName };
|
||
}
|
||
|
||
export function getOutputBase(): string {
|
||
return OUTPUT_BASE;
|
||
}
|
||
|
||
/** AI 生成的用例：用标程跑出 output，写入 .in/.out 并打包 */
|
||
export interface AITestCaseInput {
|
||
input: string;
|
||
}
|
||
|
||
export async function runAIGeneratedCases(
|
||
params: FallbackParams,
|
||
aiCases: AITestCaseInput[],
|
||
progressCallback?: ProgressCallback
|
||
): Promise<FallbackResult> {
|
||
const randomSuffix = Date.now().toString(36) + "_" + Math.random().toString(36).slice(2, 7);
|
||
const outputDirName = `${params.englishName}_${randomSuffix}`;
|
||
const outputDir = path.join(OUTPUT_BASE, outputDirName);
|
||
await fs.mkdir(outputDir, { recursive: true });
|
||
|
||
const testCases: { input: string; output: string }[] = [];
|
||
const total = aiCases.length;
|
||
|
||
for (let i = 0; i < total; i++) {
|
||
if (progressCallback) {
|
||
const progress = 0.3 + ((i + 1) / total) * 0.6;
|
||
progressCallback(progress, `正在处理第 ${i + 1}/${total} 组测试用例...`, i);
|
||
}
|
||
|
||
const inputData = aiCases[i]!.input;
|
||
let outputData: string | null = null;
|
||
|
||
for (let retry = 0; retry <= MAX_RETRIES; retry++) {
|
||
try {
|
||
outputData = await executeStandardCode(params.standardCode, inputData);
|
||
break;
|
||
} catch {
|
||
if (retry === MAX_RETRIES) break;
|
||
}
|
||
}
|
||
|
||
if (!outputData) continue;
|
||
|
||
const oneBased = i + 1;
|
||
await fs.writeFile(path.join(outputDir, `${params.englishName}${oneBased}.in`), inputData);
|
||
await fs.writeFile(path.join(outputDir, `${params.englishName}${oneBased}.out`), outputData);
|
||
testCases.push({ input: inputData, output: outputData });
|
||
}
|
||
|
||
if (progressCallback) {
|
||
progressCallback(0.9, "正在创建ZIP压缩包...", testCases.length);
|
||
}
|
||
|
||
const zipFileName = `${params.englishName}_${randomSuffix}.zip`;
|
||
const zipPath = path.join(OUTPUT_BASE, zipFileName);
|
||
await createZipFile(outputDir, zipPath, params.englishName);
|
||
|
||
return { testCases, outputDirName, zipFileName };
|
||
}
|