Battleship Field Validator

battleship-field-validator.js

function validateBattleshipField(field) {
  console.log('field:', field);
  let valid = true;
  // count ones
  const onesCount = 1 * 4 + 2 * 3 + 3 * 2 + 4 * 1;
  let onesCounter = 0;
  for (let i = 0, iMax = field.length; i < iMax; i++) {
    for (let j = 0, jMax = field[i].length; j < jMax; j++) {
      if (field[i][j] === 1) {
        onesCounter++;
      }
    }
  }
  console.log('onesCount:', onesCount, '| onesCounter:', onesCounter);
  if (onesCount !== onesCounter) { return false; }
  // detect ships
  let ships = [];
  let fieldCopy = field.slice(0);
  /*
  *  detect ships in rows
  */
  for (let i = 0, iMax = field.length; i < iMax; i++) {
    let ship = [];
    for (let j = 0, jMax = field[i].length; j < jMax; j++) {
      if (field[i][j]) {
        /*
        *  break if (ships' angles tounch)
        *  this is needed only once
        */
        let touch = false;
        if (field[i - 1]) {
          if (field[i - 1][j - 1] || field[i - 1][j + 1]) { touch = true; }
        }
        if (field[i + 1]) {
          if (field[i + 1][j - 1] || field[i + 1][j + 1]) { touch = true; }
        }
        if (touch) { return false; }
        // continue detecting
        if (i === 0) { // first line
          if (!field[i + 1][j]) { // 0 on lower line
            ship.push([i, j]);
            fieldCopy[i][j] = 0; // mark this square as visited
          }
        }
        if (i > 0 && i < field.length - 1) { // middle
          if (!field[i - 1][j] && !field[i + 1][j]) { // 0 on lower and upper lines
            ship.push([i, j]);
            fieldCopy[i][j] = 0; // mark this square as visited
          }
        }
        if (i === field.length - 1) { // last line
          if (!field[i - 1][j]) { // 0 on upper line
            ship.push([i, j]);
            fieldCopy[i][j] = 0; // mark this square as visited
          }
        }
      } else {
        if (ship.length > 0) {
          ships.push(ship);
        }
        ship = [];
      }
    }
  }
  console.log('ships:', ships);
  console.log('fieldCopy:', fieldCopy);
  /*
  *  detect ships in columns
  */
  for (let i = 0, iMax = field.length; i < iMax; i++) {
    let ship = [];
    for (let j = 0, jMax = field[i].length; j < jMax; j++) {
      if (fieldCopy[j][i]) {
        if (j === 0) { // first column
          if (!field[j][i + 1]) { // 0 on right column
            ship.push([j, i]);
            fieldCopy[j][i] = 0; // mark this square as visited
          }
        }
        if (j > 0 && j < field.length - 1) { // middle
          if (!fieldCopy[j][i - 1] && !fieldCopy[j][i + 1]) { // 0 to the left and to the right
            ship.push([j, i]);
            fieldCopy[j][i] = 0; // mark this square as visited
          }
        }
        if (j === field.length - 1) { // last column
          if (!fieldCopy[j][i - 1]) { // 0 on upper line
            ship.push([j, i]);
            fieldCopy[j][i] = 0; // mark this square as visited
          }
        }
      } else {
        if (ship.length > 0) {
          ships.push(ship);
        }
        ship = [];
      }
    }
  }
  console.log('ships:', ships);
  console.log('fieldCopy:', fieldCopy);
  let shipsCount = {
    '1': 4,
    '2': 3,
    '3': 2,
    '4': 1
  };
  console.log('shipsCount:', shipsCount);
  ships.forEach(item => {
    // reduce ships' counters
    shipsCount[item.length.toString()]--;
  });
  for (let count in shipsCount) {
    // all ships' counters should be 0
    valid = (shipsCount[count] === 0) ? valid : false
  }
  console.log('shipsCount:', shipsCount);
  /*
  *  optionally fieldCopy can be chacked to consist of only 0, but that seems to be an excessive check for now
  */
  return valid;
}

// TEST
const field1 = [
  [1, 0, 0, 0, 0, 1, 1, 0, 0, 0],
  [1, 0, 1, 0, 0, 0, 0, 0, 1, 0],
  [1, 0, 1, 0, 1, 1, 1, 0, 1, 0],
  [1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
  [0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
  [0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
];
const field2 = [
  [1, 0, 0, 0, 0, 1, 1, 0, 0, 0],
  [1, 1, 0, 0, 0, 0, 0, 0, 1, 0],
  [1, 0, 1, 0, 1, 1, 1, 0, 1, 0],
  [1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
  [0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
  [0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
];


validateBattleshipField(field1); // true
validateBattleshipField(field2); // false

BattleshipFieldValidator.markdown

Battleship Field Validator

Function validateBattleshipField validates battleships placement on the Battleship (game) field.

There must be:

• a single battleship - size 4
• 2 cruisers - size 3
• 3 destroyers - size 2
• 4 submarines - size 1

Any additional ships are not allowed, as well as missing ships.

Each ship must ocupy cells in a straight line, except for submarines, which occupy a single cell.

Ships can't overlap or be in contact with other ships, i.e. ships should not occupy neighbour cells of another ships.

This is not valid (notice cells with coordinates 1:1 and 1:2) [ [1, 0, 0, 0, 0, 1, 1, 0, 0, 0], [1, 1, 0, 0, 0, 0, 0, 0, 1, 0], [1, 0, 1, 0, 1, 1, 1, 0, 1, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 1, 1, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] ]

This is valid (notice cells with coordinates 1:1 and 1:2) [ [1, 0, 0, 0, 0, 1, 1, 0, 0, 0], [1, 0, 1, 0, 0, 0, 0, 0, 1, 0], [1, 0, 1, 0, 1, 1, 1, 0, 1, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 1, 1, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] ]

A script by V.

License.