bomber-man.js

/*
Initial questions:
- How large is the grid?
- What is the format of the input I'm given?
- Is the player guaranteed to exist on the grid?
- Is there always going to be a blocking tile?

Proposal: dynamic programming

- If adjacent tile is out of bounds (e.g. we're at
the edge) or a barrier, return 0. Cache the result.
- Otherwise return the memoized result of the
adjacent tile + 1.
*/

// Explicitly check for integers to prevent false negatives for '0' value
const tileExists = (row, col, grid) => grid[row] &&
  Number.isInteger(grid[row][col]);
  
const serializePosition = position => [position.row, position.col].join('-');

/**
* @param {Object} x,y position of a particular tile
* @param {Array} Entire game grid
*/
function countDamage(position, grid, memoTable = {}) {
  let leftTile = 0;
  let rightTile = 0;
  let aboveTile = 0;
  let belowTile = 0;

  const positionKey = serializePosition(position.row, position.col);

  if (Number.isInteger(memoTable[positionKey])) {
    return memoTable[positionKey];
  }

  if (tileExists(position.row, position.col - 1, grid)) {
    leftTile = countDamage({
      row: position.row,
      col: position.col - 1
    }, grid, memoTable);
  }
  if (tileExists(position.row, position.col + 1, grid)) {
    rightTile = countDamage({
      row: position.row,
      col: position.col + 1
    }, grid, memoTable);
  }
  if (tileExists(position.row - 1, position.col, grid)) {
    aboveTile = countDamage({
      row: position.row - 1,
      col: position.col
    }, grid, memoTable);
  }
  if (tileExists(position.row + 1, position.col, grid)) {
    belowTile = countDamage({
      row: position.row + 1,
      col: position.col
    }, grid, memoTable);
  }
  
  const totalDamage = 1 + leftTile + rightTile + aboveTile + belowTile;

  memoTable[positionKey] = totalDamage;

  if (totalDamage > memoTable.maxDamage) {
    memoTable.maxDamage = totalDamage;
    memoTable.bestTile = position;
  }
  
  return totalDamage;
}

/**
* @param {Object} Player's row and col position
* @param {Array} 2D array representing board
* @throws TypeError
*
* @return {Object} Max damage row and col
*/
function findMaxDamageTile(playerPos, grid) {
  if (typeof playerPos !== 'object' || playerPos === null) {
    throw new TypeError('Invalid player input');
  }
  if (!Array.isArray(grid)) {
    throw new TypeError('Invalid grid');
  }
  if (!grid[playerPos.col] || !grid[playerPos.row]) {
    throw new TypeError('Player is out of bounds.');
  }
  
  const memoTable = {};
  memoTable.maxDamage = 0;
  memoTable.bestTile = playerPos;
  
  countDamage(playerPos, grid, memoTable);

  return memoTable.bestTile;
}

const grid = [
  // Row 1
  [0, 0, 0, 0],
  // Row 2
  [0, 0, 1, 0]
  // etc.
];

findMaxDamageTile(
  {row: 1, col: 1},
  grid
);