Yes, I did this for some code golf challenges a while ago [1][2].
It's a simple matter of assigning each 1 an id, and propagating the biggest
one to the neighbors, also known as connected component labeling[3]:
in =: (". ;. _2) 0 : 0
6 6$0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 0 0 0 0 0 1
6 6$0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1
6 6$0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1
6 6$0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1
6 6$0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
6 6$0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
)
connected =: (2<#@~.@,@labelComponents) NB. more than 2 numbers means more
than 1 component.
labelComponents =: maxneighbor@shift^:_id
id =: *i.@:$ NB. Give each point an id
shift =: (>,{,~<0 _1 1)&(|.!.0) NB. Shift to 8 neighbors (diagonal
connection counted too)
maxneighbor =: (>./ * *@{.) NB. find maximum id of neighbors
connected "2 in
[1]
http://codegolf.stackexchange.com/questions/40798/square-circle-triangle-gear/41107#41107
[2]
http://codegolf.stackexchange.com/questions/32015/are-you-in-the-biggest-room/40205#40205
[3]:https://en.wikipedia.org/wiki/Connected-component_labeling
2015-04-12 18:40 GMT+02:00 'Pascal Jasmin' via Programming <
[email protected]>:
> I did develop further the "multiple item Power" function I brought up
> earlier to solve a semihard problem. A write up is here.
>
>
> http://www.jsoftware.com/jwiki/PascalJasmin/Single%20line%20path%20searching%20frameworks
>
>
> But I pose a challenge:
>
> consider these 6 grids:
>
> 0 0 1 1 1 1
> 0 0 1 1 1 1
> 0 0 1 1 1 1
> 0 0 1 1 1 1
> 0 1 1 1 0 1
> 0 0 0 0 0 1
>
> 0 0 1 1 1 1
> 0 0 0 0 1 1
> 0 0 0 0 0 1
> 1 0 0 0 0 1
> 1 1 1 1 1 1
> 1 1 1 1 1 1
>
> 0 0 1 1 1 1
> 0 0 1 1 1 1
> 0 0 0 1 1 1
> 1 1 0 0 0 0
> 1 1 1 1 0 0
> 1 1 1 0 0 1
>
> 0 0 1 1 1 1
> 0 0 1 1 0 0
> 0 0 0 1 0 0
> 1 1 0 0 0 0
> 1 1 1 1 1 1
> 1 1 1 1 1 1
>
> 0 0 0 0 0 1
> 0 0 1 1 0 1
> 0 0 0 0 0 1
> 1 0 0 1 1 1
> 1 1 1 1 1 1
> 1 1 1 1 1 1
>
> 0 0 1 1 1 1
> 0 0 0 0 1 0
> 0 0 0 0 0 0
> 1 0 0 1 1 1
> 1 1 1 1 1 1
> 1 1 1 1 1 1
>
>
>
> The first 2 are "connected" because all of the 1s form a single continuous
> island. The last 4 are not connected because there are more than a single
> continuous island of 1s.
>
> Can you write a function that returns 1 if a grid is connected, 0
> otherwise?
>
> An easier way to load the data for each of the grids.
>
> 6 6$0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 0 0 0 0 0 1
> 6 6$0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1
> 6 6$0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1
> 6 6$0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1
> 6 6$0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 6 6$0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
