C# – Find the Biggest Square in a Matrix – What can Excel and VBA add to it?

Finding the biggest square of specific units in a given matrix of these units is a standard dynamic programming problem. The examples in Google for it are above 18 million, thus I would simply show how it is done with C# and what is the exact steps. Then, I would solve it with Excel and VBA, to show the benefits of knowing Excel and VBA for tasks like this – it is not the speed, but the quick representation, which matters.

The C# problem:

In general, a matrix like this is given:

And the task is to answer with the biggest possible square of 1. The biggest possible square is rounded in black. It is either this one or the one, which is one row below, but the result is still the same – the side is 4.

The algorithm

  • Create a second matrix with the size of the first one;
  • Copy the array to a new array. Use Array.Copy to avoid copying the reference only.
  • Then start looping from the second row and the second column to the left, going to the bottom right of the matrix. E.g. from the column and row with index 1, as arrays are 0-based.
  • During the loop make 2 checks only:
    • Write whether the element in position [r, c] is a 1.
    • If it is 1, then give the minimum of the three element around it – the one on its top, the one its left and the one on its upper left diagonal. Increase that minimum with 1.
  • At the end take a look at the new matrix. The highest element in it is the highest possible side. It also shows the location of that square (these are 2 in our case):

The code is here, pretty much following the algorithm:

So, what can we do with Excel and VBA?

Why is it better for the representation of this algoritm? Well, just imagine the quick highlight of the exact location of the square. Plus some swap between the two matrices in real time. And this is in a real Excel file, which could be copied and pasted somewhere further. Somehow a bit fancier than a console input?

The upper left matrix is the input one and the down right is the one with the calculations. Only the upper left should be filled out to work.

This is the code. Hope you are convinced VBA and Excel are really an iconic duo:

Tagged with: , ,