Task · strings hard 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 Flashnot solved · 21 of 22 testsanswer in 9.6 s · runtime 743 ms · $0.0053

  ✓	brace_expand("a{b,c}d")expected ["abd", "acd"]	21 ms
  ✓	brace_expand("{a,b}{c,d}")expected ["ac", "ad", "bc", "bd"]	<1 ms
  ✓	brace_expand("{a}")expected ["{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
  Code

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

  Second try

  not solved · 21 of 22 testsanswer in 13 s · $0.0074

  The model saw how many tests failed, the failing examples with the expected and returned values, and only why hidden tests failed, not their inputs. Doesn't count for places or the rating.

  ✓	brace_expand("a{b,c}d")expected ["abd", "acd"]	3 ms
  ✓	brace_expand("{a,b}{c,d}")expected ["ac", "ad", "bc", "bd"]	2 ms
  ✓	brace_expand("{a}")expected ["{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

  Code

  /**
   * @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 Terranot solved · 20 of 22 testsanswer in 10 s · runtime 781 ms · $0.0046

  ✓	brace_expand("a{b,c}d")expected ["abd", "acd"]	3 ms
  ✓	brace_expand("{a,b}{c,d}")expected ["ac", "ad", "bc", "bd"]	1 ms
  ✓	brace_expand("{a}")expected ["{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
  Code

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

  Second try

  not solved · 20 of 22 testsanswer in 11 s · $0.0064

  The model saw how many tests failed, the failing examples with the expected and returned values, and only why hidden tests failed, not their inputs. Doesn't count for places or the rating.

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

  ✓ 4 ms✓ 2 ms✗ wrong answer✓ 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

  Code

  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 Codenot solved · 0 of 22 testsanswer in 27 s · $0.02

  the answer was cut off before the code ended

  ✗	brace_expand("a{b,c}d")expected ["abd", "acd"]no code in the answer	—
  ✗	brace_expand("{a,b}{c,d}")expected ["ac", "ad", "bc", "bd"]no code in the answer	—
  ✗	brace_expand("{a}")expected ["{a}"]no code in the answer	—

  ✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer⏱ no code in the answer⏱ no code in the answer⏱ no code in the answer
• #3SpaceXAI Grok 4.7not solved · 0 of 22 testsanswer in 120 s

  no code in the answer

  ✗	brace_expand("a{b,c}d")expected ["abd", "acd"]no code in the answer	—
  ✗	brace_expand("{a,b}{c,d}")expected ["ac", "ad", "bc", "bd"]no code in the answer	—
  ✗	brace_expand("{a}")expected ["{a}"]no code in the answer	—

  ✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer⏱ no code in the answer⏱ no code in the answer⏱ no code in the answer

Tokens cost: $0.04 · How rounds are run and scored →