Sand Pile

Problem Statement

Given a 2D matrix of containing sand grains

Consider the following:

A cell can have at most 3 grains at a time

If a grain is added to a cell containing 3 grains, that cell would transfer all grains to its 4 neighbors

If a cell does not have 4 neighbors (cells at the edges), then the grains are lost

Click on any cell to add the sand grain.

The goal is to find the final state of the grid after adding a grain

Solution


function deepCopyGrid(pile) {
  const newPile = [];
  for (const pileRow of pile) {
    newPile.push([...pileRow]);
  }
  return newPile;
}

function isValid(i, j, r, c) {
  return i >= 0 && i < r && j >= 0 && j < c;
}

function rebalance(pile, positions) {
  if (positions.length == 0) {
    return pile;
  }

  pile = deepCopyGrid(pile);

  let newPositions = [];

  for (const pos of positions) {
    const [i, j] = pos;

    if (pile[i][j] < 4) {
      continue;
    }

    pile[i][j] -= 4;
    updateCellIfValid(pile, i - 1, j, newPositions);
    updateCellIfValid(pile, i, j + 1, newPositions);
    updateCellIfValid(pile, i + 1, j, newPositions);
    updateCellIfValid(pile, i, j - 1, newPositions);
  }

  return rebalance(pile, newPositions);
}

function updateCellIfValid(pile, i, j, newPositions) {
  if (isValid(i, j, pile.length, pile[0].length)) {
    pile[i][j]++;
    newPositions.push([i, j]);
  }
}

function addGrain(pile, i, j) {
  if (isValid(i, j, pile.length, pile[0].length)) {
    pile[i][j]++;
  }

  return rebalance(pile, [[i, j]]);
}

Umakant Vashishtha

Sand Pile

Problem Statement

Solution