# There is water on my window

## The scenario

I drive along a road with my car and it begins to rain. The raindrops are falling on my window randomly and now i ask myself, where is the biggest connected wet area?

To make it easier, the window is split in a matrix of 10*10 squares. Your job is to find the biggest connected water-drop-area on the window.

## Input

There are two possible inputs, you can use a 2-dimensional Array or a 1-dimensional one. You can choose between any inputs like stdin, etc...
Example:

// 2-dimensional:
[[0,1,0,0,0,0,1,0,0,0],
[0,1,1,0,0,0,0,1,1,0],
[0,1,1,0,0,0,0,1,0,0],
[0,1,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,1,0],
[0,0,0,1,1,0,0,0,1,0],
[0,0,0,1,1,0,0,0,1,0],
[0,0,0,0,0,1,1,0,1,0],
[0,0,0,0,0,1,1,0,1,0],
[0,0,0,0,0,0,0,0,0,0]]

// 1-dimensional
[0,1,0,0,0,0,1,0,0,0,
0,1,1,0,0,0,0,1,1,0,
0,1,1,0,0,0,0,1,0,0,
0,1,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,1,0,
0,0,0,1,1,0,0,0,1,0,
0,0,0,1,1,0,0,0,1,0,
0,0,0,0,0,1,1,0,1,0,
0,0,0,0,0,1,1,0,1,0,
0,0,0,0,0,0,0,0,0,0]


## Output

Your code has to put out the size of the biggest connected area and the x- and y-coordinates of the waterdrops which belong to this area in the format
"Size: Z Coordinates: (X1,Y1) (X2,Y2) ..."
Example for the previous input:

Size: 6 Coordinates: (1,0) (1,1) (2,1) (1,2) (2,2) (1,3)


The order of the Coordinates doesn't matter.

## Rules

• Waterdrops are connected, if they touch each other orthogonally
• Diagonal connections don't count
• There can be many areas and your code has to find the biggest one
• An empty field is represented as "0" and a wet field as "1"
• Post your solution with a short explanation and the output of the previous input
• The shortest code within the next 7 days will win
• If there are two areas with the same size, you can choose one

### Winner: Ventero with 171 - Ruby

• @Doorknob complaining about a typo? OP is german. Jul 18, 2014 at 6:54
• @Doorknob I changed it, thank you. The time limit only says, when I will determine the winner but you can still post answers. Jul 18, 2014 at 6:56
• I'd say this one is a duplicate of codegolf.stackexchange.com/questions/32015/…. Jul 18, 2014 at 6:58
• @TeunPronk: OP means Original Poster. Look it up in Google :) Jul 18, 2014 at 6:59
• Some clarification on what input methods are allowed, exactly, would be great. Jul 18, 2014 at 18:07

# Python - 192

a=10;g+=[0]*a
def f(k):
if g[k]:g[k]=0;return" (%d,%d)"%(k/a,k%a)+f(k+a)+f(k-a)+f(k+(k%a<9))+f(k-(k%a>0))
return''
m=max(map(f,range(100)),key=len)
print"Size: "+len(m)/6+" Coordinates:"+m


Input (Paste before the code):

g=[0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0]


Thanks Calvin's Hobbies for suggested edits!

• You can use map(f,range(100)) instead of [f(i)for i in range(100)] to save 8 characters. Also I believe your coordinates are (y, x) not (x, y). Jul 18, 2014 at 10:03

## Ruby, 171 characters

r=eval *$* u=(0..99).map(&v=->p{-~p*r[p]>0?" (#{r[p]=0;u=p%c=10},#{p/c})"+v[p+c]+v[p-c]+v[u>0?p-1:p]+v[u<9?p+1:p]:""}).max_by &:size puts"Size: #{u.size/6} Coordinates:"+u  Input via command line parameter as one-dimensional array. Output for the sample input: Size: 6 Coordinates: (1,0) (1,1) (1,2) (1,3) (2,2) (2,1) This answer uses a simple flood-fill approach, building a list of coordinates for each raindrop cluster. Most of the code is actually used for bounds checking and I/O. # C# - 548523522511503 476 (under 500... yey) I'm sure there's lots of room for improvement. The way I inputted the data was to initialize an array. I didn't include that array in the score (if you think this is cheating I can change the code, but it will add relatively much code because C# isn't great at parsing arrays) using o=System.Console;using l=System.Collections.Generic.List<int[]>;class P{ static int[,] a ={{0,1,0,0,0,0,1,0,0,0},{0,1,1,0,0,0,0,1,1,0},{0,1,1,0,0,0,0,1,0,0},{0,1,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,1,0},{0,0,0,1,1,0,0,0,1,0},{0,0,0,1,1,0,0,0,1,0},{0,0,0,0,0,1,1,0,1,0},{0,0,0,0,0,1,1,0,1,0},{0,0,0,0,0,0,0,0,0,0}}; static int w=10,h=w,x=0,y;static l t=new l(),m=new l();static void f(int r,int c){if(a[r,c]==1){a[r,c]=0;if(r<h)f(c,r+1);if(r>0)f(c,r-1);if(c<w)f(c+1,r);if(c>0)f(c-1,r);t.Add(new[]{c,r});}}static void Main(){for(;++x<w;)for(y=0;++y<h;){if(a[x,y]==1)f(x,y);if(t.Count>m.Count)m=t.FindAll(r=>true);t.Clear();}o.Write("Size: "+m.Count+" Coordinates: ");m.ForEach(c=>o.Write("({0},{1}) ",c[0],c[1]));}}  Test it at http://ideone.com/UCVCPM Note: The current version doesn't work in ideone because it doesn't like using l=System.Collections..., so the ideone version is slightly outdated (and longer) ## How it works It basically checks if there is a 1. If it finds one, it uses the Flood Fill algorithm to replace all the adjacent 1's with 0 and adds the replaced coordinates to a temporary list. Afterwards it compares the top list (m) to the temporary list (t) and sets m to t if tcontains more elements. # Mathematica - 180 bytes This function takes a 2-dimensional array. ### Golfed f@x_:=(c=MorphologicalComponents[x,CornerNeighbors->False];m=Last@SortBy[ComponentMeasurements[c,"Count"],Last];Print["Size: ",Last@m," Coordinates: ",Reverse/@Position[c,m[[1]]]])  ### Pretty f@x_ := ( c = MorphologicalComponents[x, CornerNeighbors -> False]; m = Last@SortBy[ComponentMeasurements[c, "Count"], Last]; Print["Size: ", Last@m, " Coordinates: ", Reverse/@Position[c, m[[1]]]] );  ### Example {0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0}; w=Partition[%,10]; f@w  Size: 6 Coordinates: {{1,2},{2,2},{2,3},{3,2},{3,3},{4,2}} The output is slightly anomalous. Mathematica starts indexing at 1 instead of 0, and uses {} to indicate position. Add 2 bytes (-1) if the positions need to be 0-indexed. Add a lot of bytes if they need to use () instead of {} :( ### Explanation f is a function of x. It defines c as a transformation of x, where each (i,j) now equals an integer corresponding to which connected component it belongs to. It involves the main work: MorphologicalComponents[w, CornerNeighbors -> False] // Colorize  Then m computes how many elements are in each component, sorts them by that number, and takes the last result (meaning, with the most elements). The last line prints the count, and the positions in c of the index contained in m. # Haskell, 246 r=[0..9] q=[(i,j)|i<-r,j<-r] t v p@(i,j)|elem p v||notElem p q||g!!j!!i==0=v|1<2=foldr(\(k,l)v->t v(i+k,j+l))(p:v)$zip[-1,0,1,0][0,-1,0,1]
(?)=map
a=t[]?q;(b,c)=maximum$zip(length?a)a main=putStrLn.unwords$["Size:",show b,"Coordinates:"]++show?c


## Input

Two dimension and paste before code as g, for example:

g = [[0, 1, 1, ......, 0], [......], ....]


## Ungolfed

field = [
[0,1,0,0,0,0,1,0,0,0],
[0,1,1,0,0,0,0,1,1,0],
[0,1,1,0,0,0,0,1,0,0],
[0,1,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,1,0],
[0,0,0,1,1,0,0,0,1,0],
[0,0,0,1,1,0,0,0,1,0],
[0,0,0,0,0,1,1,0,1,0],
[0,0,0,0,0,1,1,0,1,0],
[0,0,0,0,0,0,0,0,0,0]
]
range = [0..9]
positions = [(i, j) | i <- range, j <- range]
directions = zip [-1, 0, 1, 0] [0, -1, 0, 1]
traverse visited pos@(i, j)
| pos elem visited || pos notElem positions || field!!j!!i == 0 = visited
| otherwise = foldr folder (pos:visited) directions
where folder = (\(di, dj) visited -> traverse visited (i + di, j + dj))
blocks = map (traverse []) positions
(maxCount, maxBlock) = maximum $zip (map length blocks) blocks main = putStrLn.unwords$ ["Size:", show maxCount, "Coordinates:"] ++ map show maxBlock


### C# 374byte function

This is a heavily modified version of my answer to Are you in the biggest room?. It takes a one-dimensional array of ints, and returns a string in the style required. It works by building up disjoint sets from the input (first loop), tallying the size of each set and finding the largest set (second loop) and then appending any cells in that set to an output string (third loop) which is then returned.

static string F(int[]g){int s=10,e=0,d=s*s,a=0,b=d+1;int[]t=new int[b],r=new int[b];t[d]=d;System.Func<int,int>T=null,k=v=>t[T(v)]=t[v]<d?a:d;T=v=>t[v]!=v?T(t[v]):v;for(;a<d;a++)if(g[a]>0){e=t[a]=a;if(a>s)k(a-s);if(a%s>0)k(a-1);}else t[a]=d;for(;a-->0;)e=r[e]<++r[b=T(a)]&&b<d?b:e;var p="Size: "+r[e]+" Coordinates:";for(;d-->1;)p+=T(d)==e?" ("+d%s+","+d/s+")":"";return p;}


Less golfed (and with test code):

class P
{
static int[] z = {0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0};

static string F(int[]g)
{
int s=10,e=0,d=s*s,a=0,b=d+1;

int[]t=new int[b],r=new int[b];
t[d]=d;
System.Func<int,int>T=null,k=v=>t[T(v)]=t[v]<d?a:d;
T=v=>t[v]!=v?T(t[v]):v;

for(;a<d;a++)
if(g[a]>0)
{
e=t[a]=a;
if(a>s)k(a-s);
if(a%s>0)k(a-1);
}
else
t[a]=d;
for(;a-->0;)
e=r[e]<++r[b=T(a)]&&b<d?b:e;

var p="Size: "+r[e]+" Coordinates:";
for(;d-->1;)
p+=T(d)==e?" ("+d%s+","+d/s+")":"";

return p;
}

static void Main()
{
System.Console.WriteLine(F(z));
}
}

• This makes me feel bad about my 476 bytes solution :( +1 for you, good sir. Jul 21, 2014 at 11:00

# JavaScript (EcmaScript 6) 183 189

A function with array input and string return value. If real output is needed (not clear to me) add 7 bytes for 'alert()'.

W=(a,n=10,x=0)=>(F=p=>a[p]|0&&(a[p]=0,o+=' ('+p%n+','+(p/n|0)+')',1+F(p-n)+F(p+n)+F(p-(p%n>0))+F(p+((p+1)%n>0))),a.map((e,p)=>(t=F(p,o=''))>x&&(x=t,k=o)),'Size: '+x+' Coordinates:'+k)


Test Output

Size: 6 Coordinates: (1,0) (1,1) (1,2) (1,3) (2,2) (2,1)


W=(a,n=10,x=0)=>
(
F=p=>
a[p]|0&&(
a[p]=0,o+=' ('+p%n+','+(p/n|0)+')',
1+F(p-n)+F(p+n)+F(p-(p%n>0))+F(p+((p+1)%n>0)) // modulo takes care of not overflowing out of a row
),
a.map((e,p)=>(t=F(p,o=''))>x&&(x=t,k=o)),
'Size: '+x+' Coordinates:'+k
)


Explanation

Get a single dimension array and an optional parameter with the size of a row. The function works also with different array dimensions, even x!=y.

Pseudo code:

 For each element,
try to fill.
During the fill operation build a string with the coordiinates.
Remember the longest fill and the corresponding string and
output that at the end.


## JavaScript, 273

Function takes array and returns string. My first attempt was ~500 characters and did not use Flood Fill. This one does. I'm learning JavaScript so any suggestions would be appreciated.

This function loops through the input array and for each 1 found it starts there and changes all connected to 1s to 0 using the Fill function. While doing so it remembers the blob with the most 1s. The Fill function changes the current position to 0 and then calls itself on the position above, to the right, below, and to the left.

function G(m){var B="",b=0;for(var p=0;p<m.length;p++)if(m[p]){var T="",t=0;
Z(p);if(t>b){b=t;B=T;}}return"Size: "+b+" Coordinates:"+B;function Z(p){if(m[p])
{m[p]=0;t++;T+=" ("+p%10+","+Math.floor(p/10)+")";if(p>9)Z(p-10);if(p%10)Z(p-
1);if(p<90)Z(p+10);if(p%10!=9)Z(p+1);}}}


Test here: http://goo.gl/9Hz5OH

var map = [0, 1, 0, 0, 0, 0, 1, 0, 0, 0,
...
0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

function F(map) {

var bestBlob = "", bestLen=0;
for (var p = 0; p < map.length; p++)
if (map[p]) {
var thisBlob = "", thisLen=0;
Fill(p);
if (thisLen > bestLen){
bestLen=thisLen ; bestBlob = thisBlob;
}
}
return "Size: " + bestLen + " Coordinates:" + bestBlob;

function Fill(p) {
if (map[p]) {
map[p] = 0; thisLen++;
thisBlob += " (" + p % 10 + "," + Math.floor(p / 10) + ")";
if (p > 9) Fill(p - 10);
if (p % 10) Fill(p - 1);
if (p < 90) Fill(p + 10);
if (p % 10 != 9) Fill(p + 1);
}
}
}


# Scala, 420

Hi, my entry takes a 2d array as a List[List[Int]], returns a String

val o=for{(r, y)<-w.zipWithIndex;(v,x)<-r.zipWithIndex;if(v == 1)}yield(x,y);val a=o.flatMap(c=>o.collect{case(x,y)if{(x==c._1+1||x==c._1-1)&&y==c._2^(y==c._2+1||y==c._2-1)&&x==c._1}=>c->(x,y)}).groupBy(_._1).map(n => (n._1->n._2.map(t=>t._2)));val b=a.values.flatMap(v=>v.map(c=>a(c)++v));val l=b.collect{case x if (x.length==b.map(_.length).max)=>x}.head;println(s\"Size: ${l.length} Coordinates:${l.mkString(" ")}\")


## Explanation

Given a window as a List[List[Int]], first we find each "1" and save the coordinates in a list. Next we turn that list into a Map of the coordinate of each "1" to a list the coordinates of every adjacent "1". Then use the adjacency map to transitively link the sub-blobs into blobs, and finally we return the largest blob (and ignoring duplicate blobs since order of the returned coordinates does not matter).

 val w = {
List(//0,1,2,3,4,5,6,7,8,9
List(0,1,0,0,0,0,1,0,0,0), //0
List(0,1,1,0,0,0,0,1,1,0), //1
List(0,1,1,0,0,0,0,1,0,0), //2
List(0,1,0,0,0,0,0,0,0,0), //3
List(0,0,0,0,0,0,0,0,1,0), //4
List(0,0,0,1,1,0,0,0,1,0), //5
List(0,0,0,1,1,0,0,0,1,0), //6
List(0,0,0,0,0,1,1,0,1,0), //7
List(0,0,0,0,0,1,1,0,1,0), //8
List(0,0,0,0,0,0,0,0,0,0)) //9
}

case class Coord(x: Int, y: Int)

val ones: List[Coord] = for{
(row, y)   <- w.zipWithIndex
(value, x) <- row.zipWithIndex
if (value == 1)
} yield Coord(x,y)

val adjacencyMap: Map[Coord, List[Coord]] = ones.flatMap(keyCoord => ones.collect{
println(s"""Size: ${largestBlob.length} Coordinates:${largestBlob.collect{case Coord(x,y) => (x,y)}.mkString(" ")}""")