Tugas · string sulit 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 Flashtidak selesai · 21 dari 22 pengujianrespons dalam 9.6 dtk · waktu eksekusi 743 md · $0.0053

  ✓	brace_expand("a{b,c}d")diharapkan ["abd", "acd"]	21 md
  ✓	brace_expand("{a,b}{c,d}")diharapkan ["ac", "ad", "bc", "bd"]	<1 md
  ✓	brace_expand("{a}")diharapkan ["{a}"]	2 md

  ✓ <1 md✓ 2 md✓ 1 md✓ 1 md✓ 2 md✓ 2 md✓ 2 md✓ 3 md✓ <1 md✓ <1 md✓ <1 md✓ 2 md✓ <1 md✓ <1 md✓ 1 md✓ 1 md⏱ batas waktu terlampaui⏱ 63 md⏱ 335 md
  Kode

  /**
   * @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);
  }

  Percobaan kedua

  tidak selesai · 21 dari 22 pengujianrespons dalam 13 dtk · $0.0074

  Model melihat berapa banyak tes yang gagal, contoh yang gagal beserta nilai yang diharapkan dan yang dihasilkan, serta hanya alasan mengapa tes tersembunyi gagal, bukan inputnya. Tidak memengaruhi peringkat atau rating.

  ✓	brace_expand("a{b,c}d")diharapkan ["abd", "acd"]	3 md
  ✓	brace_expand("{a,b}{c,d}")diharapkan ["ac", "ad", "bc", "bd"]	2 md
  ✓	brace_expand("{a}")diharapkan ["{a}"]	1 md

  ✓ <1 md✓ 1 md✓ 3 md✓ 2 md✓ 2 md✓ 2 md✓ 2 md✓ 1 md✓ 1 md✓ <1 md✓ 2 md✓ 2 md✓ 1 md✓ 2 md✓ 1 md✓ <1 md⏱ batas waktu terlampaui⏱ 43 md⏱ 187 md

  Kode

  /**
   * @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 Terratidak selesai · 20 dari 22 pengujianrespons dalam 10 dtk · waktu eksekusi 781 md · $0.0046

  ✓	brace_expand("a{b,c}d")diharapkan ["abd", "acd"]	3 md
  ✓	brace_expand("{a,b}{c,d}")diharapkan ["ac", "ad", "bc", "bd"]	1 md
  ✓	brace_expand("{a}")diharapkan ["{a}"]	2 md

  ✓ <1 md✓ 1 md✓ 1 md✓ 1 md✓ 6 md✓ 2 md✓ 2 md✓ 28 md✓ <1 md✓ 2 md✓ <1 md✓ <1 md✓ 3 md✓ 2 md✓ 1 md✓ 1 md⏱ batas waktu terlampaui⏱ 53 md⏱ batas waktu terlampaui
  Kode

  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);
  }

  Percobaan kedua

  tidak selesai · 20 dari 22 pengujianrespons dalam 11 dtk · $0.0064

  Model melihat berapa banyak tes yang gagal, contoh yang gagal beserta nilai yang diharapkan dan yang dihasilkan, serta hanya alasan mengapa tes tersembunyi gagal, bukan inputnya. Tidak memengaruhi peringkat atau rating.

  ✓	brace_expand("a{b,c}d")diharapkan ["abd", "acd"]	4 md
  ✓	brace_expand("{a,b}{c,d}")diharapkan ["ac", "ad", "bc", "bd"]	3 md
  ✓	brace_expand("{a}")diharapkan ["{a}"]	2 md

  ✓ 4 md✓ 2 md✗ jawaban salah✓ 2 md✓ 3 md✓ 1 md✓ 2 md✓ 2 md✓ 1 md✓ <1 md✓ 1 md✓ 1 md✓ 2 md✓ 1 md✓ 1 md✓ 1 md⏱ batas waktu terlampaui⏱ 68 md⏱ 208 md

  Kode

  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 Codetidak selesai · 0 dari 22 pengujianrespons dalam 27 dtk · $0.02

  jawaban terpotong sebelum kode selesai

  ✗	brace_expand("a{b,c}d")diharapkan ["abd", "acd"]tidak ada kode dalam jawaban	—
  ✗	brace_expand("{a,b}{c,d}")diharapkan ["ac", "ad", "bc", "bd"]tidak ada kode dalam jawaban	—
  ✗	brace_expand("{a}")diharapkan ["{a}"]tidak ada kode dalam jawaban	—

  ✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban⏱ tidak ada kode dalam jawaban⏱ tidak ada kode dalam jawaban⏱ tidak ada kode dalam jawaban
• #3SpaceXAI Grok 4.7tidak selesai · 0 dari 22 pengujianrespons dalam 120 dtk

  tidak ada kode dalam jawaban

  ✗	brace_expand("a{b,c}d")diharapkan ["abd", "acd"]tidak ada kode dalam jawaban	—
  ✗	brace_expand("{a,b}{c,d}")diharapkan ["ac", "ad", "bc", "bd"]tidak ada kode dalam jawaban	—
  ✗	brace_expand("{a}")diharapkan ["{a}"]tidak ada kode dalam jawaban	—

  ✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban✗ tidak ada kode dalam jawaban⏱ tidak ada kode dalam jawaban⏱ tidak ada kode dalam jawaban⏱ tidak ada kode dalam jawaban

Biaya token: $0.04 · Cara babak dijalankan dan dinilai →