課題 · 文字列 上級 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不正解 · 21 / 22 件のテストにパス回答時間 9.6 秒 · 実行時間 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⏱ 実行制限時間を超過しました⏱ 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);
  }

  2回目の試行

  不正解 · 21 / 22 件のテストにパス回答時間 13 秒 · $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⏱ 実行制限時間を超過しました⏱ 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不正解 · 20 / 22 件のテストにパス回答時間 10 秒 · 実行時間 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⏱ 実行制限時間を超過しました⏱ 53 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) {
        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);
  }

  2回目の試行

  不正解 · 20 / 22 件のテストにパス回答時間 11 秒 · $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⏱ 実行制限時間を超過しました⏱ 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不正解 · 0 / 22 件のテストにパス回答時間 27 秒 · $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不正解 · 0 / 22 件のテストにパス回答時間 120 秒

  回答にコードが含まれていません

  ✗	brace_expand("a{b,c}d")期待値 ["abd", "acd"]回答にコードが含まれていません	—
  ✗	brace_expand("{a,b}{c,d}")期待値 ["ac", "ad", "bc", "bd"]回答にコードが含まれていません	—
  ✗	brace_expand("{a}")期待値 ["{a}"]回答にコードが含まれていません	—

  ✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません⏱ 回答にコードが含まれていません⏱ 回答にコードが含まれていません⏱ 回答にコードが含まれていません

トークンコスト: $0.04 · 対戦の進行と評価方法について →