9

Esta pergunta é semelhante à maior praça de uma grade .

Desafio

Dada uma matriz 1e 0em um formato de cadeia "xxxx,xxxxx,xxxx,xx.."ou formato de matriz ["xxxx","xxxx","xxxx",...], você criará uma função que determina a área da maior submatriz quadrada que contém todas 1.

Uma submatriz quadrada é uma de largura e altura iguais, e sua função deve retornar a área da maior submatriz que contém apenas 1.

Por exemplo:

Dado "10100,10111,11111,10010", isso se parece com a seguinte matriz:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

Você pode ver o negrito 1criar a maior submatriz quadrada de tamanho 2x2, portanto seu programa deve retornar a área que é 4.

Regras

A submatriz deve ser de largura e altura iguais
A submatriz deve conter apenas valores 1
Sua função deve retornar a área da maior submatriz
Caso nenhuma submatriz seja encontrada, retorne 1
Você pode calcular a área da submatriz contando o número de 1na submatriz

Casos de teste

Entrada: "10100,10111,11111,10010" Saída: 4

Entrada: "0111,1111,1111,1111" Saída: 9

Saída de entrada "0111,1101,0111" : 1

Isso é código-golfe , então a resposta mais curta em bytes vence.

code-golf matrix Luis felipe De jesus Munoz
fonte

3

Por que formato de string?

Stewie Griffin

3

Podemos considerar a entrada como uma matriz binária (numérica)?

Stewie Griffin

5

Para [0] ainda é necessário a saída 1?

L4m2

6

Espere um pouco, por que retornar 1 quando nenhuma sub-matriz 1 é encontrada, 0 não faria muito mais sentido? (Caso contrário, é simplesmente um caso especial para lidar com)

Jonathan Allan

2

Como está, acho que os dois respondentes não se importariam se você alterasse as especificações e eu recomendo isso porque não há sentido em retornar 1 e isso não torna os envios mais interessantes.

ბიმო

2

Geléia , 18 bytes

_{+2 para lidar com a saída atual da sublist no-all-1}

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

Experimente online! Ou veja a suíte de testes

Como?

Ẇ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
fonte

Impressionante. Você pode adicionar alguma explicação?

Luis felipe De jesus Munoz

Eu vou, eu estou tentando pensar em mais curto primeiro ...

Jonathan Allan

@ Mr.Xcoder Eu atualizei para lidar com a exigência de agora

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]

Experimente online!

_{-3 bytes graças a Laikoni !}

_{-1 byte graças a Lynn !}

_{+8 bytes para o requisito ridículo de retornar 1 para nenhuma sub-matriz all-1s.}

Explicação / Ungolfed

A seguinte função auxiliar apenas cria deslocamentos para xpermitir diminuí-los s:

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

x#ysoltará yelementos de uma lista e, em seguida, pegará x:

t#d=take t.drop d

A função faz um floop em todos os tamanhos possíveis para sub-matrizes em ordem, gera cada sub-matriz do tamanho correspondente, testa se ela contém apenas se '1'armazena o tamanho. Assim, a solução será a última entrada na 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
                ]

ბიმო
fonte

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

Verifica se a entrada é uma matriz quadrada de apenas uma com s==('1'<$s<$s), se for, a resposta tem comprimento ^ 2, mais o 0. Então, recursivamente divide a primeira / última coluna / linha e leva o valor máximo que encontra em qualquer lugar.

Experimente online!

Angs
fonte

3

K (ngn / k) , 33 28 bytes

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

Experimente online!

ngn
fonte

Eu nunca soube que você tinha uma versão K!

Zacharý

3

J , 33 27 bytes

-6 bytes graças ao FrownyFrog!

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

Experimente online!

Explicação:

Vou usar o primeiro caso de teste na minha explicação:

    ] 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

Eu gero todas as submatrizes quadradas possíveis com tamanho de 1 ao número de linhas da entrada.

,~@#\cria uma lista de pares para os tamanhos das submatrizes ,.unindo o comprimento dos prefixos sucessivos #\da entrada:

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

Então eu os uso para cortar x u ;. _3 ya entrada em submatrizes. Eu já tenho x(a lista de tamanhos); yé o argumento certo ](a 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 se ela consiste inteiramente de 1s: (#**/)@,- achatar a matriz e alterar o número de itens por seu produto. Se todos os itens forem 1s, o resultado será sua soma, caso contrário - 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

Por fim, aplico a lista de resultados para cada submatriz e encontro o máximo:

>./@,

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

Galen Ivanov
fonte

11

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

FrownyFrog

@FrownyFrog Obrigado! Eu não sabia sobre"$

Galen Ivanov

11

#é menor que a soma dos 1s.

FrownyFrog

@ FrownyFrog Hmm, é mesmo. Legal, obrigado!

Galen Ivanov

3

APL (Dyalog Unicode) , 35 34 32 bytes

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

Experimente online!

O SBCS de Adám possui todos os caracteres no código

Explicação chegando eventualmente!

Zacharý
fonte

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

Experimente online! O link inclui casos de teste. Recebe entrada como sequências separadas por vírgula. Explicação:

%`$
,;#

Adicione a ,para finalizar a última cadeia, a ;para separar as cadeias de se #um #como contador.

+%(`
)

Repita o bloco até que não ocorram mais subsituções (porque cada string agora possui apenas um dígito).

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

Triplicar a linha, configurando o contador para 1 na primeira linha e incrementando-o na última linha.

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

Na primeira linha, exclua o primeiro dígito de cada sequência, enquanto na segunda linha, exclua todos os dígitos, exceto o primeiro.

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

Na terceira linha, bit a bit e os dois primeiros dígitos juntos.

1,
#

Nesse ponto, cada linha consiste em dois valores: a) um contador de largura horizontal eb) o bit a bit e o número de bits extraídos de cada string. Converta qualquer 1s restante em #s para que eles possam ser comparados com o contador.

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

Encontre todas as execuções de bits (verticalmente) que correspondam ao contador (horizontalmente), correspondentes aos quadrados de 1s na entrada original e quadrilhe o comprimento.

N`

Classifique numericamente.

-1G`

Pegue o maior.

^$
1

Caso especial da matriz zero.

Neil
fonte

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 snippet 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 snippet

tsh
fonte

2

APL (Dyalog Classic) , 21 20 bytes

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

Experimente online!

ngn
fonte

Recursão! Agradável!

Zachary

@ Zacharý Obrigado. Na verdade, em vez de recursão, prefiro algo como k's f \ x para um f monádico, que é (x; fx; ffx; ...) até a convergência, mas ainda não há equivalente no APL. Fazer isso com ⍣≡ leva muitos bytes.

NGN

2

Python 2 , 117 109 bytes

Os nossos agradecimentos a @etene por apontar uma ineficiência que me custou um 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

Experimente online!

Recebe a entrada como uma sequência separada por vírgula. Essa é uma abordagem baseada em regex que tenta combinar a sequência de entrada com os padrões do formulário 111.....111.....111para todos os tamanhos possíveis do quadrado.

Nos meus cálculos, fazer isso com um lambda anônimo é apenas um pouco menor que a função definida ou um programa completo. A or 1parte no final é necessária apenas para lidar com o caso estranho da aresta, onde devemos produzir 1se não houver nenhum na entrada.

Kirill L.
fonte

2

Python 2 , 116 115 117 109 bytes

Créditos ao @Kirill por me ajudarem a jogar ainda mais e por sua solução inteligente e inicial

Edit : Golfed 1 byte usando um lambda, eu não sabia que atribuí-lo a uma variável não conta para a contagem de bytes.

Edit 2 : Kirill apontou que minha solução não funcionava nos casos em que a entrada contém apenas 1s, tive que corrigi-la e perdi dois bytes preciosos ...

Edit 3 : mais golfe graças a Kirill

Pega uma sequência separada por vírgula e retorna um número inteiro.

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

Experimente online!

Eu encontrei independentemente uma resposta próxima à de Kiril, ou seja, com base em regex, exceto que eu uso re.search ~~e adef~~ .

Ele usa uma regex criada durante cada loop para corresponder a um quadrado incrementalmente maior e retorna o maior ou 1.

eteno
fonte

11

Bom, de alguma forma, descartei automaticamente a ifabordagem como "muito longa, com certeza", mas depois tive que inventar outra maneira de fazer com que um valor bool fora da partida. Infelizmente, sua solução perde um ponto - você não pode ter apenas range(l)- perderá o caso quando não houver zeros. Por exemplo, tomar caso 2º teste e fazer tudo 1s - deve se tornar 16, não 9.

Kirill L.

Porra, pensei em testar com todos os zeros, mas não com todos (nunca mencionado no desafio ...). Vou tentar inventar algo.

eteno

@KirillL. a propósito, você é rápido! Eu ainda estava trabalhando na minha resposta quando você postou a sua e fiquei um pouco chateado (e orgulhoso!) Quando vi nossas abordagens serem semelhantes ... o nível por aqui é impressionante.

eteno

11

Jogou mais alguns bytes eliminando duplicados find. Agora que nossos códigos não são mais idênticos, sugiro que ao menos corrijamos os erros óbvios um do outro - no seu caso, o byte extra vem do uso da tupla em ("1"*i,)vez da lista.

26418 Kirill L.

Obrigado, sim, a tupla inútil é muito estúpida da minha parte. E o extra findtambém, foi inteligente da sua parte.

eteno

2

Ruby `-n` , 63 bytes

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

Experimente online!

Versão Ruby da minha resposta em Python . Golfier como um programa completo. Como alternativa, uma lambda anônima:

Ruby , 70 68 bytes

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

Experimente online!

Kirill L.
fonte

1

Perl 6 , 61 60 58 bytes

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

Experimente online!

Nwellnhof
fonte

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

Experimente online!

Salvou

-10 bytes graças a ovs

TFeld
fonte

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

Uau, as coisas aumentaram: o

Menos golfe:

(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
fonte

A maior praça

Respostas:

Geléia , 18 bytes

Como?

Haskell , 113 121 118 117 bytes

Explicação / Ungolfed

Haskell , 99 97 bytes

K (ngn / k) , 33 28 bytes

J , 33 27 bytes

Explicação:

APL (Dyalog Unicode) , 35 34 32 bytes

Retina , 143 bytes

JavaScript, 92 bytes

APL (Dyalog Classic) , 21 20 bytes

Python 2 , 117 109 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

A maior praça

Respostas:

Geléia , 18 bytes

Como?

Haskell , 113 121 118 117 bytes

Explicação / Ungolfed

Haskell , 99 97 bytes

K (ngn / k) , 33 28 bytes

J , 33 27 bytes

Explicação:

APL (Dyalog Unicode) , 35 34 32 bytes

Retina , 143 bytes

JavaScript, 92 bytes

APL (Dyalog Classic) , 21 20 bytes

Python 2 , 117 109 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