El escenario

Conduzco por un camino con mi auto y comienza a llover. Las gotas de lluvia caen al azar en mi ventana y ahora me pregunto, ¿dónde está la mayor área húmeda conectada?

La tarea

Para hacerlo más fácil, la ventana se divide en una matriz de 10 * 10 cuadrados. Su trabajo es encontrar la mayor área de caída de agua conectada en la ventana.

Entrada

Hay dos entradas posibles, puede usar una matriz bidimensional o una unidimensional. Puede elegir entre entradas como stdin, etc.
Ejemplo:

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

Salida

Su código debe incluir el tamaño del área conectada más grande y las coordenadas x e y de las gotas de agua que pertenecen a esta área en el formato
"Tamaño: Coordenadas Z: (X1, Y1) (X2, Y2) .. ".
Ejemplo para la entrada anterior:

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

El orden de las coordenadas no importa.

Reglas

Las gotas de agua están conectadas, si se tocan entre sí ortogonalmente
Las conexiones diagonales no cuentan
Puede haber muchas áreas y su código tiene que encontrar la más grande
Un campo vacío se representa como "0" y un campo húmedo como "1"
Publique su solución con una breve explicación y la salida de la entrada anterior
El código más corto dentro de los próximos 7 días ganará
Si hay dos áreas con el mismo tamaño, puede elegir una

Ganador: Ventero con 171 - Ruby

code-golf izlin
fuente

2

@Doorknob quejándose de un error tipográfico? OP es alemán.

edc65

1

@Doorknob Lo cambié, gracias. El límite de tiempo solo dice cuándo determinaré el ganador, pero aún puede publicar respuestas.

izlin

66

Yo diría que este es un duplicado de codegolf.stackexchange.com/questions/32015/… .

Howard

1

@TeunPronk: OP significa Cartel original.

Búscalo

2

Alguna aclaración sobre qué métodos de entrada están permitidos, exactamente, sería genial.

Ventero

3

Ruby, 171 caracteres

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

Entrada a través del parámetro de línea de comando como matriz unidimensional.

Salida para la entrada de muestra: Size: 6 Coordinates: (1,0) (1,1) (1,2) (1,3) (2,2) (2,1)

Esta respuesta utiliza un enfoque simple de relleno de inundación, construyendo una lista de coordenadas para cada grupo de gotas de lluvia. La mayor parte del código se usa realmente para la verificación de límites y E / S.

Ventero
fuente

5

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

Entrada (pegar antes del código):

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]

Gracias Calvin's Hobbies por las ediciones sugeridas.

Vectorizado
fuente

Puede usar en map(f,range(100))lugar de [f(i)for i in range(100)]guardar 8 caracteres. También creo que sus coordenadas son (y, x) no (x, y).

Hobbies de Calvin

3

C # - 548 523 522 511 503 476

(menos de 500 ... sí)

Estoy seguro de que hay mucho margen de mejora.

La forma en que ingresé los datos fue inicializar una matriz. No incluí esa matriz en el puntaje (si crees que esto es una trampa, puedo cambiar el código, pero agregará relativamente mucho código porque C # no es excelente para analizar matrices)

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

Pruébelo en http://ideone.com/UCVCPM

Nota: La versión actual no funciona en ideone porque no le gusta using l=System.Collections... , por lo que la versión de ideone está un poco desactualizada (y es más larga)

Cómo funciona

Básicamente verifica si hay un 1. Si encuentra uno, se utiliza el algoritmo de relleno por inundación para reemplazar todos los adyacentes 1's con 0y añade las coordenadas reemplazados a una lista temporal. A continuación se compara la lista de arriba ( m) a la lista temporal ( t) y se pone ma tsi tcontiene más elementos.

Christoph Böhmwalder
fuente

3

Mathematica - 180 bytes

Esta función toma una matriz bidimensional.

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

Bonito

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

Ejemplo

{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

Tamaño: 6 Coordenadas: {{1,2}, {2,2}, {2,3}, {3,2}, {3,3}, {4,2}}

La salida es ligeramente anómala. Mathematica comienza a indexar en 1 en lugar de 0, y lo usa {}para indicar la posición. Agregue 2 bytes ( -1) si las posiciones deben estar indexadas en 0. Agregue muchos bytes si necesitan usar en ()lugar de {}:(

Explicación

fes una función de x. Se define ccomo una transformación de x, donde cada (i, j) ahora es igual a un número entero correspondiente al componente conectado al que pertenece. Implica el trabajo principal:

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

ingrese la descripción de la imagen aquí

Luego mcalcula cuántos elementos hay en cada componente, los ordena por ese número y toma el último resultado (es decir, con la mayoría de los elementos). La última línea imprime el recuento y las posiciones en cel índice contenido en m.

mfvonh
fuente

2

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

Entrada

Dos dimensiones y pegar antes del código como g, por ejemplo:

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

Sin golf

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

Rayo
fuente

2

C # 374 función de bytes

Esta es una versión muy modificada de mi respuesta a ¿Estás en la sala más grande? . Toma una matriz unidimensional de entradas y devuelve una cadena en el estilo requerido. Funciona construyendo conjuntos disjuntos a partir de la entrada (primer bucle), calculando el tamaño de cada conjunto y encontrando el conjunto más grande (segundo bucle) y luego agregando las celdas de ese conjunto a una cadena de salida (tercer bucle) que luego se devuelve .

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

Menos golf (y con código de prueba):

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

VisualMelon
fuente

Esto me hace sentir mal por mi solución de 476 bytes :( +1 para usted, buen señor.

Christoph Böhmwalder

1

JavaScript (EcmaScript 6) 183 189

Una función con entrada de matriz y valor de retorno de cadena. Si se necesita una salida real (no está claro para mí) agregue 7 bytes para '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)

Prueba de salida

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

Más legible

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
)

Explicación

Obtenga una matriz de una sola dimensión y un parámetro opcional con el tamaño de una fila. La función también funciona con diferentes dimensiones de matriz, incluso x! = Y.

Pseudocódigo:

 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.

edc65
fuente

1

JavaScript, 273

La función toma una matriz y devuelve una cadena. Mi primer intento fue de ~ 500 caracteres y no usé Flood Fill. Este sí. Estoy aprendiendo JavaScript, por lo que cualquier sugerencia sería apreciada.

Esta función recorre la matriz de entrada y por cada 1 encontrado comienza allí y cambia todos los conectados a 1s a 0 usando la función Rellenar. Al hacerlo, recuerda el blob con más 1s. La función Rellenar cambia la posición actual a 0 y luego se llama a sí misma en la posición superior, a la derecha, debajo y a la izquierda.

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

Prueba aquí: http://goo.gl/9Hz5OH

Código legible

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

JeffSB
fuente

1

Scala, 420

Hola, mi entrada toma una matriz 2d como a List[List[Int]], devuelve unString

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

Explicación

Dada una ventana como a List[List[Int]], primero encontramos cada "1" y guardamos las coordenadas en una lista. Luego convertimos esa lista en unaMap de las coordenadas de cada "1" a una lista de las coordenadas de cada "1" adyacente. Luego use el mapa de adyacencia para vincular de forma transitiva los sub-blobs en blobs, y finalmente devolveremos el blob más grande (e ignorando los blobs duplicados ya que el orden de las coordenadas devueltas no importa).

Más legible

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

La crítica es muy apreciada.

Julian Peeters
fuente

Hay agua en mi ventana

El escenario

La tarea

Entrada

Salida

Reglas

Ganador: Ventero con 171 - Ruby

Respuestas:

Ruby, 171 caracteres

Python - 192

C # - 548 523 522 511 503 476

Cómo funciona

Mathematica - 180 bytes

Golfed

Bonito

Ejemplo

Explicación

Haskell, 246

Entrada

Sin golf

C # 374 función de bytes

JavaScript (EcmaScript 6) 183 189

JavaScript, 273

Scala, 420

Explicación

Más legible