المهمة · خوارزميات صعب JavaScript ·

Most points on one line

/**
 * @param {number[][]} points
 * @returns {number}
 */
function max_collinear(points)

max_collinear([[1, 1], [2, 2], [3, 3]])  // -> 3
max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])  // -> 4

• المركز 1Anthropic Claude Sonnet 5.5محلولة · 12 من أصل 12 اختباراتتمت الإجابة في 7.6 ثوانٍ · زمن التشغيل 888 مللي ثانية · $0.01

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])المتوقع 3	2 مللي ثانية
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])المتوقع 4	<1 مللي ثانية

  ✓ 1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ 2 مللي ثانية✓ 2 مللي ثانية✓ 1 مللي ثانية✓ 5 مللي ثانية✓ <1 مللي ثانية✓ 3 مللي ثانية⏱ 868 مللي ثانية
  الكود

  function max_collinear(points) {
    const n = points.length;
    if (n <= 2) return n;
    let best = 1;
    for (let i = 0; i < n; i++) {
      if (n - i <= best) break;
      const xi = points[i][0], yi = points[i][1];
      const map = new Map();
      let dup = 1;
      let localMax = 0;
      for (let j = i + 1; j < n; j++) {
        let dx = points[j][0] - xi;
        let dy = points[j][1] - yi;
        if (dx === 0 && dy === 0) { dup++; continue; }
        let a = dx < 0 ? -dx : dx, b = dy < 0 ? -dy : dy;
        while (b) { const t = a % b; a = b; b = t; }
        dx /= a; dy /= a;
        if (dx < 0 || (dx === 0 && dy < 0)) { dx = -dx; dy = -dy; }
        const key = dx + "," + dy;
        const c = (map.get(key) || 0) + 1;
        map.set(key, c);
        if (c > localMax) localMax = c;
      }
      const total = localMax + dup;
      if (total > best) best = total;
    }
    return best;
  }

• المركز 1OpenAI GPT-5.3-Codexمحلولة · 12 من أصل 12 اختباراتتمت الإجابة في 5.4 ثوانٍ · زمن التشغيل 1.0 ثوانٍ · $0.0069

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])المتوقع 3	2 مللي ثانية
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])المتوقع 4	2 مللي ثانية

  ✓ 2 مللي ثانية✓ 1 مللي ثانية✓ <1 مللي ثانية✓ 1 مللي ثانية✓ 2 مللي ثانية✓ 1 مللي ثانية✓ 2 مللي ثانية✓ 1 مللي ثانية✓ 1 مللي ثانية⏱ 1.0 ثوانٍ
  الكود

  /**
   * @param {number[][]} points
   * @returns {number}
   */
  function max_collinear(points) {
    const n = points.length;
    if (n <= 2) return n;
  
    let globalBest = 1;
  
    for (let i = 0; i < n; i++) {
      // Early stop: even if all remaining points align with i, can't beat current best
      if (globalBest >= n - i) break;
  
      const [x1, y1] = points[i];
      let duplicates = 0;
      let localBest = 0;
      const map = new Map();
  
      for (let j = i + 1; j < n; j++) {
        let dx = points[j][0] - x1;
        let dy = points[j][1] - y1;
  
        if (dx === 0 && dy === 0) {
          duplicates++;
          continue;
        }
  
        // Normalize slope as reduced integer pair (dy, dx)
        const g = gcd(Math.abs(dx), Math.abs(dy));
        dx /= g;
        dy /= g;
  
        // Canonical sign: dx > 0, or dx == 0 and dy > 0
        if (dx < 0 || (dx === 0 && dy < 0)) {
          dx = -dx;
          dy = -dy;
        }
  
        const key = dy + "/" + dx;
        const cnt = (map.get(key) || 0) + 1;
        map.set(key, cnt);
        if (cnt > localBest) localBest = cnt;
      }
  
      // +1 for pivot point itself; +duplicates for identical points to pivot
      const bestThroughI = localBest + duplicates + 1;
      if (bestThroughI > globalBest) globalBest = bestThroughI;
    }
  
    return globalBest;
  }
  
  function gcd(a, b) {
    while (b !== 0) {
      const t = a % b;
      a = b;
      b = t;
    }
    return a === 0 ? 1 : a;
  }

• المركز 3SpaceXAI Grok Build 0.1غير محلولة · 11 من أصل 12 اختباراتتمت الإجابة في 54 ثوانٍ · زمن التشغيل 1.2 ثوانٍ · $0.02

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])المتوقع 3	2 مللي ثانية
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])المتوقع 4	1 مللي ثانية

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

  function max_collinear(points) {
    const n = points.length;
    if (n === 0) return 0;
    let pointFreq = {};
    for (let p of points) {
      let key = p[0] + "," + p[1];
      pointFreq[key] = (pointFreq[key] || 0) + 1;
    }
    let unique = [];
    for (let key in pointFreq) {
      let parts = key.split(",");
      let x = Number(parts[0]);
      let y = Number(parts[1]);
      unique.push([x, y, pointFreq[key]]);
    }
    let m = unique.length;
    function gcd(a, b) {
      a = Math.abs(a);
      b = Math.abs(b);
      while (b !== 0) {
        let t = b;
        b = a % b;
        a = t;
      }
      return a;
    }
    let maxPoints = 0;
    for (let i = 0; i < m; i++) {
      let slopeCount = {};
      for (let j = 0; j < m; j++) {
        if (i === j) continue;
        let dx = unique[j][0] - unique[i][0];
        let dy = unique[j][1] - unique[i][1];
        let g = gcd(dx, dy);
        if (g === 0) continue;
        dx = Math.trunc(dx / g);
        dy = Math.trunc(dy / g);
        if (dx < 0 || (dx === 0 && dy < 0)) {
          dx = -dx;
          dy = -dy;
        }
        let key = dx + "," + dy;
        slopeCount[key] = (slopeCount[key] || 0) + unique[j][2];
      }
      let curr = unique[i][2];
      for (let k in slopeCount) {
        curr = Math.max(curr, slopeCount[k] + unique[i][2]);
      }
      maxPoints = Math.max(maxPoints, curr);
    }
    return maxPoints;
  }

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

  غير محلولة · 11 من أصل 12 اختباراتتمت الإجابة في 45 ثوانٍ · $0.02

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

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])المتوقع 3	5 مللي ثانية
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])المتوقع 4	2 مللي ثانية

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

  الكود

  function max_collinear(points) {
    const n = points.length;
    if (n === 0) return 0;
    function gcd(a, b) {
      a = Math.abs(a);
      b = Math.abs(b);
      while (b !== 0) {
        let t = b;
        b = a % b;
        a = t;
      }
      return a;
    }
    let maxPoints = 1;
    for (let i = 0; i < n; i++) {
      let slopeCount = {};
      let dup = 1;
      for (let j = i + 1; j < n; j++) {
        let dx = points[j][0] - points[i][0];
        let dy = points[j][1] - points[i][1];
        if (dx === 0 && dy === 0) {
          dup++;
          continue;
        }
        let g = gcd(dx, dy);
        if (g === 0) continue;
        dx = Math.trunc(dx / g);
        dy = Math.trunc(dy / g);
        if (dx < 0 || (dx === 0 && dy < 0)) {
          dx = -dx;
          dy = -dy;
        }
        let key = dx + "," + dy;
        slopeCount[key] = (slopeCount[key] || 0) + 1;
      }
      let localMax = dup;
      for (let key in slopeCount) {
        localMax = Math.max(localMax, slopeCount[key] + dup);
      }
      maxPoints = Math.max(maxPoints, localMax);
      if (maxPoints === n) return n;
    }
    return maxPoints;
  }

• المركز 3DeepSeek V4.1 Flashغير محلولة · 11 من أصل 12 اختباراتتمت الإجابة في 5.6 ثوانٍ · زمن التشغيل 1.2 ثوانٍ · $0.0003

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])المتوقع 3	5 مللي ثانية
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])المتوقع 4	2 مللي ثانية

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

  function max_collinear(points) {
    const n = points.length;
    if (n <= 2) return n;
  
    // Sort points to group duplicates together.
    const pts = points.slice().sort((a, b) => (a[0] - b[0]) || (a[1] - b[1]));
  
    // Compress duplicates: unique points with multiplicities.
    const xs = [], ys = [], cnt = [];
    for (let i = 0; i < n; i++) {
      const x = pts[i][0], y = pts[i][1];
      const m = cnt.length - 1;
      if (m >= 0 && xs[m] === x && ys[m] === y) {
        cnt[m]++;
      } else {
        xs.push(x); ys.push(y); cnt.push(1);
      }
    }
  
    const m = xs.length;
    let best = 0;
    for (let i = 0; i < m; i++) if (cnt[i] > best) best = cnt[i];
  
    if (m === 1) return n;
  
    // If one point has multiplicity high enough, a line through it and any other point
    // can reach best + maxOther. We just do the standard enumeration; n small enough.
    const map = new Map();
  
    for (let i = 0; i < m; i++) {
      const xi = xs[i], yi = ys[i];
  
      // Upper bound check: cnt[i] + (sum of all multiplicity from j>i) <= remaining possible.
      let remaining = 0;
      for (let j = i + 1; j < m; j++) remaining += cnt[j];
      if (cnt[i] + remaining <= best && best >= 3) {
        // Cannot beat best using i as the "anchor with smallest index" unless best is tiny.
        if (cnt[i] + remaining <= best) continue;
      }
  
      map.clear();
      let localBest = 0;
  
      for (let j = i + 1; j < m; j++) {
        let dx = xs[j] - xi;
        let dy = ys[j] - yi;
  
        // Normalize direction. Since j>i after sorting, dx >= 0, and if dx==0 then dy>0.
        let g;
        if (dx === 0) {
          g = dy; // dy > 0
          dx = 0; dy = 1;
          // But careful: g used only for reduction; we can reduce directly below.
          // Redo cleanly:
        }
        // Use Euclidean gcd for robust reduction.
        let a = dx, b = dy;
        if (b < 0) { a = -a; b = -b; }
        let u = a < 0 ? -a : a, v = b;
        while (v) { const t = u % v; u = v; v = t; }
        g = u || 1;
        dx = a / g; dy = b / g;
  
        const key = dx * 4000000000 + dy; // safe? dx,dy can be large
        // Use string key to be safe.
        const k = dx + ',' + dy;
        const c = (map.get(k) || 0) + cnt[j];
        map.set(k, c);
        if (c > localBest) localBest = c;
      }
      const total = cnt[i] + localBest;
      if (total > best) best = total;
    }
  
    return best;
  }

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

  غير محلولة · 11 من أصل 12 اختباراتتمت الإجابة في 4.3 ثوانٍ · $0.0003

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

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])المتوقع 3	18 مللي ثانية
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])المتوقع 4	<1 مللي ثانية

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

  الكود

  function max_collinear(points) {
    const n = points.length;
    if (n <= 2) return n;
  
    const pts = points.slice().sort((a, b) => (a[0] - b[0]) || (a[1] - b[1]));
  
    const xs = [], ys = [], cnt = [];
    for (let i = 0; i < n; i++) {
      const x = pts[i][0], y = pts[i][1];
      const m = cnt.length - 1;
      if (m >= 0 && xs[m] === x && ys[m] === y) {
        cnt[m]++;
      } else {
        xs.push(x); ys.push(y); cnt.push(1);
      }
    }
  
    const m = xs.length;
    let best = 0;
    for (let i = 0; i < m; i++) if (cnt[i] > best) best = cnt[i];
  
    if (m === 1) return n;
  
    // Suffix sum of multiplicities for pruning.
    const suffix = new Array(m + 1);
    suffix[m] = 0;
    for (let i = m - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + cnt[i];
  
    // Find max multiplicity among points j > i quickly via running max from right.
    // But since we iterate and prune, we just track cheaply.
  
    const map = new Map();
  
    for (let i = 0; i < m; i++) {
      // Upper bound: line through i can include at most cnt[i] + suffix[i+1].
      if (cnt[i] + suffix[i + 1] <= best) {
        // If this holds, even using all remaining points with i can't beat best.
        // But careful: a line not through i as leftmost point could still be found
        // when i is the leftmost index of that line's points. Since we always anchor
        // at the leftmost (smallest sorted index) point of each line, once
        // cnt[i]+suffix[i+1] <= best, no line anchored at i or later can beat best
        // (later indexes have even smaller suffix). So we can break.
        break;
      }
  
      const xi = xs[i], yi = ys[i];
      map.clear();
      let localBest = 0;
  
      for (let j = i + 1; j < m; j++) {
        const a = xs[j] - xi;
        const b = ys[j] - yi;
        // Normalize: since sorted, a >= 0; if a == 0 then b > 0.
        let u = a < 0 ? -a : a, v = b < 0 ? -b : b;
        while (v) { const t = u % v; u = v; v = t; }
        const g = u || 1;
        const dx = a / g, dy = b / g;
        const k = dx + ',' + dy;
        const c = (map.get(k) || 0) + cnt[j];
        map.set(k, c);
        if (c > localBest) localBest = c;
      }
      const total = cnt[i] + localBest;
      if (total > best) best = total;
      if (best === n) return n;
    }
  
    return best;
  }

تكلفة الرموز: $0.05 · كيف تُدار الجولات وتُحتسب النقاط ←