Given a 2-dimensional array of values, count the blocks of identical values and return the counts as a map.
A block is defined as a contiguous selection of cells with identical values along the horizontal and vertical (but not diagonal) axes.
So, given an input array like this...
[['R', 'R', 'B', 'G'], ['R', 'B', 'B', 'G'], ['B', 'G', 'G', 'G'], ['B', 'G', 'G', 'R']]
Generate a map of block counts like this...
Map { 'R' => 2, 'B' => 2, 'G' => 1 }
Seems easy enough. We'll definitely need to iterate over all the items in the array at least once, and likely several time as we focus on different block types. What we'll need is a breadth first approach, and to make it work we'll need to be able to track which cells we've visited and counted as part of a block.
Map is our friend here and we'll need two: one to track the counts of each unique block type, and one to track the visited cells. We could perhaps only do this with one block if we were allowed to either modify the input, or pre-process the input to make the strings into objects with a 'visited' property. Either of those would save us some complexity, but maybe not enough to make a huge difference.
The basics of the breadth first search are pretty simple. From a given index, (X, Y), we can determine if the value at the index is unique, if the index has been visited, and if the cell at the index has neighbors with the same value (are part of a block). We can then recursively explore in the cardinal directions (up, down, left, and right) looking only for the cells with the same value as our original index, marking 'visited' as we go.
As we curse over each index in the array building our map of visited indices, the iterations will get faster as we'll (hopefully) need to dive into the recursive search function less and less.
Let's take a look at a solution...
Now, since we need to touch every index in the input array at least once, let's start with an assumption that N is the total length of a flattened input array. If we also assume that every index is unique, our direction checks will be made for each index four times regardless of position, plus the check on the index itself. That puts our worst-case complexity at O-5N, or just ON which is pretty good!
For now, I'm happy with this solution but if you're reading this and you know a better one, let me know!