On Sunday, 16 July 2017 at 10:37:39 UTC, kerdemdemir wrote:
My goal is to find connected components in a 2D array for example finding connected '*'
chars below.

      x x x x x x
      x x x x x x
      x x * * x x
      x x * * x x
      x x x * * x
      * x x x x x

...

Is there any better way to achieve this with cool std functions like enumerate or iota without needing to write eight if checks?

I don't know of a library facility to do this.

Still, there is a language-agnostic way to make it more concise. Instead of repeating eight similar blocks, define an array of delta-rows and delta-columns to neighboring cells, and use that array in a loop. A complete example follows:

-----
import std.algorithm, std.array, std.range, std.stdio;

immutable int dirs = 8;
immutable int [dirs] dRow = [-1, -1, -1,  0, +1, +1, +1,  0];
immutable int [dirs] dCol = [-1,  0, +1, +1, +1,  0, -1, -1];

char [] [] arr;

int componentSizeRecur (int row, int col)
{
        int res = 1;
        arr[row][col] = 'x';
        foreach (dir; 0..dirs)
        {
                auto nRow = row + dRow[dir];
                auto nCol = col + dCol[dir];
                if (arr[nRow][nCol] == '*')
                        res += componentSizeRecur (nRow, nCol);
        }
        return res;
}

void main ()
{
        arr = ["xxxxxxx",
               "xxxx*xx",
               "xx**xxx",
               "xx**x*x",
               "xxxxxxx",
               ].map !(line => line.dup).array;

        foreach (row; 0..arr.length)
                foreach (col; 0..arr.front.length)
                        if (arr[row][col] == '*')
                                writeln (componentSizeRecur (row, col));
}
-----

If the neighbors array is regular and known in advance (like, 4 edge-connected cells, or 8 corner-connected cells as here), you may also like to loop over possible deltas and pick the good ones, like below:

-----
int componentSizeRecur (int row, int col)
{
        int res = 1;
        arr[row][col] = 'x';
        foreach (dRow; -1..+2)
                foreach (dCol; -1..+2)
                        if (dRow || dCol)
                        {
                                auto nRow = row + dRow;
                                auto nCol = col + dCol;
                                if (arr[nRow][nCol] == '*')
                                        res += componentSizeRecur (nRow, nCol);
                        }
        return res;
}
-----

I have to make two additional notes.

1. This works only if the border does not contain '*' characters. To make it work without that restriction, either add two sentinel rows and columns at the four borders of the array, or put an if on nRow and nCol before using them.

2. The recursive solution can eat up lots of stack. If you intend using it on large arrays, make sure you don't hit the stack size limit of the environment. On Windows, it can be achieved by a compiler switch like "-L/STACK:268435456". On Linux, the "ulimit" command may help.

Ivan Kazmenko.

Reply via email to