www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Avoid if statements for checking neighboring indexes in a 2D array

reply kerdemdemir <kerdemdemir hotmail.com> writes:
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
}

Is there any better way to achieve this with cool std functions 
like enumerate or iota without needing to write eight if checks?
Jul 16
next sibling parent Nicholas Wilson <iamthewilsonator hotmail.com> writes:
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


 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
 }

 Is there any better way to achieve this with cool std functions 
 like enumerate or iota without needing to write eight if checks?
What you probably want is a convolution, used a lot in image processing. insted of using recursion you walk left to right in blocks of 3x3 and compute a "sum" and then do the same vertically, then each cell contains the number of neighbours that are *. In this case you want the kernel 111 101 111 o o o x x x o o o x x x o o # * x x x x * * x x x x x * * x * x x x x x x o o o x x x o o o x x x o # # x x x x * * x x x x x * * x * x x x x x x x o o o x x x o o o x x x # # o x x x * * x x x x x * * x * x x x x x x x x o o o x x x o o o x x * # o o x x * * x x x x x * * x * x x x x x Have a look at the video on http://halide-lang.org describing the different methods used.
Jul 16
prev sibling next sibling parent Ivan Kazmenko <gassa mail.ru> writes:
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.
Jul 16
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.)
Jul 16
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.)
Jul 16
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 16.07.2017 19:10, Timon Gehr wrote:
 ...
 
 (This works even if there are * at the border.)
Well, not really. :) Version that actually works if there are * at the border: import std.stdio, std.range, std.algorithm, std.array; char[][] arr; int componentSize(int row,int 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=["**xxxx*", "xxxx*xx", "xx**xxx", "xxx*x**", "**xxxxx"].map!dup.array; cartesianProduct(iota(cast(int)arr.length),iota(cast(int)arr[0].length)) .filter!(a=>arr[a[0]][a[1]]=='*') .each!(a=>writeln(componentSize(a.expand))); }
Jul 16
parent reply kerdemdemir <kerdemdemir hotmail.com> writes:
Hi Guys,

 Nicholas , thanks a lot for cool solution but actually I weren't 
working on image processing. I was trying to solve 
"http://codeforces.com/contest/828/problem/B". I really needed 
finding connected components this time.

 Ivan, your solution is much more elegant than what I did. But I 
find  Timon's solution with cartesian product a bit nicer in this 
case since I love to see std function more and more.

Thanks guys for all your advises. D community is really the best.

Here is my solution to question. It seems I didn't get it working 
completely yet. In my debugger(Msvc MonoD) even there are many 
rows it seems Recurse function only loops the columns in the 
first row. And debugger is jumping so strangely I couldn't tag 
the problem.
But I don't expect a big change there should be a small bug that 
is it.

Sorry if code contains some foreign words I just replaced many 
variable names from my native language I might be missing some.

import std.stdio;
import std.string;
import std.algorithm;
import std.conv;
import std.array;
import std.range;
import std.math;

int totalrow;
int totalcolumn;
dchar[][] twoDimensionArray;

struct ConnectedElementsSolver
{
	this(  dchar[][] twoDimArray )
	{
		m_twoDimStruct = twoDimArray;
		Recurse(0, 0);
	}

	void Recurse ( int row, int column )
	{
		if( row < 0 || column < 0  )
			return;

		for ( ; row <  m_twoDimStruct.length ; row++  )
		{
			for ( ; column <  m_twoDimStruct[row].length; column++  )
			{
				Process( row, column, m_twoDimStruct.length, 
m_twoDimStruct[row].length );
			}
		}
	}

	void Process( int row, int column, ulong maxrow, ulong maxcolumn 
)
	{
		if( row < 0 || column < 0 || row >= maxrow || column >= 
maxcolumn  )
			return;

		if (  m_twoDimStruct[row][column] == 'B' )
		{
			m_twoDimStruct[row][column] = 'W';
			m_tempResult.Process(row, column );
			Process(row-1,column-1, maxrow, maxcolumn);
			Process(row,column-1, maxrow, maxcolumn);
			Process(row+1,column-1, maxrow, maxcolumn);				
			Process(row-1,column, maxrow, maxcolumn);				
			Process(row+1,column, maxrow, maxcolumn);				
			Process(row-1,column+1, maxrow, maxcolumn);			
			Process(row,column+1, maxrow, maxcolumn);		
			Process(row-1,column+1, maxrow, maxcolumn);
		}
		else
		{
			if ( m_tempResult.HowManyFilled )
				m_results ~= m_tempResult;
			m_tempResult.Resetle();
		}	
	}

	SquareCandidate   m_tempResult;
	SquareCandidate[] m_results;
	dchar[][] m_twoDimStruct;
}

struct SquareCandidate
{
	int MaxY;
	int MinY;
	int MaxX;
	int MinX;
     int HowManyFilled;

	this( int howManyFilled )
	{
		HowManyFilled = howManyFilled;
	}
	
	void Resetle()
	{
		this = SquareCandidate();
	}


	void Process( int row, int column )
	{
		HowManyFilled++;
		MaxY = max( column, MaxY);
		MinY = min( column, MinY);
		MaxX = max( row, MaxX);
		MinX = min( row, MinX);
	}

	int FindEmptySlots()
	{
		int kareKenarUzunlugu = max(MaxX-MinX, MaxY-MinY);
		int kareAlani = kareKenarUzunlugu*kareKenarUzunlugu;
		return kareAlani - HowManyFilled;
	}
	
	bool CanCreateSquare( int xMax, int yMax )
	{
		int xUzunlugu = MaxX-MinX;
		int yUzunlugu = MaxY-MinY;
		if ( xUzunlugu > yUzunlugu )
         {
			return yMax >= xUzunlugu;
		}
		else
		{
			return xMax >= yUzunlugu;
		}
	}
}


void main()
{
     auto dimensions = stdin.readln.strip.split().map!(a => 
to!int(a)).array();
	totalrow = dimensions[0];
	totalcolumn = dimensions[1];
     twoDimensionArray = stdin
		.byLine()
		.take(totalrow)
		.map!(line => line
			  .map!(a => to!dchar(a))
			  .array())
		.array;

	ConnectedElementsSolver baglantiliElemCozucu = 
ConnectedElementsSolver(twoDimensionArray);
	bool isAnyProblemMakingSquare = 
baglantiliElemCozucu.m_results.any!(a => 
a.CanCreateSquare(totalrow, totalcolumn) == false );
	if ( isAnyProblemMakingSquare )
		writeln(-1);
	
	int sonuc;
	baglantiliElemCozucu.m_results.each!( a => sonuc += 
a.FindEmptySlots() );
	writeln( sonuc );
}
Jul 16
next sibling parent kerdemdemir <kerdemdemir hotmail.com> writes:
Of course now I will try to have it work first. Than replace for 
loops with Cartesian product calls. Than I will make 2D array 
template and even maybe with random access range. And finally for 
being able to use this class later in the some other coding 
challenge I will make Searching( == 'W' part) and Process 
functions passed by parameter.

Thanks a lot for help.
Erdem
Jul 16
prev sibling parent reply Ivan Kazmenko <gassa mail.ru> writes:
On Sunday, 16 July 2017 at 21:50:19 UTC, kerdemdemir wrote:

 			Process(row-1,column-1, maxrow, maxcolumn);
 			Process(row,column-1, maxrow, maxcolumn);
 			Process(row+1,column-1, maxrow, maxcolumn);
 			Process(row-1,column, maxrow, maxcolumn);
 			Process(row+1,column, maxrow, maxcolumn);
 			Process(row-1,column+1, maxrow, maxcolumn);
 			Process(row,column+1, maxrow, maxcolumn);
 			Process(row-1,column+1, maxrow, maxcolumn);
One of "row-1,column+1" should actually be "row+1,column+1". That's where the mentioned ways help. As for the problem itself, it can be solved without finding connected components. I won't post the solution right away because it is potentially a spoiler. See http://codeforces.com/blog/entry/53268 for problem analysis (828B) and http://codeforces.com/contest/828/submission/28637184 for an example implementation in D. Ivan Kazmenko.
Jul 17
parent kerdemdemir <kerdemdemir hotmail.com> writes:
 As for the problem itself, it can be solved without finding 
 connected components.  I won't post the solution right away 
 because it is potentially a spoiler.  See 
 http://codeforces.com/blog/entry/53268 for problem analysis 
 (828B) and 
 http://codeforces.com/contest/828/submission/28637184 for an 
 example implementation in D.

 Ivan Kazmenko.
Wow I understand the question wrongly than, WWWWB WWWWW WWWBB WWBWW I excepted there should be two B squares here. One 3*3 and another 1*1. And my answer would be 6 instead 12 here. Yes if there can be only one black square than my solution would be much more simple. One good thing about D community is when I ask a question here you guys are really nice that I get inspired. Thanks Ivan
Jul 17
prev sibling parent reply Andrea Fontana <nospam example.com> writes:
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.
You can also use a queue to avoid recursion that should improve performances and readibility. Probably using ndslice library could help you! Andrea
Jul 17
parent Ivan Kazmenko <gassa mail.ru> writes:
On Monday, 17 July 2017 at 07:14:26 UTC, Andrea Fontana wrote:

 Probably using ndslice library could help you!
Unfortunately, that's not possible on most online contest platforms like Codeforces. For each programming language and compiler available, only the most basic package is usually installed on the server. There is a mix of reasons involved (historical, maintenance, choice of libraries, more equality for different languages, etc.). That means, e.g., no numpy for Python, no Boost for C++, and no third-party libraries for D. Ivan Kazmenko.
Jul 17