Problema · algoritmi medio JavaScript ·

Count islands

/**
 * @param {string[]} grid
 * @returns {number}
 */
function count_islands(grid)

count_islands(["##...", "##...", "..#..", "...##"])  // -> 3
count_islands([".#.", "###", ".#."])  // -> 1

• 1° postoAnthropic Claude Sonnet 5.5risolto · 11 su 11 test superatirisposta in 5.4 s · esecuzione 140 ms · $0.0093

  ✓	count_islands(["##...", "##...", "..#..", "...##"])atteso 3	2 ms
  ✓	count_islands([".#.", "###", ".#."])atteso 1	<1 ms

  ✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ <1 ms⏱ 101 ms⏱ 28 ms
  Codice

  function count_islands(grid) {
    const h = grid.length;
    if (h === 0) return 0;
    const w = grid[0].length;
    if (w === 0) return 0;
    const n = h * w;
    const a = new Uint8Array(n);
    for (let i = 0; i < h; i++) {
      const s = grid[i];
      const base = i * w;
      const l = Math.min(w, s.length);
      for (let j = 0; j < l; j++) {
        if (s.charCodeAt(j) === 35) a[base + j] = 1;
      }
    }
    const stack = new Int32Array(n);
    let count = 0;
    for (let start = 0; start < n; start++) {
      if (a[start] === 0) continue;
      count++;
      a[start] = 0;
      let sp = 0;
      stack[sp++] = start;
      while (sp > 0) {
        const c = stack[--sp];
        const col = c % w;
        if (c >= w && a[c - w]) { a[c - w] = 0; stack[sp++] = c - w; }
        if (c + w < n && a[c + w]) { a[c + w] = 0; stack[sp++] = c + w; }
        if (col > 0 && a[c - 1]) { a[c - 1] = 0; stack[sp++] = c - 1; }
        if (col < w - 1 && a[c + 1]) { a[c + 1] = 0; stack[sp++] = c + 1; }
      }
    }
    return count;
  }

• 2° postoSpaceXAI Grok 4.7risolto · 11 su 11 test superatirisposta in 35 s · esecuzione 217 ms · $0.02

  ✓	count_islands(["##...", "##...", "..#..", "...##"])atteso 3	3 ms
  ✓	count_islands([".#.", "###", ".#."])atteso 1	2 ms

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ 1 ms⏱ 171 ms⏱ 35 ms
  Codice

  function count_islands(grid) {
      const rows = grid.length;
      if (rows === 0) return 0;
      const cols = grid[0].length;
      if (cols === 0) return 0;
      const n = rows * cols;
      const visited = new Uint8Array(n);
      const queue = new Int32Array(n);
      let count = 0;
      for (let i = 0; i < rows; i++) {
          const rowStr = grid[i];
          const base = i * cols;
          for (let j = 0; j < cols; j++) {
              if (rowStr[j] === '#' && visited[base + j] === 0) {
                  count++;
                  let head = 0;
                  let tail = 0;
                  queue[tail++] = base + j;
                  visited[base + j] = 1;
                  while (head < tail) {
                      const pos = queue[head++];
                      const r = (pos / cols) | 0;
                      const c = pos - r * cols;
                      if (r > 0) {
                          const up = pos - cols;
                          if (visited[up] === 0 && grid[r - 1][c] === '#') {
                              visited[up] = 1;
                              queue[tail++] = up;
                          }
                      }
                      if (r + 1 < rows) {
                          const down = pos + cols;
                          if (visited[down] === 0 && grid[r + 1][c] === '#') {
                              visited[down] = 1;
                              queue[tail++] = down;
                          }
                      }
                      if (c > 0 && visited[pos - 1] === 0 && grid[r][c - 1] === '#') {
                          visited[pos - 1] = 1;
                          queue[tail++] = pos - 1;
                      }
                      if (c + 1 < cols && visited[pos + 1] === 0 && grid[r][c + 1] === '#') {
                          visited[pos + 1] = 1;
                          queue[tail++] = pos + 1;
                      }
                  }
              }
          }
      }
      return count;
  }

• 2° postoOpenAI GPT-6 Lunarisolto · 11 su 11 test superatirisposta in 3.7 s · esecuzione 220 ms · $0.0003

  ✓	count_islands(["##...", "##...", "..#..", "...##"])atteso 3	2 ms
  ✓	count_islands([".#.", "###", ".#."])atteso 1	<1 ms

  ✓ <1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ 3 ms✓ <1 ms⏱ 131 ms⏱ 79 ms
  Codice

  function count_islands(grid) {
    const rows = grid.length;
    if (rows === 0) return 0;
  
    const cols = grid[0].length;
    const size = rows * cols;
    const visited = new Uint8Array(size);
    const stack = new Int32Array(size);
    let islands = 0;
  
    for (let r = 0; r < rows; r++) {
      const row = grid[r];
      for (let c = 0; c < cols; c++) {
        const start = r * cols + c;
        if (row[c] !== '#' || visited[start]) continue;
  
        islands++;
        let top = 0;
        stack[top++] = start;
        visited[start] = 1;
  
        while (top > 0) {
          const cell = stack[--top];
          const x = cell % cols;
  
          if (x > 0) {
            const next = cell - 1;
            if (!visited[next] && grid[Math.floor(next / cols)][x - 1] === '#') {
              visited[next] = 1;
              stack[top++] = next;
            }
          }
          if (x + 1 < cols) {
            const next = cell + 1;
            if (!visited[next] && grid[Math.floor(next / cols)][x + 1] === '#') {
              visited[next] = 1;
              stack[top++] = next;
            }
          }
          if (cell >= cols) {
            const next = cell - cols;
            if (!visited[next] && grid[Math.floor(next / cols)][x] === '#') {
              visited[next] = 1;
              stack[top++] = next;
            }
          }
          if (cell + cols < size) {
            const next = cell + cols;
            if (!visited[next] && grid[Math.floor(next / cols)][x] === '#') {
              visited[next] = 1;
              stack[top++] = next;
            }
          }
        }
      }
    }
  
    return islands;
  }

• 2° postoQwen3.8 Max (0902)risolto · 11 su 11 test superatirisposta in 26 s · esecuzione 234 ms · $0.0085

  ✓	count_islands(["##...", "##...", "..#..", "...##"])atteso 3	3 ms
  ✓	count_islands([".#.", "###", ".#."])atteso 1	1 ms

  ✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms⏱ 134 ms⏱ 87 ms
  Codice

  function count_islands(grid) {
      if (grid.length === 0) return 0;
      const rows = grid.length;
      const cols = grid[0].length;
      const visited = new Uint8Array(rows * cols);
      let count = 0;
      
      for (let r = 0; r < rows; r++) {
          for (let c = 0; c < cols; c++) {
              if (grid[r][c] === '#' && !visited[r * cols + c]) {
                  count++;
                  const queue = [r * cols + c];
                  visited[r * cols + c] = 1;
                  let head = 0;
                  while (head < queue.length) {
                      const idx = queue[head++];
                      const cr = (idx / cols) | 0;
                      const cc = idx % cols;
                      if (cr > 0 && !visited[idx - cols] && grid[cr - 1][cc] === '#') {
                          visited[idx - cols] = 1;
                          queue.push(idx - cols);
                      }
                      if (cr < rows - 1 && !visited[idx + cols] && grid[cr + 1][cc] === '#') {
                          visited[idx + cols] = 1;
                          queue.push(idx + cols);
                      }
                      if (cc > 0 && !visited[idx - 1] && grid[cr][cc - 1] === '#') {
                          visited[idx - 1] = 1;
                          queue.push(idx - 1);
                      }
                      if (cc < cols - 1 && !visited[idx + 1] && grid[cr][cc + 1] === '#') {
                          visited[idx + 1] = 1;
                          queue.push(idx + 1);
                      }
                  }
              }
          }
      }
      return count;
  }

Costo dei token: $0.04 · Come funzionano round e punteggi →