sanket3280/code-execution

1/**2 * Enhanced Output Validator3 * Validates test outputs with support for multiple valid answers4 * Handles dynamic validation for all problem types5 */6 7/**8 * Validate Two Sum problem output9 * Accepts any valid pair of indices that sum to target10 */11const validateTwoSum = (outputArr, expectedArr, inputObj) => {12  if (!inputObj.nums || inputObj.target === undefined) return null;13  if (!Array.isArray(outputArr) || outputArr.length !== 2) return null;14  15  const nums = inputObj.nums;16  const target = inputObj.target;17  const [i, j] = outputArr;18  19  // Check if indices are valid and sum to target20  if (i >= 0 && i < nums.length && j >= 0 && j < nums.length && 21      i !== j && nums[i] + nums[j] === target) {22    23    // Find all valid pairs for comparison24    const allValidPairs = [];25    for (let x = 0; x < nums.length; x++) {26      for (let y = x + 1; y < nums.length; y++) {27        if (nums[x] + nums[y] === target) {28          allValidPairs.push([x, y]);29        }30      }31    }32    33    return {34      isValid: true,35      message: `Two Sum: [${i},${j}] is valid (${nums[i]} + ${nums[j]} = ${target})`,36      allValidOutputs: allValidPairs.map(p => JSON.stringify(p))37    };38  }39  40  return null;41};42 43/**44 * Validate Three Sum problem output45 * Accepts any valid set of triplets that sum to target (order doesn't matter)46 */47const validateThreeSum = (outputArr, expectedArr, inputObj) => {48  if (!inputObj.nums) return null;49  if (!Array.isArray(outputArr) || !Array.isArray(outputArr[0])) return null;50  51  const nums = inputObj.nums;52  const target = inputObj.target || 0; // Default target is 0 for 3Sum53  54  // Normalize triplets (sort each triplet and the array of triplets)55  const normalizeTriplets = (triplets) => {56    return triplets57      .map(t => [...t].sort((a, b) => a - b))58      .sort((a, b) => {59        for (let i = 0; i < 3; i++) {60          if (a[i] !== b[i]) return a[i] - b[i];61        }62        return 0;63      });64  };65  66  // Check if all triplets sum to target67  const allValid = outputArr.every(triplet => {68    if (!Array.isArray(triplet) || triplet.length !== 3) return false;69    const [a, b, c] = triplet;70    return a + b + c === target;71  });72  73  if (!allValid) return null;74  75  // Check if output has same triplets as expected (order doesn't matter)76  const normalizedOutput = normalizeTriplets(outputArr);77  const normalizedExpected = normalizeTriplets(expectedArr);78  79  if (JSON.stringify(normalizedOutput) === JSON.stringify(normalizedExpected)) {80    return {81      isValid: true,82      message: `Three Sum: All ${outputArr.length} triplets are valid and match expected`,83      allValidOutputs: [JSON.stringify(expectedArr)]84    };85  }86  87  return null;88};89 90/**91 * Validate Permutations output92 * Accepts any valid set of permutations (order of permutations doesn't matter)93 */94const validatePermutations = (outputArr, expectedArr, inputObj) => {95  if (!inputObj.nums || !Array.isArray(outputArr) || !Array.isArray(outputArr[0])) return null;96  97  const inputNums = inputObj.nums;98  const sortedInput = [...inputNums].sort((a, b) => a - b).join(',');99  100  // Check if each output is a valid permutation101  const allValid = outputArr.every(perm => {102    if (!Array.isArray(perm) || perm.length !== inputNums.length) return false;103    const sortedPerm = [...perm].sort((a, b) => a - b).join(',');104    return sortedPerm === sortedInput;105  });106  107  if (!allValid) return null;108  109  // Check if count matches (all permutations should be present)110  const factorial = (n) => n <= 1 ? 1 : n * factorial(n - 1);111  const expectedCount = factorial(inputNums.length);112  113  if (outputArr.length === expectedCount || outputArr.length === expectedArr.length) {114    return {115      isValid: true,116      message: `Permutations: All ${outputArr.length} permutations are valid`,117      allValidOutputs: ['Multiple valid permutation sets possible']118    };119  }120  121  return null;122};123 124/**125 * Validate array with same elements (different order acceptable)126 */127const validateSameElements = (outputArr, expectedArr) => {128  if (!Array.isArray(outputArr) || !Array.isArray(expectedArr)) return null;129  if (Array.isArray(outputArr[0]) || Array.isArray(expectedArr[0])) return null;130  if (outputArr.length !== expectedArr.length) return null;131  132  const sortedOutput = [...outputArr].sort((a, b) => a - b).join(',');133  const sortedExpected = [...expectedArr].sort((a, b) => a - b).join(',');134  135  if (sortedOutput === sortedExpected) {136    return {137      isValid: true,138      message: 'Array contains same elements (order may differ)',139      allValidOutputs: ['Multiple orderings possible']140    };141  }142  143  return null;144};145 146/**147 * Validate Palindrome problems148 * Any palindrome of same length is valid149 */150const validatePalindrome = (output, expected, inputObj) => {151  if (typeof output !== 'string' || typeof expected !== 'string') return null;152  153  const isPalindrome = (s) => s === s.split('').reverse().join('');154  155  if (output.length === expected.length && 156      isPalindrome(output) && 157      isPalindrome(expected)) {158    return {159      isValid: true,160      message: `Palindrome: "${output}" is a valid palindrome of length ${output.length}`,161      allValidOutputs: ['Any palindrome of same length is valid']162    };163  }164  165  return null;166};167 168/**169 * Validate Subsets/Combinations170 * Order doesn't matter, but all subsets should be present171 */172const validateSubsets = (outputArr, expectedArr, inputObj) => {173  if (!Array.isArray(outputArr) || !Array.isArray(expectedArr)) return null;174  if (!Array.isArray(outputArr[0]) || !Array.isArray(expectedArr[0])) return null;175  176  // Normalize subsets (sort each subset and the array of subsets)177  const normalizeSubsets = (subsets) => {178    return subsets179      .map(s => [...s].sort((a, b) => a - b).join(','))180      .sort()181      .join('|');182  };183  184  const normalizedOutput = normalizeSubsets(outputArr);185  const normalizedExpected = normalizeSubsets(expectedArr);186  187  if (normalizedOutput === normalizedExpected) {188    return {189      isValid: true,190      message: `Subsets: All ${outputArr.length} subsets are valid`,191      allValidOutputs: ['Order of subsets may vary']192    };193  }194  195  return null;196};197 198/**199 * Validate Top K Elements200 * Any K elements with highest/lowest values are valid201 */202const validateTopK = (outputArr, expectedArr, inputObj) => {203  if (!Array.isArray(outputArr) || !Array.isArray(expectedArr)) return null;204  if (outputArr.length !== expectedArr.length) return null;205  206  // Check if output contains same elements (order doesn't matter)207  const sortedOutput = [...outputArr].sort((a, b) => a - b).join(',');208  const sortedExpected = [...expectedArr].sort((a, b) => a - b).join(',');209  210  if (sortedOutput === sortedExpected) {211    return {212      isValid: true,213      message: `Top K: Output contains correct ${outputArr.length} elements`,214      allValidOutputs: ['Order may vary']215    };216  }217  218  return null;219};220 221/**222 * Validate Graph Traversal (BFS/DFS)223 * Multiple valid traversal orders possible224 */225const validateGraphTraversal = (outputArr, expectedArr, inputObj) => {226  if (!Array.isArray(outputArr) || !Array.isArray(expectedArr)) return null;227  if (outputArr.length !== expectedArr.length) return null;228  229  // Check if all nodes are visited230  const outputSet = new Set(outputArr);231  const expectedSet = new Set(expectedArr);232  233  if (outputSet.size === expectedSet.size && 234      [...outputSet].every(node => expectedSet.has(node))) {235    return {236      isValid: true,237      message: `Graph Traversal: All ${outputArr.length} nodes visited`,238      allValidOutputs: ['Multiple valid traversal orders possible']239    };240  }241  242  return null;243};244 245/**246 * Validate Interval Merge247 * Merged intervals should cover same ranges248 */249const validateIntervalMerge = (outputArr, expectedArr, inputObj) => {250  if (!Array.isArray(outputArr) || !Array.isArray(expectedArr)) return null;251  if (!Array.isArray(outputArr[0]) || !Array.isArray(expectedArr[0])) return null;252  253  // Sort intervals by start time254  const sortIntervals = (intervals) => {255    return intervals256      .map(i => [...i])257      .sort((a, b) => a[0] - b[0])258      .map(i => i.join(','))259      .join('|');260  };261  262  const normalizedOutput = sortIntervals(outputArr);263  const normalizedExpected = sortIntervals(expectedArr);264  265  if (normalizedOutput === normalizedExpected) {266    return {267      isValid: true,268      message: `Interval Merge: ${outputArr.length} merged intervals are correct`,269      allValidOutputs: [JSON.stringify(expectedArr)]270    };271  }272  273  return null;274};275 276/**277 * Main validation function - tries all validators dynamically278 * This handles ALL problem types with multiple valid outputs279 */280const validateMultipleOutputs = (outputArr, expectedArr, inputObj) => {281  console.log('🔍 Dynamic Validation Started');282  console.log('   Output:', JSON.stringify(outputArr).substring(0, 100));283  console.log('   Expected:', JSON.stringify(expectedArr).substring(0, 100));284  console.log('   Input:', JSON.stringify(inputObj).substring(0, 100));285  286  // Try each validator in order of specificity287  const validators = [288    { name: 'Two Sum', fn: validateTwoSum },289    { name: 'Three Sum', fn: validateThreeSum },290    { name: 'Permutations', fn: validatePermutations },291    { name: 'Subsets', fn: validateSubsets },292    { name: 'Top K', fn: validateTopK },293    { name: 'Graph Traversal', fn: validateGraphTraversal },294    { name: 'Interval Merge', fn: validateIntervalMerge },295    { name: 'Palindrome', fn: validatePalindrome },296    { name: 'Same Elements', fn: validateSameElements }297  ];298  299  for (const { name, fn } of validators) {300    try {301      const result = fn(outputArr, expectedArr, inputObj);302      if (result && result.isValid) {303        console.log(`   ✅ Validated using: ${name}`);304        console.log(`   📝 ${result.message}`);305        return result;306      }307    } catch (error) {308      console.log(`   ⚠️ ${name} validator error:`, error.message);309      continue;310    }311  }312  313  console.log('   ❌ No matching validation rule found');314  return { isValid: false, message: 'No matching validation rule' };315};316 317/**318 * Normalize output for comparison319 */320const normalizeOutput = (output) => {321  if (typeof output !== 'string') return String(output);322  323  return output324    .trim()325    .replace(/^"|"$/g, '')  // Remove surrounding quotes326    .replace(/\s+/g, '')     // Remove whitespace327    .toLowerCase();328};329 330/**331 * Compare outputs with normalization332 */333const compareOutputs = (output, expected) => {334  // Direct comparison335  if (output === expected) return true;336  337  // Normalized comparison338  const normalizedOutput = normalizeOutput(output);339  const normalizedExpected = normalizeOutput(expected);340  341  if (normalizedOutput === normalizedExpected) return true;342  343  // Numeric comparison with decimal precision tolerance344  if (!isNaN(normalizedOutput) && !isNaN(normalizedExpected)) {345    const outputNum = Number(normalizedOutput);346    const expectedNum = Number(normalizedExpected);347    348    // For floating point numbers, use tolerance-based comparison349    // Tolerance: 1e-5 (0.00001) - handles 5 decimal places350    const tolerance = 1e-5;351    const diff = Math.abs(outputNum - expectedNum);352    353    if (diff < tolerance) {354      return true;355    }356    357    // Also check if they're equal when rounded to 5 decimal places358    const outputRounded = outputNum.toFixed(5);359    const expectedRounded = expectedNum.toFixed(5);360    361    return outputRounded === expectedRounded;362  }363  364  // Array comparison (for multiple valid outputs)365  try {366    const outputArr = JSON.parse(output);367    const expectedArr = JSON.parse(expected);368    369    if (Array.isArray(outputArr) && Array.isArray(expectedArr)) {370      return JSON.stringify(outputArr) === JSON.stringify(expectedArr);371    }372  } catch (e) {373    // Not valid JSON, skip374  }375  376  return false;377};378 379module.exports = {380  validateMultipleOutputs,381  normalizeOutput,382  compareOutputs,383  // Individual validators384  validateTwoSum,385  validateThreeSum,386  validatePermutations,387  validateSameElements,388  validatePalindrome,389  validateSubsets,390  validateTopK,391  validateGraphTraversal,392  validateIntervalMerge393};394