Matrix and Grid Simulation

// Template 1: rotate by combining two simple moves. Transpose swaps (i, j) with (j, i); reversing every row
// then mirrors left to right. Transpose + reverse rows = 90 degrees clockwise, in place, O(1) extra space.
export function transpose(m) {
  // A new grid, so it also works for rectangles: rows x cols becomes cols x rows.
  const out = Array.from({ length: m[0].length }, () => new Array(m.length)); // never fill() with one shared row
  for (let i = 0; i < m.length; i++) for (let j = 0; j < m[0].length; j++) out[j][i] = m[i][j];
  return out;
}

export function rotateClockwise(m) {
  const n = m.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) [m[i][j], m[j][i]] = [m[j][i], m[i][j]]; // j > i: swap each pair once
  }
  for (const row of m) row.reverse();
}

export function rotateCounterClockwise(m) {
  for (const row of m) row.reverse(); // reverse first, then transpose, for the other direction
  const n = m.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) [m[i][j], m[j][i]] = [m[j][i], m[i][j]];
  }
}

// Template 2: layers and boundaries. Four walls frame the unread rectangle; after each side is read,
// that wall moves inward. The two guards stop a leftover single row or column being read twice.
export function spiralOrder(m) {
  const out = [];
  let top = 0;
  let bottom = m.length - 1;
  let left = 0;
  let right = m[0].length - 1;
  while (top <= bottom && left <= right) {
    for (let c = left; c <= right; c++) out.push(m[top][c]);
    top++;
    for (let r = top; r <= bottom; r++) out.push(m[r][right]);
    right--;
    if (top <= bottom) {
      for (let c = right; c >= left; c--) out.push(m[bottom][c]);
      bottom--;
    }
    if (left <= right) {
      for (let r = bottom; r >= top; r--) out.push(m[r][left]);
      left++;
    }
  }
  return out;
}

// The same spiral written the other way round: a direction array and "turn when blocked", to fill 1..n*n.
export function spiralFill(n) {
  const grid = Array.from({ length: n }, () => new Array(n).fill(0));
  const dr = [0, 1, 0, -1]; // right, down, left, up
  const dc = [1, 0, -1, 0];
  let r = 0;
  let c = 0;
  let d = 0;
  for (let k = 1; k <= n * n; k++) {
    grid[r][c] = k;
    const nr = r + dr[d];
    const nc = c + dc[d];
    if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] !== 0) d = (d + 1) % 4; // blocked: turn right
    r += dr[d];
    c += dc[d];
  }
  return grid;
}

// Template 3: marker row and column. Record "this row/column must be cleared" inside the grid itself (its first
// row and first column), instead of in extra arrays. Decide first, change later: never zero while scanning.
export function setZeroes(m) {
  const rows = m.length;
  const cols = m[0].length;
  let firstRowZero = false; // the markers live in row 0 and column 0, so remember if they held a zero
  let firstColZero = false;
  for (let j = 0; j < cols; j++) if (m[0][j] === 0) firstRowZero = true;
  for (let i = 0; i < rows; i++) if (m[i][0] === 0) firstColZero = true;

  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      if (m[i][j] === 0) {
        m[i][0] = 0; // mark row i
        m[0][j] = 0; // mark column j
      }
    }
  }
  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      if (m[i][0] === 0 || m[0][j] === 0) m[i][j] = 0;
    }
  }
  if (firstRowZero) for (let j = 0; j < cols; j++) m[0][j] = 0; // only now is it safe to clear the markers
  if (firstColZero) for (let i = 0; i < rows; i++) m[i][0] = 0;
}

// Template 4: simulation with state encoding. All cells change at once, so decisions must use the OLD board.
// Encode old and new state in one number: 0 dead, 1 alive, 2 alive -> dead, 3 dead -> alive.
// Eight directions as (row, column) steps: the direction-array idiom for every grid walk.
const NEIGHBOURS = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];

function aliveNeighbours(board, r, c) {
  let live = 0;
  for (const [dr, dc] of NEIGHBOURS) {
    const nr = r + dr;
    const nc = c + dc;
    if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length) continue;
    if (board[nr][nc] === 1 || board[nr][nc] === 2) live++; // 2 was alive in the old generation
  }
  return live;
}

export function gameOfLife(board) {
  for (let r = 0; r < board.length; r++) {
    for (let c = 0; c < board[0].length; c++) {
      const live = aliveNeighbours(board, r, c);
      if (board[r][c] === 1 && (live < 2 || live > 3)) board[r][c] = 2; // dies
      else if (board[r][c] === 0 && live === 3) board[r][c] = 3; // is born
    }
  }
  for (const row of board) {
    for (let c = 0; c < row.length; c++) row[c] = row[c] === 1 || row[c] === 3 ? 1 : 0; // keep the new state
  }
}

// The simple alternative: write into a copy, read from the original. O(rows * columns) extra space.
export function nextGeneration(board) {
  const next = board.map((row) => row.slice());
  for (let r = 0; r < board.length; r++) {
    for (let c = 0; c < board[0].length; c++) {
      const live = aliveNeighbours(board, r, c);
      next[r][c] = board[r][c] === 1 ? (live === 2 || live === 3 ? 1 : 0) : live === 3 ? 1 : 0;
    }
  }
  return next;
}

// Template 5a: binary search on a matrix. If each row starts above the previous row's end, the grid read row by
// row is one sorted list: search positions 0..rows*cols-1 and convert a position to (row, column).
export function searchFlat(m, target) {
  const cols = m[0].length;
  let lo = 0;
  let hi = m.length * cols - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    const value = m[Math.floor(mid / cols)][mid % cols];
    if (value === target) return true;
    if (value < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return false;
}

// If rows and columns are each sorted but rows do not chain, walk a staircase from the top-right corner:
// too big means nothing below-left of here can match in this column, so go left; too small, go down.
export function searchStaircase(m, target) {
  let r = 0;
  let c = m[0].length - 1;
  while (r < m.length && c >= 0) {
    if (m[r][c] === target) return true;
    if (m[r][c] > target) c--;
    else r++;
  }
  return false;
}