टास्क · स्ट्रिंग्स कठिन JavaScript ·

Brace expansion

/**
 * @param {string} s
 * @returns {string[]}
 */
function brace_expand(s)

brace_expand("a{b,c}d")  // -> ["abd", "acd"]
brace_expand("{a,b}{c,d}")  // -> ["ac", "ad", "bc", "bd"]
brace_expand("{a}")  // -> ["{a}"]

• #1Google Gemini 3.8 Flashहल नहीं हुआ · 22 में से 21 टेस्ट्स पासजवाब का समय 9.6 s · रनटाइम 743 ms · $0.0053

  ✓	brace_expand("a{b,c}d")अपेक्षित ["abd", "acd"]	21 ms
  ✓	brace_expand("{a,b}{c,d}")अपेक्षित ["ac", "ad", "bc", "bd"]	<1 ms
  ✓	brace_expand("{a}")अपेक्षित ["{a}"]	2 ms

  ✓ <1 ms✓ 2 ms✓ 1 ms✓ 1 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ 3 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ 1 ms⏱ समय सीमा समाप्त (time limit exceeded)⏱ 63 ms⏱ 335 ms
  कोड

  /**
   * @param {string} s
   * @returns {string[]}
   */
  function brace_expand(s) {
    const n = s.length;
    // Step 1: Match braces
    // Braces are matched left to right: each '}' closes nearest unclosed '{'.
    // Unmatched braces are ordinary characters.
    const match = new Int32Array(n).fill(-1);
    const stack = [];
    for (let i = 0; i < n; i++) {
      if (s.charCodeAt(i) === 123) { // '{'
        stack.push(i);
      } else if (s.charCodeAt(i) === 125) { // '}'
        if (stack.length > 0) {
          const open = stack.pop();
          match[open] = i;
          match[i] = open;
        }
      }
    }
  
    // Step 2: Determine for each matched '{' whether it is a valid group (has comma directly inside)
    const isGroup = new Uint8Array(n);
    for (let i = 0; i < n; i++) {
      if (s.charCodeAt(i) === 123 && match[i] !== -1) {
        const close = match[i];
        let hasComma = false;
        let j = i + 1;
        while (j < close) {
          const c = s.charCodeAt(j);
          if (c === 44) { // ','
            hasComma = true;
            break;
          }
          if (c === 123 && match[j] !== -1) {
            j = match[j] + 1;
          } else {
            j++;
          }
        }
        if (hasComma) {
          isGroup[i] = 1;
        }
      }
    }
  
    // Parse [start, end) into an AST or expand directly
    // Note: result has at most 100,000 strings.
    // Recursion depth up to 300 levels deep.
    function expand(start, end) {
      // Collect sequence of parts
      const parts = [];
      let i = start;
      let literalBuf = '';
  
      while (i < end) {
        const c = s.charCodeAt(i);
        if (c === 123 && match[i] !== -1 && match[i] < end) {
          const close = match[i];
          if (isGroup[i]) {
            if (literalBuf.length > 0) {
              parts.push([literalBuf]);
              literalBuf = '';
            }
            // Split by top-level commas inside [i + 1, close)
            const alternatives = [];
            let segStart = i + 1;
            let k = i + 1;
            while (k < close) {
              const kc = s.charCodeAt(k);
              if (kc === 44) { // ','
                alternatives.push(expand(segStart, k));
                segStart = k + 1;
                k++;
              } else if (kc === 123 && match[k] !== -1 && match[k] < close) {
                k = match[k] + 1;
              } else {
                k++;
              }
            }
            alternatives.push(expand(segStart, close));
            
            // Flatten alternatives
            const groupRes = [];
            for (const alt of alternatives) {
              for (let a = 0; a < alt.length; a++) {
                groupRes.push(alt[a]);
              }
            }
            parts.push(groupRes);
            i = close + 1;
          } else {
            // Matched pair without top-level comma: kept literally, braces included,
            // though groups inside it still expand!
            // "{a}" -> literal '{', expand(a), literal '}'
            if (literalBuf.length > 0) {
              parts.push([literalBuf]);
              literalBuf = '';
            }
            const inner = expand(i + 1, close);
            const preserved = new Array(inner.length);
            for (let idx = 0; idx < inner.length; idx++) {
              preserved[idx] = '{' + inner[idx] + '}';
            }
            parts.push(preserved);
            i = close + 1;
          }
        } else {
          literalBuf += s[i];
          i++;
        }
      }
  
      if (literalBuf.length > 0) {
        parts.push([literalBuf]);
      }
  
      if (parts.length === 0) {
        return [''];
      }
  
      // Cartesian product of parts
      let current = parts[0];
      for (let p = 1; p < parts.length; p++) {
        const nextPart = parts[p];
        const nextLen = nextPart.length;
        const curLen = current.length;
        const combined = new Array(curLen * nextLen);
        let ptr = 0;
        for (let cIdx = 0; cIdx < curLen; cIdx++) {
          const prefix = current[cIdx];
          for (let nIdx = 0; nIdx < nextLen; nIdx++) {
            combined[ptr++] = prefix + nextPart[nIdx];
          }
        }
        current = combined;
      }
  
      return current;
    }
  
    return expand(0, n);
  }

  दूसरा प्रयास

  हल नहीं हुआ · 22 में से 21 टेस्ट्स पासजवाब का समय 13 s · $0.0074

  मॉडल को दिखाया गया कि कितने टेस्ट फेल हुए, फेल हुए उदाहरणों के अपेक्षित और मिले हुए परिणाम क्या थे, और छिपे हुए टेस्ट्स के फेल होने का सिर्फ़ कारण (इनपुट्स नहीं)। यह रैंकिंग या रेटिंग में नहीं गिना जाता।

  ✓	brace_expand("a{b,c}d")अपेक्षित ["abd", "acd"]	3 ms
  ✓	brace_expand("{a,b}{c,d}")अपेक्षित ["ac", "ad", "bc", "bd"]	2 ms
  ✓	brace_expand("{a}")अपेक्षित ["{a}"]	1 ms

  ✓ <1 ms✓ 1 ms✓ 3 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 1 ms✓ 2 ms✓ 1 ms✓ <1 ms⏱ समय सीमा समाप्त (time limit exceeded)⏱ 43 ms⏱ 187 ms

  कोड

  /**
   * @param {string} s
   * @returns {string[]}
   */
  function brace_expand(s) {
    const n = s.length;
    if (n === 0) return [''];
  
    const match = new Int32Array(n).fill(-1);
    const stack = [];
    for (let i = 0; i < n; i++) {
      const code = s.charCodeAt(i);
      if (code === 123) { // '{'
        stack.push(i);
      } else if (code === 125) { // '}'
        if (stack.length > 0) {
          const open = stack.pop();
          match[open] = i;
          match[i] = open;
        }
      }
    }
  
    // Check if each matched brace contains any unnested comma or groups inside
    // hasGroup[i] = whether anything expands inside (groups or nested groups)
    const isGroup = new Uint8Array(n);
    const hasExpansion = new Uint8Array(n);
  
    for (let i = n - 1; i >= 0; i--) {
      if (s.charCodeAt(i) === 123 && match[i] !== -1) {
        const close = match[i];
        let hasComma = false;
        let anyExpand = false;
        let j = i + 1;
        while (j < close) {
          const c = s.charCodeAt(j);
          if (c === 44) {
            hasComma = true;
            j++;
          } else if (c === 123 && match[j] !== -1 && match[j] < close) {
            if (isGroup[j] || hasExpansion[j]) {
              anyExpand = true;
            }
            j = match[j] + 1;
          } else {
            j++;
          }
        }
        if (hasComma) {
          isGroup[i] = 1;
          hasExpansion[i] = 1;
        } else if (anyExpand) {
          hasExpansion[i] = 1;
        }
      }
    }
  
    // Quick check: does the whole string have any group expansion?
    let hasAnyGroup = false;
    for (let i = 0; i < n; i++) {
      if (isGroup[i]) {
        hasAnyGroup = true;
        break;
      }
    }
    if (!hasAnyGroup) {
      return [s];
    }
  
    function expand(start, end) {
      const parts = [];
      let i = start;
      let litStart = start;
  
      while (i < end) {
        const c = s.charCodeAt(i);
        if (c === 123 && match[i] !== -1 && match[i] < end) {
          const close = match[i];
          if (isGroup[i]) {
            if (i > litStart) {
              parts.push([s.slice(litStart, i)]);
            }
  
            const groupRes = [];
            let segStart = i + 1;
            let k = i + 1;
            while (k < close) {
              const kc = s.charCodeAt(k);
              if (kc === 44) {
                const alt = expand(segStart, k);
                for (let a = 0; a < alt.length; a++) groupRes.push(alt[a]);
                segStart = k + 1;
                k++;
              } else if (kc === 123 && match[k] !== -1 && match[k] < close) {
                k = match[k] + 1;
              } else {
                k++;
              }
            }
            const lastAlt = expand(segStart, close);
            for (let a = 0; a < lastAlt.length; a++) groupRes.push(lastAlt[a]);
  
            parts.push(groupRes);
            i = close + 1;
            litStart = i;
          } else if (hasExpansion[i]) {
            if (i > litStart) {
              parts.push([s.slice(litStart, i)]);
            }
            const inner = expand(i + 1, close);
            const preserved = new Array(inner.length);
            for (let idx = 0; idx < inner.length; idx++) {
              preserved[idx] = '{' + inner[idx] + '}';
            }
            parts.push(preserved);
            i = close + 1;
            litStart = i;
          } else {
            // No expansion inside this brace pair, treat entire { ... } as literal
            i = close + 1;
          }
        } else {
          i++;
        }
      }
  
      if (i > litStart) {
        parts.push([s.slice(litStart, i)]);
      }
  
      if (parts.length === 0) {
        return [''];
      }
  
      let current = parts[0];
      for (let p = 1; p < parts.length; p++) {
        const nextPart = parts[p];
        const nextLen = nextPart.length;
        const curLen = current.length;
  
        if (curLen === 1 && current[0] === '') {
          current = nextPart;
          continue;
        }
        if (nextLen === 1 && nextPart[0] === '') {
          continue;
        }
  
        if (nextLen === 1) {
          const suffix = nextPart[0];
          const combined = new Array(curLen);
          for (let cIdx = 0; cIdx < curLen; cIdx++) {
            combined[cIdx] = current[cIdx] + suffix;
          }
          current = combined;
        } else if (curLen === 1) {
          const prefix = current[0];
          const combined = new Array(nextLen);
          for (let nIdx = 0; nIdx < nextLen; nIdx++) {
            combined[nIdx] = prefix + nextPart[nIdx];
          }
          current = combined;
        } else {
          const combined = new Array(curLen * nextLen);
          let ptr = 0;
          for (let cIdx = 0; cIdx < curLen; cIdx++) {
            const prefix = current[cIdx];
            for (let nIdx = 0; nIdx < nextLen; nIdx++) {
              combined[ptr++] = prefix + nextPart[nIdx];
            }
          }
          current = combined;
        }
      }
  
      return current;
    }
  
    return expand(0, n);
  }

• #2OpenAI GPT-6.1 Terraहल नहीं हुआ · 22 में से 20 टेस्ट्स पासजवाब का समय 10 s · रनटाइम 781 ms · $0.0046

  ✓	brace_expand("a{b,c}d")अपेक्षित ["abd", "acd"]	3 ms
  ✓	brace_expand("{a,b}{c,d}")अपेक्षित ["ac", "ad", "bc", "bd"]	1 ms
  ✓	brace_expand("{a}")अपेक्षित ["{a}"]	2 ms

  ✓ <1 ms✓ 1 ms✓ 1 ms✓ 1 ms✓ 6 ms✓ 2 ms✓ 2 ms✓ 28 ms✓ <1 ms✓ 2 ms✓ <1 ms✓ <1 ms✓ 3 ms✓ 2 ms✓ 1 ms✓ 1 ms⏱ समय सीमा समाप्त (time limit exceeded)⏱ 53 ms⏱ समय सीमा समाप्त (time limit exceeded)
  कोड

  function brace_expand(s) {
    const n = s.length;
    const match = new Int32Array(n);
    match.fill(-1);
  
    const stack = [];
    for (let i = 0; i < n; i++) {
      const c = s.charCodeAt(i);
      if (c === 123) {
        stack.push(i);
      } else if (c === 125 && stack.length) {
        const open = stack.pop();
        match[open] = i;
      }
    }
  
    // Parse matched pairs into concatenation and alternative nodes.
    // Unmatched braces are included in literal substrings.
    const root = { parts: [], start: 0, open: -1, alternatives: null };
    const frames = [root];
  
    for (let i = 0; i < n; i++) {
      const frame = frames[frames.length - 1];
      const c = s.charCodeAt(i);
  
      if (c === 123 && match[i] !== -1) {
        if (frame.start < i) frame.parts.push(s.slice(frame.start, i));
        frames.push({ parts: [], start: i + 1, open: i, alternatives: null });
      } else if (c === 44 && frame.open !== -1) {
        if (frame.start < i) frame.parts.push(s.slice(frame.start, i));
        if (frame.alternatives === null) frame.alternatives = [];
        frame.alternatives.push(frame.parts);
        frame.parts = [];
        frame.start = i + 1;
      } else if (c === 125 && frame.open !== -1 && match[frame.open] === i) {
        if (frame.start < i) frame.parts.push(s.slice(frame.start, i));
        frames.pop();
  
        let node;
        if (frame.alternatives !== null) {
          frame.alternatives.push(frame.parts);
          node = { alternatives: frame.alternatives };
        } else {
          node = { literalBraces: true, parts: frame.parts };
        }
  
        const parent = frames[frames.length - 1];
        parent.parts.push(node);
        parent.start = i + 1;
      }
    }
    if (root.start < n) root.parts.push(s.slice(root.start));
  
    function combine(left, right) {
      if (right.length === 1 && right[0] === "") return left;
      if (left.length === 1 && left[0] === "") return right;
      const result = new Array(left.length * right.length);
      let k = 0;
      for (let i = 0; i < left.length; i++) {
        for (let j = 0; j < right.length; j++) {
          result[k++] = left[i] + right[j];
        }
      }
      return result;
    }
  
    function expandParts(parts) {
      let result = [""];
      for (let i = 0; i < parts.length; i++) {
        const part = parts[i];
        let values;
        if (typeof part === "string") {
          values = [part];
        } else if (part.literalBraces) {
          values = expandParts(part.parts);
          for (let j = 0; j < values.length; j++) {
            values[j] = "{" + values[j] + "}";
          }
        } else {
          values = [];
          for (let j = 0; j < part.alternatives.length; j++) {
            const expanded = expandParts(part.alternatives[j]);
            for (let k = 0; k < expanded.length; k++) values.push(expanded[k]);
          }
        }
        result = combine(result, values);
      }
      return result;
    }
  
    return expandParts(root.parts);
  }

  दूसरा प्रयास

  हल नहीं हुआ · 22 में से 20 टेस्ट्स पासजवाब का समय 11 s · $0.0064

  मॉडल को दिखाया गया कि कितने टेस्ट फेल हुए, फेल हुए उदाहरणों के अपेक्षित और मिले हुए परिणाम क्या थे, और छिपे हुए टेस्ट्स के फेल होने का सिर्फ़ कारण (इनपुट्स नहीं)। यह रैंकिंग या रेटिंग में नहीं गिना जाता।

  ✓	brace_expand("a{b,c}d")अपेक्षित ["abd", "acd"]	4 ms
  ✓	brace_expand("{a,b}{c,d}")अपेक्षित ["ac", "ad", "bc", "bd"]	3 ms
  ✓	brace_expand("{a}")अपेक्षित ["{a}"]	2 ms

  ✓ 4 ms✓ 2 ms✗ गलत उत्तर✓ 2 ms✓ 3 ms✓ 1 ms✓ 2 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ 2 ms✓ 1 ms✓ 1 ms✓ 1 ms⏱ समय सीमा समाप्त (time limit exceeded)⏱ 68 ms⏱ 208 ms

  कोड

  function brace_expand(s) {
    const n = s.length;
    const match = new Int32Array(n);
    match.fill(-1);
    const stack = [];
  
    for (let i = 0; i < n; i++) {
      const c = s.charCodeAt(i);
      if (c === 123) {
        stack.push(i);
      } else if (c === 125 && stack.length) {
        match[stack.pop()] = i;
      }
    }
  
    const root = { parts: [], start: 0, open: -1, alternatives: null };
    const frames = [root];
  
    for (let i = 0; i < n; i++) {
      const frame = frames[frames.length - 1];
      const c = s.charCodeAt(i);
  
      if (c === 123 && match[i] !== -1) {
        if (frame.start < i) frame.parts.push(s.slice(frame.start, i));
        frames.push({ parts: [], start: i + 1, open: i, alternatives: null });
      } else if (c === 44 && frame.open !== -1) {
        if (frame.start < i) frame.parts.push(s.slice(frame.start, i));
        if (frame.alternatives === null) frame.alternatives = [];
        frame.alternatives.push(frame.parts);
        frame.parts = [];
        frame.start = i + 1;
      } else if (c === 125 && frame.open !== -1 && match[frame.open] === i) {
        if (frame.start < i) frame.parts.push(s.slice(frame.start, i));
        frames.pop();
  
        const parent = frames[frames.length - 1];
        if (frame.alternatives === null) {
          parent.parts.push("{");
          for (let j = 0; j < frame.parts.length; j++) {
            parent.parts.push(frame.parts[j]);
          }
          parent.parts.push("}");
        } else {
          frame.alternatives.push(frame.parts);
          parent.parts.push(frame.alternatives);
        }
        parent.start = i + 1;
      }
    }
    if (root.start < n) root.parts.push(s.slice(root.start));
  
    // Compile the expression into a sequence of literals and choice points.
    // Each alternative ends with a jump to the continuation.
    const code = [];
  
    function compile(parts) {
      let pending = "";
      function flush() {
        if (pending) {
          code.push(pending);
          pending = "";
        }
      }
  
      for (let i = 0; i < parts.length; i++) {
        const part = parts[i];
        if (typeof part === "string") {
          pending += part;
        } else {
          flush();
          const choice = { branches: [] };
          code.push(choice);
          const jumps = [];
  
          for (let j = 0; j < part.length; j++) {
            choice.branches.push(code.length);
            compile(part[j]);
            if (j + 1 < part.length) {
              const jump = { target: 0 };
              jumps.push(jump);
              code.push(jump);
            }
          }
          const end = code.length;
          for (let j = 0; j < jumps.length; j++) jumps[j].target = end;
        }
      }
      flush();
    }
  
    compile(root.parts);
  
    const results = [];
    const pieces = [];
    const choices = [];
    let pc = 0;
  
    while (true) {
      while (pc < code.length) {
        const instruction = code[pc];
        if (typeof instruction === "string") {
          pieces.push(instruction);
          pc++;
        } else if (instruction.branches) {
          const branches = instruction.branches;
          if (branches.length > 1) {
            choices.push({ branches, next: 1, length: pieces.length });
          }
          pc = branches[0];
        } else {
          pc = instruction.target;
        }
      }
  
      results.push(pieces.join(""));
  
      while (choices.length) {
        const choice = choices[choices.length - 1];
        pieces.length = choice.length;
        pc = choice.branches[choice.next++];
        if (choice.next === choice.branches.length) choices.pop();
        break;
      }
      if (!choices.length && pc >= code.length) break;
    }
  
    return results;
  }

• #3MoonshotAI Kimi K2.7 Codeहल नहीं हुआ · 22 में से 0 टेस्ट्स पासजवाब का समय 27 s · $0.02

  कोड खत्म होने से पहले ही उत्तर कट गया

  ✗	brace_expand("a{b,c}d")अपेक्षित ["abd", "acd"]उत्तर में कोई कोड नहीं मिला	—
  ✗	brace_expand("{a,b}{c,d}")अपेक्षित ["ac", "ad", "bc", "bd"]उत्तर में कोई कोड नहीं मिला	—
  ✗	brace_expand("{a}")अपेक्षित ["{a}"]उत्तर में कोई कोड नहीं मिला	—

  ✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला⏱ उत्तर में कोई कोड नहीं मिला⏱ उत्तर में कोई कोड नहीं मिला⏱ उत्तर में कोई कोड नहीं मिला
• #3SpaceXAI Grok 4.7हल नहीं हुआ · 22 में से 0 टेस्ट्स पासजवाब का समय 120 s

  उत्तर में कोई कोड नहीं मिला

  ✗	brace_expand("a{b,c}d")अपेक्षित ["abd", "acd"]उत्तर में कोई कोड नहीं मिला	—
  ✗	brace_expand("{a,b}{c,d}")अपेक्षित ["ac", "ad", "bc", "bd"]उत्तर में कोई कोड नहीं मिला	—
  ✗	brace_expand("{a}")अपेक्षित ["{a}"]उत्तर में कोई कोड नहीं मिला	—

  ✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला⏱ उत्तर में कोई कोड नहीं मिला⏱ उत्तर में कोई कोड नहीं मिला⏱ उत्तर में कोई कोड नहीं मिला

टोकन लागत: $0.04 · राउंड कैसे आयोजित और स्कोर किए जाते हैं →