Finding quickly how many neighbors you have...

...inside matrices (gotcha!).

Created on 11/22/2024, finished on 11/27/2024

Today I had a course of informatic programming (it's just C course actually). There was a strange exercise we had to do: from a matrix, create a new one telling for each cell how many neighbors which share the same value they have.

Easy at a quick glance, but harder when thinking about edge cases.

First, I took a paper, because it's always easier for me to visualize by writing and drawing.

There are four edge cases concerning the analyzed cell :
  1. It is on the first line.
  2. It is on the first column.
  3. It is on the last line.
  4. It is on the last column.

Four more edge cases happen when you think about corners.

So I used the rough way : checking each edge case, and adding one thanks to boolean results.

I define this algorithm inside a function declared as this : size_t countNeighbors(int **matrix, size_t m, size_t n, size_t i, size_t j).

m corresponds to rows and n to columns. I could have created a struct, but I already had done this here.

countNeighbors.c 
size_t countNeighbors(int **matrix, size_t m, size_t n, size_t i, size_t j)
{
  const int a = matrix[i][j];

  const size_t up = (i != 0 && matrix[i-1][j] == a);
  const size_t down = (i != m-1 && matrix[i+1][j] == a);
  const size_t left = (j != 0 && matrix[i][j-1] == a);
  const size_t right = (j != n-1 && matrix[i][j+1] == a);

  const size_t up_left = (i != 0 && j != 0 && matrix[i-1][j-1] == a);
  const size_t up_right = (i != 0 && j != n-1 && matrix[i-1][j+1] == a);
  const size_t down_left = (i != m-1 && j != 0 && matrix[i+1][j-1] == a);
  const size_t down_right = (i != m-1 && j != n-1 && matrix[i+1][j+1] == a);

  return up + down + left + right + up_left + up_right + down_left + down_right;
}

It's definitely ugly, but it works, and is somewhat readable.

Now let's try to solve this exercise using C++.

To do so I created a MatrixInt class, since I didn't want to bother with templates, but I will be using std::optional to safely get elements from the matrix.

countNeighbors.cpp 
class MatrixInt {
  // Defining constructors and operators...

  std::optional<int> at(int i, int j) const
  {
    if (0 <= i && i < m_rows && 0 <= j && j < m_columns) {
      return m_elems[i][j];
    }
    return std::nullopt;
  }

  size_t countNeighborsAt(int i, int j) const
  {
    size_t result = 0;
    const int a = m_elems[i][j];

    // Actually, I didn't know this syntax until coding this program.
    for (int k : {-1, 0, 1}) {
      for (int l : {-1, 0, 1}) {
        result += (this->at(i+k, j+l) == a);
      }
    }
    return result - 1;
  }

  MatrixInt neighbors() const
  {
    MatrixInt result(m_rows, m_columns);
    for (int i = 0; i < m_rows; ++i) {
      for (int j = 0; j < m_columns; ++j) {
        result.m_elems[i][j] = this->countNeighborsAt(i, j);
      }
    }
    return result;
  }
};

It might be fun if we were using a more modern version of C++ (like C++20) and making a function more pythonic.

pythonic.cpp 
MatrixInt neighbors() const
{
  auto range = std::views::iota;
  #define in :
  MatrixInt result(m_rows, m_columns);
  for (int i in range(0ull, m_rows)) {
    for (int j in range(0ull, m_columns)) {
      result.m_elems[i][j] = this->countNeighborsAt(i, j);
    }
  }
  return result;
}

Yeah that's definitely cursed, but I think it was worth it.

That's all for today!