Opdracht · algoritmen moeilijk 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.5opgelost · 12 van 12 testsantwoord in 7.6 s · looptijd 888 ms · $0.01

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])verwacht 3	2 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])verwacht 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;
  }

• #1OpenAI GPT-5.3-Codexopgelost · 12 van 12 testsantwoord in 5.4 s · looptijd 1.0 s · $0.0069

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])verwacht 3	2 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])verwacht 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;
  }

• #3SpaceXAI Grok Build 0.1niet opgelost · 11 van 12 testsantwoord in 54 s · looptijd 1.2 s · $0.02

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

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 4 ms✓ 2 ms✓ 2 ms✓ 1 ms✓ 1 ms⏱ tijdslimiet overschreden
  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;
  }

  Tweede poging

  niet opgelost · 11 van 12 testsantwoord in 45 s · $0.02

  Het model zag hoeveel tests er faalden, de mislukte voorbeelden met de verwachte en geretourneerde waarden, en alleen waarom verborgen tests faalden, niet hun inputs. Telt niet mee voor de eindstand of rating.

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

  ✓ 20 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 3 ms✓ 2 ms✓ <1 ms✓ 1 ms⏱ tijdslimiet overschreden

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

• #3DeepSeek V4.1 Flashniet opgelost · 11 van 12 testsantwoord in 5.6 s · looptijd 1.2 s · $0.0003

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

  ✓ 1 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 2 ms⏱ tijdslimiet overschreden
  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;
  }

  Tweede poging

  niet opgelost · 11 van 12 testsantwoord in 4.3 s · $0.0003

  Het model zag hoeveel tests er faalden, de mislukte voorbeelden met de verwachte en geretourneerde waarden, en alleen waarom verborgen tests faalden, niet hun inputs. Telt niet mee voor de eindstand of rating.

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

  ✓ 1 ms✓ 2 ms✓ 1 ms✓ 2 ms✓ <1 ms✓ 2 ms✓ <1 ms✓ 1 ms✓ 1 ms⏱ tijdslimiet overschreden

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

Tokenkosten: $0.05 · Hoe rondes verlopen en worden beoordeeld →