Codesignal Solution: Matrix Perimeter

Original Problem

You are given a matrix that contains booleans. If an element is true, it means that it is colored black, otherwise it is colored white.

Your task is to find perimeter of the objects colored black.

Example

For

matrix = [[false, false, false, true, false],
 [false, true, true, true, false],
 [false, false, false, true, false],
 [false, true, true, true, false],
 [ true, true, false, false, false]]

the output should be

MatrixPerimeter(matrix) = 22.

As you can see, perimeter of the area colored black is 22.

Input/Output

• [time limit] 4000ms (js)

• [input] array.array.boolean matrix

  A rectangular matrix.

  Constraints:
  
  1 ≤ matrix.length ≤ 100,
  
  1 ≤ matrix[i].length ≤ 100.

• [output] integer

  Perimeter of the black figures.

Solution

I think the most trivial solution scans over the full matrix, and for each cell, the neighbors or the borders are considered and according to them, the final perimeter is increased by one if the neighbor isn't occupied as well.

function MatrixPerimeter(m) {
  var s = 0;
  for (var i = 0; i < m.length; i++) {
    for (var j = 0; j < m[i].length; j++) {
      if (m[i][j]) {
        if (i <= 0 || !m[i-1][j]) s++;
        if (j <= 0 || !m[i][j-1]) s++;
        if (j >= m[i].length-1 || !m[i][j+1]) s++;
        if (i >= m.length-1 || !m[i+1][j]) s++;
      }
    }
  }
  return s;
}

That's a totally valid solution. However, Codefights assesses it's participants on the brevity and therefore also on the elegance and cleverness of the implementations. The first improvements we can make are removing the "var" keywords (even if it's bad style), calculate the length of the arrays only once and the most important part: invert the if statements and subtract them from 4 sides, which we add generally:

MatrixPerimeter = m => {
  r=m.length
  c=m[0].length
  for (s = i = 0; i < r; i++)
    for (j = 0; j < c; j++)
      if (m[i][j]) {
        s-= i > 0 && m[i-1][j]
        s-= j > 0 && m[i][j-1]
        s-= j < c-1 && m[i][j+1]
        s-= i < r-1 && m[i+1][j]
        s+= 4
      }
  return s
}

Okay, what else can we do? We can remove the for loops and replace them by something functional:

s = 0
MatrixPerimeter = m => (
  m.map((r, i) => {
    r.map((c, j) => {
      if (c) {
        s-= i > 0 && m[i-1][j]
        s-= j > 0 && r[j-1]
        s-= j < r.length-1 && r[j+1]
        s-= i < m.length-1 && m[i+1][j]
        s+= 4
     }
   })
  }), s)

The inner of the loop is still the most space sapping part of the function. We could say, that the previous line is always the return value of the inner map. Furthermore, we can remove the size check of the inner loop:

p = s = 0
MatrixPerimeter = m => (
  m.map((r, i) => {
    p = r.map((c, j) => {
      if (c) {
        s-= !!p[j]
        s-= !!r[j-1]
        s-= !!r[j+1]
        s-= i < m.length-1 && m[i+1][j]
        s+= 4
        return r
      }
    })
  }), s)

When we invert the bools again and sum it together, we get

p = s = 0
MatrixPerimeter = m => (
  m.map((r, i) => {
    p = r.map((c, j) =>
      c ? (
        s+= !p[j]
         + !r[j-1]
         + !r[j+1]
         + (i >= m.length-1 || !m[i + 1][j]), r
      ) : null
    )
  }), s)

Now something cool is possible. Since we need to sum the borders anyway, we can skip the checks and double the result at the end:

p = s = 0
MatrixPerimeter = m =>
  (m.map(r =>
    p = r.map((c, j) =>
      c ? s += !p[j] + !r[j + 1] : 0)
), s * 2)