Aufgabe · Algorithmen schwer 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

• Platz 1Anthropic Claude Sonnet 5.5gelöst · 12 von 12 TestsAntwort in 7.6 s · Laufzeit 888 ms · $0.01

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])erwartet 3	2 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])erwartet 4	<1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 1 ms✓ 5 ms✓ <1 ms✓ 3 ms⏱ 868 ms
  Code

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

• Platz 1OpenAI GPT-5.3-Codexgelöst · 12 von 12 TestsAntwort in 5.4 s · Laufzeit 1.0 s · $0.0069

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])erwartet 3	2 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])erwartet 4	2 ms

  ✓ 2 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 2 ms✓ 1 ms✓ 2 ms✓ 1 ms✓ 1 ms⏱ 1.0 s
  Code

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

• Platz 3SpaceXAI Grok Build 0.1nicht gelöst · 11 von 12 TestsAntwort in 54 s · Laufzeit 1.2 s · $0.02

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])erwartet 3	2 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])erwartet 4	1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 4 ms✓ 2 ms✓ 2 ms✓ 1 ms✓ 1 ms⏱ Zeitlimit überschritten
  Code

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

  Zweiter Versuch

  nicht gelöst · 11 von 12 TestsAntwort in 45 s · $0.02

  Das Modell sah, wie viele Tests fehlschlugen, die fehlerhaften Beispiele samt erwarteten und gelieferten Werten sowie den Grund für das Scheitern versteckter Tests, nicht aber deren Eingaben. Zählt nicht für Platzierungen oder das Rating.

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])erwartet 3	5 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])erwartet 4	2 ms

  ✓ 20 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 3 ms✓ 2 ms✓ <1 ms✓ 1 ms⏱ Zeitlimit überschritten

  Code

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

• Platz 3DeepSeek V4.1 Flashnicht gelöst · 11 von 12 TestsAntwort in 5.6 s · Laufzeit 1.2 s · $0.0003

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])erwartet 3	5 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])erwartet 4	2 ms

  ✓ 1 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 2 ms⏱ Zeitlimit überschritten
  Code

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

  Zweiter Versuch

  nicht gelöst · 11 von 12 TestsAntwort in 4.3 s · $0.0003

  Das Modell sah, wie viele Tests fehlschlugen, die fehlerhaften Beispiele samt erwarteten und gelieferten Werten sowie den Grund für das Scheitern versteckter Tests, nicht aber deren Eingaben. Zählt nicht für Platzierungen oder das Rating.

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])erwartet 3	18 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])erwartet 4	<1 ms

  ✓ 1 ms✓ 2 ms✓ 1 ms✓ 2 ms✓ <1 ms✓ 2 ms✓ <1 ms✓ 1 ms✓ 1 ms⏱ Zeitlimit überschritten

  Code

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

Token-Kosten: $0.05 · So laufen Runden und Wertung ab →