On 16.07.2017 18:55, Timon Gehr wrote:
On 16.07.2017 12:37, 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
There are two connected '*' group in this example. First group is
composes of six '*' located closer to middle and the second group
composes only one '*' char located in the left bottom corner.
Do to this I generally implement a recursive algorithm which repeat
calling the same function by checking all neighbors around the current
index. I generally end up with something like :
void foo( int row, int col)
{
//Do something here like caching the index
if ( twoDimensionData[row - 1][col] == '*')
foo(row- 1, col);
else if ( twoDimensionData[row + 1][col] == '*')
foo(row+ 1, col);
else if ( twoDimensionData[row - 1 ][col - 1] == '*')
foo(row - 1, col - 1);
//..... I need 5 more of this bad boys I mean if checks
}
...
It is wrong to explore in only one direction, so I assume you do not
mean "else".
Is there any better way to achieve this
foreach(i;row-1..row+2){
foreach(j;col-1..col+2){
if(i==row && j==col) continue;
if(twoDimensionData[i][j] == '*')
foo(row,col);
}
}
with cool std functions like enumerate or iota without needing to
write eight if checks?
cartesianProduct(iota(row-1,row+2),iota(col-1,col+2))
.filter!(a=>(a[0]!=row||a[1]!=col))
.filter!(a=>twoDimensionData[a[0]][a[1]]=='*')
.each!(a=>foo(a.expand));
(You can usually drop the first filter because "doing something" will
usually involve checking if the node has been visited and returning or
else marking the node as visited.)
Ivan's example in this style:
import std.stdio, std.range, std.algorithm, std.array;
char[][] arr;
int componentSize(size_t row, size_t col){
if(row>=arr.length||col>=arr[row].length||arr[row][col]!='*')
return 0;
arr[row][col]='x';
return 1+cartesianProduct(iota(row-1,row+2),iota(col-1,col+2))
.map!(a=>componentSize(a.expand)).sum;
}
void main (){
arr=["xxxxxx*",
"xxxx*xx",
"xx**xxx",
"xx**x**",
"xxxxxxx"].map!dup.array;
cartesianProduct(iota(arr.length),iota(arr[0].length))
.filter!(a=>arr[a[0]][a[1]]=='*')
.each!(a=>writeln(componentSize(a.expand)));
}
(This works even if there are * at the border.)
