9

Esta pregunta es similar a Biggest Square en una cuadrícula .

Desafío

Dada una matriz de 1y 0en un formato de cadena "xxxx,xxxxx,xxxx,xx.."o formato de matriz ["xxxx","xxxx","xxxx",...], creará una función que determina el área de la submatriz cuadrada más grande que contiene todo 1.

Una submatriz cuadrada es una de igual ancho y alto, y su función debe devolver el área de la submatriz más grande que solo contiene 1.

Por ejemplo:

Dado "10100,10111,11111,10010", esto se parece a la siguiente matriz:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

Puede ver que la negrita 1crea la submatriz cuadrada más grande de tamaño 2x2, por lo que su programa debe devolver el área que es 4.

Reglas

La submatriz debe ser de igual ancho y alto
La submatriz debe contener solo valores 1
Su función debe devolver el área de la submatriz más grande
En caso de que no se encuentre la submatriz, regrese 1
Puede calcular el área de la submatriz con el número de 1la submatriz

Casos de prueba

Entrada: "10100,10111,11111,10010" Salida: 4

Entrada: "0111,1111,1111,1111" Salida: 9

Entrada "0111,1101,0111" Salida: 1

Este es el código de golf , por lo que gana la respuesta más corta en bytes.

code-golf matrix Luis felipe De jesus Munoz
fuente

3

¿Por qué formato de cadena?

Stewie Griffin

3

¿Podemos tomar la entrada como una matriz binaria (numérica)?

Stewie Griffin

55

¿Para [0] todavía se requiere para la salida 1?

l4m2

66

Espera un momento, ¿por qué devolver 1 cuando no se encuentra la submatriz de todo-1, 0 no tendría mucho más sentido? (De lo contrario, es simplemente un caso especial para manejar)

Jonathan Allan

2

Tal como está, creo que a ambos respondedores no les importaría si cambiaran las especificaciones y recomiendo hacerlo porque no tiene sentido devolver 1 y no hace que las presentaciones sean más interesantes.

ბიმო

2

Jalea , 18 bytes

_{+2 para manejar la salida presente de la sublista no todo-1}

ẆZṡ¥"L€$ẎȦÐfL€Ṁ²»1

Pruébalo en línea! O ver el conjunto de pruebas

¿Cómo?

ẆZṡ¥"L€$ẎȦÐfL€Ṁ²»1 - Link: list of lists of 1s and 0s
Ẇ                  - all slices (lists of "rows") call these S = [s1,s2,...]
       $           - last two links as a monad:
     L€            -   length of each (number of rows in each slice) call these X = [x1, x2, ...]
    "              -   zip with (i.e. [f(s1,x1),f(s2,x2),...]):
   ¥               -     last two links as a dyad:
 Z                 -       transpose (get the columns of the current slice)
  ṡ                -       all slices of length xi (i.e. squares of he slice)
        Ẏ          - tighten (to get a list of the square sub-matrices)
          Ðf       - filter keep if:
         Ȧ         -   any & all (all non-zero when flattened?)
            L€     - length of €ach (the side length)
              Ṁ    - maximum
               ²   - square (the maximal area)
                »1 - maximum of that and 1 (to coerce a 0 found area to 1)

Jonathan Allan
fuente

Increíble. ¿Puedes agregar alguna explicación?

Luis felipe De jesus Munoz

Lo haré, estoy tratando de pensar en más corto primero ...

Jonathan Allan

@ Mr.Xcoder He actualizado para manejar el requisito por ahora

Jonathan Allan

5

Haskell , 113 121 118 117 bytes

x!s=[0..length x-s]
t#d=take t.drop d
f x=last$1:[s*s|s<-min(x!0)$x!!0!0,i<-x!!0!s,j<-x!s,all(>'0')$s#i=<<(s#j)x,s>0]

Pruébalo en línea!

_{-3 bytes gracias a Laikoni !}

_{-1 byte gracias a Lynn !}

_{+8 bytes para el requisito ridículo de devolver 1 para ninguna submatriz de todos 1.}

Explicación / Ungolfed

La siguiente función auxiliar solo crea compensaciones para xpermitir disminuirlas s:

x!s=[0..length x-s]

x#yeliminará yelementos de una lista y luego tomará x:

t#d=take t.drop d

La función frecorre todos los tamaños posibles para las submatrices en orden, genera cada submatriz del tamaño correspondiente, prueba si contiene solo '1'sy almacena el tamaño. Por lo tanto, la solución será la última entrada en la lista:

--          v prepend a 1 for no all-1s submatrices
f x= last $ 1 : [ s*s
                -- all possible sizes are given by the minimum side-length
                | s <- min(x!0)$x!!0!0
                -- the horizontal offsets are [0..length(x!!0) - s]
                , i <- x!!0!s
                -- the vertical offsets are [0..length x - s]
                , j <- x!s
                -- test whether all are '1's
                , all(>'0') $
                -- from each row: drop first i elements and take s (concatenates them to a single string)
                              s#i =<<
                -- drop the first j rows and take s from the remaining
                                      (s#j) x
                -- exclude size 0...........................................
                , s>0
                ]

ბიმო
fuente

4

Haskell , 99 97 bytes

b s@((_:_):_)=maximum$sum[length s^2|s==('1'<$s<$s)]:map b[init s,tail s,init<$>s,tail<$>s]
b _=1

Comprueba si input es una matriz cuadrada de unos con s==('1'<$s<$s), si es así, la respuesta es length ^ 2, else 0. Luego corta recursivamente la primera / última columna / fila y toma el valor máximo que encuentra en cualquier parte.

Pruébalo en línea!

Angs
fuente

3

K (ngn / k) , 33 28 bytes

{*/2#+/|/',/'{0&':'0&':x}\x}

Pruébalo en línea!

ngn
fuente

¡Nunca supe que tenías una versión K!

Zacharý

3

J , 33 27 bytes

-6 bytes gracias a FrownyFrog!

[:>./@,,~@#\(#**/)@,;._3"$]

Pruébalo en línea!

Explicación:

Usaré el primer caso de prueba en mi explicación:

    ] a =. 3 5$1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1

Genero todas las submatrices cuadradas posibles con un tamaño de 1 al número de filas de la entrada.

,~@#\crea una lista de pares para los tamaños de las submatrices ,.uniendo juntas la longitud de los prefijos sucesivos #\de la entrada:

   ,~@#\ a
1 1
2 2
3 3

Luego los uso para cortar x u ;. _3 yla entrada en submatrices. Ya tengo x(la lista de tamaños); yes el argumento correcto ](la entrada).

 ((,~@#\)<;._3"$]) a
┌─────┬─────┬─────┬───┬─┐
│1    │0    │1    │0  │0│
│     │     │     │   │ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│1    │0    │1    │1  │1│
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│1    │1    │1    │1  │1│
└─────┴─────┴─────┴───┴─┘

┌─────┬─────┬─────┬───┬─┐
│1 0  │0 1  │1 0  │0 0│ │
│1 0  │0 1  │1 1  │1 1│ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│1 0  │0 1  │1 1  │1 1│ │
│1 1  │1 1  │1 1  │1 1│ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
└─────┴─────┴─────┴───┴─┘

┌─────┬─────┬─────┬───┬─┐
│1 0 1│0 1 0│1 0 0│   │ │
│1 0 1│0 1 1│1 1 1│   │ │
│1 1 1│1 1 1│1 1 1│   │ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
└─────┴─────┴─────┴───┴─┘

Para cada submatriz (#**/)@,, verifico si consta completamente de 1: aplanar la matriz y multiplicar el número de elementos por su producto. Si todos los elementos son 1s, el resultado será su suma; de lo contrario, 0:

   (#**/)@, 3 3$1 0 0 1 1 1 1 1 1
0
   (#**/)@, 2 2$1 1 1 1
4 

   ((,~@#\)(+/**/)@,;._3"$]) a
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1

0 0 0 0 0
0 0 4 4 0
0 0 0 0 0

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Finalmente, aplané la lista de resultados para cada submatriz y encuentro el máximo:

>./@,

   ([:>./@,,~@#\(+/**/)@,;._3"$]) a
4

Galen Ivanov
fuente

1

,~@#\y "1 2->"$

FrownyFrog

@FrownyFrog ¡Gracias! No sabía sobre"$

Galen Ivanov

1

#es más corto que sumar los 1s.

FrownyFrog

@ FrownyFrog Hmm, realmente lo es. ¡Genial, gracias!

Galen Ivanov

3

APL (Dyalog Unicode) , 35 34 32 bytes

{⌈/{×⍨⍵×1∊{∧/∊⍵}⌺⍵ ⍵⊢X}¨⍳⌊/⍴X←⍵}

Pruébalo en línea!

El SBCS de Adám tiene todos los caracteres en el código

¡La explicación viene eventualmente!

Zacharý
fuente

2

Retina , 143 bytes

%`$
,;#
+%(`(\d\d.+;#)#*
$1¶$&¶$&#
\G\d(\d+,)|\G((;#+¶|,)\d)\d+
$1$2
)r`((11)|\d\d)(\d*,;?#*)\G
$#2$3
1,
#
Lv$`(#+).*;\1
$.($.1*$1
N`
-1G`
^$
1

Pruébalo en línea! El enlace incluye casos de prueba. Toma la entrada como cadenas separadas por comas. Explicación:

%`$
,;#

Agregue a ,para terminar la última cadena, a ;para separar las cadenas de la #sy a #como contador.

+%(`
)

Repita el bloque hasta que no ocurran más subvenciones (porque cada cadena ahora tiene solo un dígito de longitud).

(\d\d.+;#)#*
$1¶$&¶$&#

Triplique la línea, establezca el contador en 1 en la primera línea e increméntelo en la última línea.

\G\d(\d+,)|\G((;#+¶|,)\d)\d+
$1$2

En la primera línea, elimine el primer dígito de cada cadena, mientras que en la segunda línea, elimine todos los dígitos excepto el primero.

r`((11)|\d\d)(\d*,;?#*)\G
$#2$3

En la tercera línea, bit a bit y los dos primeros dígitos juntos.

1,
#

En este punto, cada línea consta de dos valores, a) un contador de ancho horizontal yb) los bits y la cantidad de bits tomados de cada cadena. Convierta los 1s restantes en #s para poder compararlos con el contador.

Lv$`(#+).*;\1
$.($.1*$1

Encuentre cualquier corrida de bits (verticalmente) que coincida con el contador (horizontalmente), correspondiente a los cuadrados de 1s en la entrada original, y al cuadrado la longitud.

N`

Ordenar numéricamente.

-1G`

Toma la más grande.

^$
1

Caso especial de la matriz cero.

Neil
fuente

2

JavaScript, 92 bytes

a=>(g=w=>a.match(Array(w).fill(`1{${w}}`).join(`..{${W-w}}`))?w*w:g(w-1))(W=a.indexOf`,`)||1

Mostrar fragmento de código

f=
a=>(g=w=>a.match(Array(w).fill(`1{${w}}`).join(`..{${W-w}}`))?w*w:g(w-1))(W=a.indexOf`,`)||1
console.log(f('0111,1111,1111,1111'));
console.log(f('10100,10111,11111,10010'));
console.log(f('0111,1101,0111'));

Expandir fragmento

tsh
fuente

2

APL (Dyalog Classic) , 21 20 bytes

×⍨{1∊⍵:1+∇2×/2×⌿⍵⋄0}

Pruébalo en línea!

ngn
fuente

Recursión! ¡Agradable!

Zacharý

@ Zacharý Gracias. En realidad, en lugar de recurrencia, preferiría algo así como k's f \ x para una monádica f, que es (x; fx; ffx; ...) hasta la convergencia, pero no hay un equivalente en APL (todavía). Hacerlo con ⍣≡ toma demasiados bytes.

ngn

2

Python 2 , 117109 bytes

Gracias a @etene por señalar una ineficiencia que me costó un byte adicional.

lambda s:max(i*i for i in range(len(s))if re.search(("."*(s.find(',')-i+1)).join(["1"*i]*i),s))or 1
import re

Pruébalo en línea!

Toma la entrada como una cadena separada por comas. Este es un enfoque basado en expresiones regulares que intenta hacer coincidir la cadena de entrada con los patrones del formulario 111.....111.....111para todos los tamaños posibles del cuadrado.

En mis cálculos, hacer esto con una lambda anónima es solo un poco más corta que la función definida o un programa completo. La or 1parte al final solo es necesaria para manejar el extraño caso de borde, donde debemos generar resultados 1si no hay ninguno en la entrada.

Kirill L.
fuente

2

Python 2 , 116 115 117 109 bytes

Créditos a @Kirill por ayudarme a jugar al golf aún más y por su solución inteligente y temprana

Editar : Golfé 1 byte usando una lambda, no sabía que asignarlo a una variable no contaba para el conteo de bytes.

Edición 2 : Kirill señaló que mi solución no funcionó para los casos en que la entrada solo contiene 1s, tuve que arreglarlo y perdí dos bytes preciosos ...

Edición 3 : más golf gracias a Kirill

Toma una cadena separada por comas, devuelve un entero.

lambda g:max(i*i for i in range(len(g))if re.search(("."*(g.find(",")+1-i)).join(["1"*i]*i),g))or 1
import re

Pruébalo en línea!

Independientemente encontré una respuesta cercana a la de Kiril, es decir, basada en expresiones regulares, excepto que uso re.search ~~y adef~~ .

Utiliza una expresión regular construida durante cada ciclo para hacer coincidir un cuadrado incrementalmente más grande y devuelve el más grande, o 1.

etene
fuente

1

Agradable, de alguna manera automáticamente descarté el ifenfoque como "demasiado largo seguro", pero luego tuve que inventar alguna otra forma de sacar un valor bool del partido. Desafortunadamente, su solución pierde un punto, no puede tener solo range(l), perderá el caso cuando no haya ceros en absoluto. Por ejemplo, tome el segundo caso de prueba y hágalo todo 1s - debería ser 16, no 9.

Kirill L.

Maldición, pensé en probar con todos los ceros pero no con todos (nunca mencionado en el desafío ...). Trataré de inventar algo.

etene

@KirillL. por cierto, eres rápido! Todavía estaba trabajando en mi respuesta cuando publicaste la tuya y estaba un poco desanimado (¡y orgulloso!) Cuando vi que nuestros enfoques eran similares ... el nivel por aquí es impresionante.

Etene

1

Golfé unos pocos bytes más al deshacernos de los duplicados find. Ahora que nuestros códigos ya no son idénticos, sugiero que al menos arreglemos los errores obvios entre nosotros; en su caso, el byte adicional proviene del uso de tupla en ("1"*i,)lugar de la lista.

Kirill L.

Gracias, sí, la tupla inútil es bastante estúpida de mi parte. Y el extra findtambién, eso fue inteligente de tu parte.

etene

2

Ruby `-n` , 63 bytes

p (1..l=$_=~/,|$/).map{|i|/#{[?1*i]*i*(?.*(l-i+1))}/?i*i:1}.max

Pruébalo en línea!

Versión rubí de mi respuesta de Python . Golfier como un programa completo. Alternativamente, una lambda anónima:

Ruby , 70 68 bytes

->s{(1..l=s=~/,|$/).map{|i|s=~/#{[?1*i]*i*(?.*(l-i+1))}/?i*i:1}.max}

Pruébalo en línea!

Kirill L.
fuente

1

Perl 6 , 61 60 58 bytes

{(^$_ X.. ^$_).max({[~&](.[|$^r||*])~~/$(1 x$r)/&&+$r})²}

Pruébalo en línea!

nwellnhof
fuente

1

Python 2 , 138 128 bytes

def f(m):j=''.join;L=j(m);k=map(j,zip(*m));return len(L)and max(len(L)*(len(m)**2*'1'==L),f(k[1:]),f(k[:-1]),f(m[1:]),f(m[:-1]))

Pruébalo en línea!

Salvado

-10 bytes gracias a ovs

TFeld
fuente

1

Clojure, 193 bytes

#(apply max(for [f[(fn[a b](take-while seq(iterate a b)))]R(f next %)R(f butlast R)n[(count R)]c(for[i(range(-(count(first R))n -1)):when(apply = 1(for[r R c(subvec r i(+ i n))]c))](* n n))]c))

Wow, las cosas se intensificaron: o

Menos golfizado:

(def f #(for [rows (->> %    (iterate next)    (take-while seq)) ; row-postfixes
              rows (->> rows (iterate butlast) (take-while seq)) ; row-suffixes
              n    [(count rows)]
              c    (for[i(range(-(count(first rows))n -1)):when(every? pos?(for [row rows col(subvec row i(+ i n))]col))](* n n))] ; rectangular subsections
          c))

NikoNyrh
fuente

La plaza mas grande

Respuestas:

Jalea , 18 bytes

¿Cómo?

Haskell , 113 121 118 117 bytes

Explicación / Ungolfed

Haskell , 99 97 bytes

K (ngn / k) , 33 28 bytes

J , 33 27 bytes

Explicación:

APL (Dyalog Unicode) , 35 34 32 bytes

Retina , 143 bytes

JavaScript, 92 bytes

APL (Dyalog Classic) , 21 20 bytes

Python 2 , 117109 bytes

Python 2 , 116 115 117 109 bytes

Ruby `-n` , 63 bytes

Ruby , 70 68 bytes

Perl 6 , 61 60 58 bytes

Python 2 , 138 128 bytes

Clojure, 193 bytes

La plaza mas grande

Respuestas:

Jalea , 18 bytes

¿Cómo?

Haskell , 113 121 118 117 bytes

Explicación / Ungolfed

Haskell , 99 97 bytes

K (ngn / k) , 33 28 bytes

J , 33 27 bytes

Explicación:

APL (Dyalog Unicode) , 35 34 32 bytes

Retina , 143 bytes

JavaScript, 92 bytes

APL (Dyalog Classic) , 21 20 bytes

Python 2 , 117109 bytes

Python 2 , 116 115 117 109 bytes

Ruby -n , 63 bytes

Ruby , 70 68 bytes

Perl 6 , 61 60 58 bytes

Python 2 , 138 128 bytes

Clojure, 193 bytes

Ruby `-n` , 63 bytes