13
\$\begingroup\$

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?

The task

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

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

9 Answers 9

Reset to default
5
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 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). \$\endgroup\$
    – Calvin's Hobbies
    Jul 18, 2014 at 10:03
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

C# - 548 523 522 511 503 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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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

enter image description here

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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));
    }
}
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ This makes me feel bad about my 476 bytes solution :( +1 for you, good sir. \$\endgroup\$
    – Christoph Böhmwalder
    Jul 21, 2014 at 11:00
1
\$\begingroup\$

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)

More readable

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.
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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

Readable Code

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);
        }
    }
}
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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).

More Readable

 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{
case Coord(adjacentX, adjacentY) if {
    (adjacentX == keyCoord.x + 1 || adjacentX == keyCoord.x - 1) && adjacentY == keyCoord.y ^ 
    (adjacentY == keyCoord.y + 1 || adjacentY == keyCoord.y - 1) && adjacentX == keyCoord.x
  }  => keyCoord->Coord(adjacentX,adjacentY)
}).groupBy(_._1).map(n => (n._1->n._2.map(t=>t._2) ))

val blobs: Iterable[List[Coord]] = adjacencyMap.values.flatMap(v => v.map(coord => adjacencyMap(coord)++v))

val largestBlob: List[Coord] = blobs.collect{case x if (x.length == blobs.map(b=> b.length).max) => x}.head

println(s"""Size: ${largestBlob.length} Coordinates: ${largestBlob.collect{case Coord(x,y) => (x,y)}.mkString(" ")}""")

Criticism is very much appreciated.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.