Scenariusz

Jadę samochodem samochodem i zaczyna padać deszcz. Krople deszczu spadają losowo na moje okno, a teraz zadaję sobie pytanie, gdzie jest największy połączony mokry teren?

Zadanie

Aby to ułatwić, okno jest podzielone na macierz 10 * 10 kwadratów. Twoim zadaniem jest znalezienie największego połączonego obszaru zrzutu wody w oknie.

Wejście

Istnieją dwa możliwe dane wejściowe, możesz użyć macierzy dwuwymiarowej lub jednowymiarowej. Możesz wybierać między dowolnymi danymi wejściowymi, takimi jak stdin itp.
Przykład:

// 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]

Wynik

Twój kod musi podawać rozmiar największego połączonego obszaru oraz współrzędne x i y kropli wody należących do tego obszaru w formacie
„Rozmiar: Współrzędne Z: (X1, Y1) (X2, Y2) .. . "
Przykład dla poprzedniego wejścia:

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

Kolejność współrzędnych nie ma znaczenia.

Zasady

• Krople wody są połączone, jeśli dotykają się one ortogonalnie
• Połączenia ukośne się nie liczą
• Może być wiele obszarów, a Twój kod musi znaleźć największy
• Puste pole jest reprezentowane jako „0”, a mokre pole jako „1”
• Zamieść swoje rozwiązanie z krótkim objaśnieniem i wynikiem poprzednich danych wejściowych
• Zwycięży najkrótszy kod w ciągu najbliższych 7 dni
• Jeśli są dwa obszary o tym samym rozmiarze, możesz wybrać jeden

Zwycięzca: Ventero z 171 - Ruby

Ruby, 171 znaków

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

Wprowadź za pomocą parametru wiersza polecenia jako tablicę jednowymiarową.

Dane wyjściowe dla przykładowego wejścia: Size: 6 Coordinates: (1,0) (1,1) (1,2) (1,3) (2,2) (2,1)

W tej odpowiedzi zastosowano proste podejście do wypełniania zalewem, tworząc listę współrzędnych dla każdej grupy kropel deszczu. Większość kodu jest faktycznie używana do sprawdzania granic i we / wy.

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

Dane wejściowe (wklej przed kodem):

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]

Dzięki za hobby Calvina za sugerowane zmiany!

C # - 548 523 522 511 503 476

(poniżej 500 ... tak)

Jestem pewien, że jest wiele miejsca na ulepszenia.

Sposób, w jaki wprowadziłem dane, to zainicjowanie tablicy. Nie uwzględniłem tej tablicy w partyturze (jeśli uważasz, że to oszustwo, mogę zmienić kod, ale doda on stosunkowo dużo kodu, ponieważ C # nie jest dobry w analizowaniu tablic)

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]));}}

Przetestuj na stronie http://ideone.com/UCVCPM

Uwaga: bieżąca wersja nie działa w ideone, ponieważ się nie podoba using l=System.Collections..., więc wersja ideone jest nieco nieaktualna (i dłuższa)

Jak to działa

Zasadniczo sprawdza, czy istnieje 1. Jeżeli stwierdzi jedną, używa algorytmu Wypełnienia zastąpić wszystkie sąsiadujące 1„sz 0i dodaje zastąpionych współrzędne do listy tymczasowego. Następnie porównuje górną listę ( m) z listą tymczasową ( t) i ustawia mna tif, jeśli tzawiera więcej elementów.

Mathematica - 180 bajtów

Ta funkcja przyjmuje tablicę dwuwymiarową.

Grał w golfa

f@x_:=(c=MorphologicalComponents[x,CornerNeighbors->False];m=Last@SortBy[ComponentMeasurements[c,"Count"],Last];Print["Size: ",Last@m," Coordinates: ",Reverse/@Position[c,m[[1]]]])

Ładny

f@x_ := (
   c = MorphologicalComponents[x, CornerNeighbors -> False];
   m = Last@SortBy[ComponentMeasurements[c, "Count"], Last];
   Print["Size: ", Last@m, " Coordinates: ", Reverse/@Position[c, m[[1]]]]
   );

Przykład

{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

Rozmiar: 6 współrzędnych: {{1,2}, {2,2}, {2,3}, {3,2}, {3,3}, {4,2}}

Wyjście jest nieco anomalne. Mathematica rozpoczyna indeksowanie od 1 zamiast 0 i używa {}do wskazania pozycji. Dodaj 2 bajty ( -1), jeśli pozycje muszą być indeksowane 0. Dodaj dużo bajtów, jeśli trzeba ich użyć ()zamiast {}:(

Wyjaśnienie

fjest funkcją x. Definiuje on cjako transformację tego x, gdzie każdy (i, j) jest teraz liczbą całkowitą odpowiadającą, do którego podłączonego komponentu należy. Obejmuje główną pracę:

MorphologicalComponents[w, CornerNeighbors -> False] // Colorize

Następnie moblicza, ile elementów jest w każdym komponencie, sortuje je według tej liczby i przyjmuje ostatni wynik (czyli najwięcej elementów). Ostatni wiersz wypisuje liczbę i pozycje cindeksu zawarte w 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

Wejście

Dwuwymiarowy i wklej przed kodem g, na przykład:

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

Nie golfił

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

Funkcja C # 374 bajtów

To jest mocno zmodyfikowana wersja mojej odpowiedzi na pytanie Czy jesteś w największym pokoju? . Pobiera jednowymiarową tablicę liczb całkowitych i zwraca ciąg znaków w wymaganym stylu. Działa poprzez budowanie rozłącznych zestawów z danych wejściowych (pierwsza pętla), obliczanie wielkości każdego zestawu i znajdowanie największego zestawu (druga pętla), a następnie dołączanie dowolnych komórek w tym zestawie do ciągu wyjściowego (trzecia pętla), który jest następnie zwracany .

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;}

Mniej golfa (z kodem testowym):

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));
    }
}

JavaScript (EcmaScript 6) 183 189

Funkcja z wejściem tablicowym i zwracaną wartością ciągu. Jeśli potrzebne jest wyjście (nie jest to dla mnie jasne), dodaj 7 bajtów dla „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)

Wyjście testowe

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

Bardziej czytelny

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
)

Wyjaśnienie

Uzyskaj tablicę jednowymiarową i opcjonalny parametr o wielkości wiersza. Funkcja działa również z różnymi wymiarami tablicy, nawet x! = Y.

Pseudo kod:

 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

Funkcja przyjmuje tablicę i zwraca ciąg znaków. Moja pierwsza próba to ~ 500 znaków i nie użyłem Flood Fill. Ten robi. Uczę się JavaScript, więc wszelkie sugestie będą mile widziane.

Ta funkcja przechodzi przez tablicę wejściową i dla każdego znalezionego 1 zaczyna się tam i zmienia wszystkie połączone na 1s na 0 za pomocą funkcji Fill. Robiąc to, pamięta kroplę z największą liczbą 1. Funkcja Wypełnienie zmienia bieżącą pozycję na 0, a następnie wywołuje się w pozycji powyżej, w prawo, poniżej i w lewo.

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);}}}

Przetestuj tutaj: http://goo.gl/9Hz5OH

Kod czytelny

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

Cześć, mój wpis przyjmuje tablicę 2d jako a List[List[Int]], zwraca aString

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(" ")}\")

Wyjaśnienie

Biorąc pod uwagę okno jako List[List[Int]], najpierw znajdujemy każde „1” i zapisujemy współrzędne na liście. Następnie zamieniamy tę listę na Mapwspółrzędną każdego „1” na listę współrzędnych każdego sąsiedniego „1”. Następnie użyj mapy sąsiedztwa, aby przejściowo połączyć podpobloki w obiekty BLOB, a na koniec zwracamy największy obiekt BLOB (i ignorujemy zduplikowane obiekty BLOB, ponieważ kolejność zwracanych współrzędnych nie ma znaczenia).

Bardziej czytelny

 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(" ")}""")

Krytyka jest bardzo ceniona.