المهمة · سلاسل نصية صعب 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 مللي ثانية · $0.0053

  ✓	brace_expand("a{b,c}d")المتوقع ["abd", "acd"]	21 مللي ثانية
  ✓	brace_expand("{a,b}{c,d}")المتوقع ["ac", "ad", "bc", "bd"]	<1 مللي ثانية
  ✓	brace_expand("{a}")المتوقع ["{a}"]	2 مللي ثانية

  ✓ <1 مللي ثانية✓ 2 مللي ثانية✓ 1 مللي ثانية✓ 1 مللي ثانية✓ 2 مللي ثانية✓ 2 مللي ثانية✓ 2 مللي ثانية✓ 3 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ 2 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ 1 مللي ثانية✓ 1 مللي ثانية⏱ تجاوز الوقت المسموح⏱ 63 مللي ثانية⏱ 335 مللي ثانية
  الكود

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

  المحاولة الثانية

  غير محلولة · 21 من أصل 22 اختباراتتمت الإجابة في 13 ثوانٍ · $0.0074

  اطلع النموذج على عدد الاختبارات التي فشلت، مع الأمثلة الخاطئة وقيمها المتوقعة والراجعة، واطلع على سبب فشل الاختبارات الخفية فقط دون مدخلاتها. لا تؤثر هذه المحاولة في الترتيب أو التقييم.

  ✓	brace_expand("a{b,c}d")المتوقع ["abd", "acd"]	3 مللي ثانية
  ✓	brace_expand("{a,b}{c,d}")المتوقع ["ac", "ad", "bc", "bd"]	2 مللي ثانية
  ✓	brace_expand("{a}")المتوقع ["{a}"]	1 مللي ثانية

  ✓ <1 مللي ثانية✓ 1 مللي ثانية✓ 3 مللي ثانية✓ 2 مللي ثانية✓ 2 مللي ثانية✓ 2 مللي ثانية✓ 2 مللي ثانية✓ 1 مللي ثانية✓ 1 مللي ثانية✓ <1 مللي ثانية✓ 2 مللي ثانية✓ 2 مللي ثانية✓ 1 مللي ثانية✓ 2 مللي ثانية✓ 1 مللي ثانية✓ <1 مللي ثانية⏱ تجاوز الوقت المسموح⏱ 43 مللي ثانية⏱ 187 مللي ثانية

  الكود

  /**
   * @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 مللي ثانية · $0.0046

  ✓	brace_expand("a{b,c}d")المتوقع ["abd", "acd"]	3 مللي ثانية
  ✓	brace_expand("{a,b}{c,d}")المتوقع ["ac", "ad", "bc", "bd"]	1 مللي ثانية
  ✓	brace_expand("{a}")المتوقع ["{a}"]	2 مللي ثانية

  ✓ <1 مللي ثانية✓ 1 مللي ثانية✓ 1 مللي ثانية✓ 1 مللي ثانية✓ 6 مللي ثانية✓ 2 مللي ثانية✓ 2 مللي ثانية✓ 28 مللي ثانية✓ <1 مللي ثانية✓ 2 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ 3 مللي ثانية✓ 2 مللي ثانية✓ 1 مللي ثانية✓ 1 مللي ثانية⏱ تجاوز الوقت المسموح⏱ 53 مللي ثانية⏱ تجاوز الوقت المسموح
  الكود

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

  المحاولة الثانية

  غير محلولة · 20 من أصل 22 اختباراتتمت الإجابة في 11 ثوانٍ · $0.0064

  اطلع النموذج على عدد الاختبارات التي فشلت، مع الأمثلة الخاطئة وقيمها المتوقعة والراجعة، واطلع على سبب فشل الاختبارات الخفية فقط دون مدخلاتها. لا تؤثر هذه المحاولة في الترتيب أو التقييم.

  ✓	brace_expand("a{b,c}d")المتوقع ["abd", "acd"]	4 مللي ثانية
  ✓	brace_expand("{a,b}{c,d}")المتوقع ["ac", "ad", "bc", "bd"]	3 مللي ثانية
  ✓	brace_expand("{a}")المتوقع ["{a}"]	2 مللي ثانية

  ✓ 4 مللي ثانية✓ 2 مللي ثانية✗ إجابة خاطئة✓ 2 مللي ثانية✓ 3 مللي ثانية✓ 1 مللي ثانية✓ 2 مللي ثانية✓ 2 مللي ثانية✓ 1 مللي ثانية✓ <1 مللي ثانية✓ 1 مللي ثانية✓ 1 مللي ثانية✓ 2 مللي ثانية✓ 1 مللي ثانية✓ 1 مللي ثانية✓ 1 مللي ثانية⏱ تجاوز الوقت المسموح⏱ 68 مللي ثانية⏱ 208 مللي ثانية

  الكود

  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 · كيف تُدار الجولات وتُحتسب النقاط ←