Apare esse fundo perturbador!

13

Não é chato quando você está tirando uma foto, mas o fundo diminui a substância real da imagem? Eu diria que sim. Preciso saber quanto devo cortar para me livrar desse problema! Mas - como sempre - sou muito preguiçosa, então preciso de alguém para fazer isso por mim ...

Tarefa e Regras

Dada uma matriz binária que representa a imagem, imprima as dimensões (largura e altura) da menor sub-matriz que contém todos os 1 s na matriz original. Uma sub-matriz é um bloco de entradas adjacentes da matriz original. Equivalentemente, é uma nova matriz formada pela sobreposição de um subconjunto de linhas adjacentes e um subconjunto de colunas adjacentes do original.

  • É permitido levar também a largura e a altura da matriz.
  • A entrada é garantida para conter pelo menos um .1
  • Você pode obter entrada e fornecer saída através de qualquer método padrão , observando que essas brechas são proibidas por padrão. Isso é , então tente concluir a tarefa no mínimo de bytes que você puder gerenciar no seu idioma preferido.

Exemplo

[0 00 00 00 00 00 00 010 010 00 00 0110 0110 00 010 010 00 00 00 00 00 00 0][10 010 00 0110 0110 010 010 0](5,3)

Casos de teste

Entrada | Resultado

[[0,1,0,0,0,1,0]]
-> (5,1) ou (1,5)

[[0,0,0,0,0], [0,1,0,1,0], [0,0,1,0,0]]
-> (3,2) ou (2,3)

[[1,1,1,1], [0,0,0,0], [0,0,0,0], [1,0,0,0]]
-> (4,4)

[[0,0,0,0,0,0], [0,1,0,1,0,1], [0,0,0,0,0,0]]
-> (5,1) ou (1,5)

[[0,0,0,0,0], [0,1,0,1,0], [0,0,1,0,0], [0,1,0,1,0], [ 0,0,0,0,0]]
-> (3,3)

[[0,0,0,0,0,0], [0,1,0,1,0,0], [0,1,1,0,1,1], [0,0,1, 0,1,0], [0,0,0,0,0,0]]
-> (5,3) ou (3,5)
Mr. Xcoder
fonte
1
Isso parece muito familiar; ficou na Sandbox por um tempo?
Salsicha
8
Isso é realmente muito próximo da questão vinculada, mas acho que pode ser considerado um subconjunto suficientemente distante, porque gerar a matriz não é absolutamente necessário para calcular a largura e a altura reais. Por exemplo, um algoritmo possível seria contar o número mínimo de zeros marginais para cada linha e coluna e subtrair os das dimensões originais.
Xcoder 28/10

Respostas:

5

APL (Dyalog Unicode) , SBCS de 10 bytes

Função de prefixo tácito anônimo.

(1+⌈/-⌊/)⍸

Experimente online!

 índices de 1s.

() Aplique a seguinte função tácita a isso:

⌊/ o mínimo (menor coordenada y e menor coordenada x )

⌈/- o máximo menos isso (isso nos dá o alcance)

1+ um mais que (para ser inclusivo)

Adão
fonte
5

Oitava , 57 56 45 bytes

Aqui findestá o trabalho pesado: são findsos índices de linha e coluna das entradas diferentes de zero. Então, apenas precisamos encontrar a diferença entre o máximo e o mínimo (mais um) para cada um deles separadamente.

Obrigado @beaker e @AndrasDeak por -1 byte e @LuisMendo por -11 bytes!

@(a){[I{1:2}]=find(a),cellfun(@range,I)}{2}+1

Experimente online!

flawr
fonte
3

Python 2 , 92 86 bytes

def f(a,L=len):exec"a=zip(*a[1-any(a[0]):])[::-1];"*4*L(a[0])*L(a);return L(a[0]),L(a)

Experimente online!

Chas Brown
fonte
3

Geléia , 7 bytes

S,§t€0Ẉ

Experimente online!

Como funciona

S,§t€0Ẉ  Main link. Argument: M (matrix)

S        Take the columnwise sum. Let's call the resulting array A.
  §      Take the sum of each row. Let's call the resulting array B.
 ,       Pair; yield [A, B].
   t€0   Trim surrounding zeroes of A and B.
      Ẉ  Widths; yields the lengths of the trimmed arrays.
Dennis
fonte
3

Python 2 ,  63  55 bytes

-8 com a ajuda de Vincent (use a matriz de entrada como uma matriz Numpy)

lambda a:[len(`a.max(x)`[7::3].strip('0'))for x in 0,1]

Uma função sem nome que aceita uma matriz Numpy 2D de números inteiros (pol {0,1}) que retorna uma lista de números inteiros [width,height],.

Experimente online!


Versão não numpy em 63 bytes (aceitando uma lista de listas de números inteiros em {0,1}):

lambda a:[len(`map(max,v)`[1::3].strip('0'))for v in zip(*a),a]

Experimente online!

Quão?

Dada uma matriz, a, forcada ( v) da transposição, zip(*a)e aem si encontramos a altura necessária (dado a transposta esta é a largura).

O mapeamento maxentre vproduz uma lista de zeros e uns, representando se cada linha de vcontém algum. A representação de string desta lista é encontrada usando backticks ( `...`), isso fornece uma string com um à esquerda [, depois os zeros e os delimitados por , (vírgula + espaço). Nós dividimos essa string iniciando no índice um em etapas de três usando [1::3]uma string apenas de zeros e uns, o que nos permite usar a função string strippara remover os zeros externos ( strip('0')).

Por exemplo:

      a = [[0,0,0,0,0]           map(max,a)                    = [0,1,1]
          ,[0,1,0,0,0]          `map(max,a)`[1::3]             = '011'
          ,[0,0,0,1,0]]         `map(max,a)`[1::3].strip('0')  = '11'
                            len(`map(max,a)`[1::3].strip('0')) = 2

zip(*a) = [(0,0,0)         map(max,zip(*a))                    = [0,1,0,1,0]
          ,(0,1,0)        `map(max,zip(*a))`[1::3]             = '01010'
          ,(0,0,0)        `map(max,zip(*a))`[1::3].strip('0')  = '101'
          ,(0,0,1)    len(`map(max,zip(*a))`[1::3].strip('0')) = 3
          ,(0,0,0)]

    --> [len(`map(max,v)`[1::3].strip('0'))for v in zip(*a),a] = [3,2]
Jonathan Allan
fonte
57 bytes usando uma matriz numpy.
28418 Vincent Vincent
Se considerarmos a entrada como um tipo não incorporado, não deveríamos estar contando algum tipo de declaração de importação para permitir isso? (Pode ser que tenhamos que nomear o post como "Python 2 com numpy" - não tenho muita certeza) ... se você tiver algum tempo, poderá perguntar na sala de bate-papo com dezenove bytes?
Jonathan Allan
1
... também 55 bytes, certo?
Jonathan Allan
1
Não consegui encontrar uma resposta clara sobre o PPCG Meta , por isso não tenho certeza. E sim, 55 bytes na verdade :)
Vincent
1
Eu apenas perguntei. De acordo com este post , a importação não precisa ser incluída.
28418 Vincent
1

Retina 0.8.2 , 83 bytes

+`^0+¶|¶0+$

+1`((.)*).(¶(?<-2>.)*).(?<=(1)¶.*|(.))
$1$3$4$5
(¶?)*0*(.*1)0*
$#1 $.2

Experimente online! Explicação:

+`^0+¶|¶0+$

Exclua as linhas zero à esquerda e à direita.

+1`((.)*).(¶(?<-2>.)*).(?<=(1)¶.*|(.))
$1$3$4$5

Remova todos os 0s nas linhas acima da última. Remova todos os 1dois, mas mude o dígito abaixo na próxima linha para a 1nesse caso. Este bit a bit ou são as linhas juntas.

(¶?)*0*(.*1)0*
$#1 $.2

Conte o número de linhas como o número de novas linhas mais 1 e o número de colunas como o número de dígitos entre o primeiro e o último 1.

Neil
fonte
1

J , 31 bytes

[:$([:|.@|:}.^:(0=1#.{.))^:4^:_

Experimente online!

Explicação:

                            ^:_ - repeat until the result stops changing
   (                    )^:4    - repeat 4 times
             ^:(        )       - is
                  1#.           - the sum of
                      {.        - the first row
                 =              - equal 
                0               - to 0
           }.                   - if yes, drop the first row
    [:|.@|:                     - transpose and reverse (rotate 90 degrees) 
[:$                             - what's the shape of the result?
Galen Ivanov
fonte
1

q / kdb +, 16 bytes

sum@'(|/;|/')@\:
Thomas Smyth
fonte
1

Mathematica, 34 bytes

Max@#-Min@#+1&/@(#~Position~1)&

Função pura. Pega uma lista aninhada de números inteiros como entrada e retorna uma lista de dois números inteiros (a altura seguida pela largura) como saída. O caractere Unicode é U + F3C7 para \[Transpose].

LegionMammal978
fonte
1

R , 48 bytes 46

function(m)1+diff(apply(which(m>0,T),2,range))

Experimente online!

-2 bytes salvos por Giuseppe.

Kirill L.
fonte
1

05AB1E , 11 9 bytes

ζ‚Oε0Û0Üg

-2 bytes graças a @ Mr.Xcoder .

Experimente online ou verifique todos os casos de teste .

Explicação:

ζ            # Swap the rows and columns of the (implicit) input-list
            # Pair it with the (implicit) input-list
  O          # Take the sum of each column and row
   ε         # Map Both the list of column-sums and list of row-sums to:
    0Û       #  Remove all leading zeros
      0Ü     #  Remove all trailing zeros
        g    #  Take the length of the remaining lists
Kevin Cruijssen
fonte
1
ζ‚Oε0Û0Ügeconomiza 2 bytes.
Sr. Xcoder
@ Mr.Xcoder Ah, é claro. Eu já não estava muito feliz com essa troca. Não posso acreditar que eu não tinha pensado em fazer o par primeiro e que a soma ..>.>
Kevin Cruijssen
0

Haskell , 76 bytes

f x=length.s.reverse.s<$>[foldr(zipWith(:))e x,x]
e=[]:e
s=snd.span(all(<1))

Experimente online!

Laikoni
fonte
0

Japonês, 16 15 bytes

[UUy]®=ðd)ÎaZÌÄ

Experimente ou execute todos os casos de teste


Explicação

[   ]               :Create an array containing
 U                  : The input and
  Uy                : The input transposed
     ®              :Map each Z
       ð            : Indices of elements where
        d           :  Any element is truthy (not 0)
      =  )          : Reassign to Z
          Î         : First element
           a        : Absolute difference with
            ZÌ      :  Last element
              Ä     :   Plus 1
Shaggy
fonte
0

Ruby , 60 bytes

->m{[m,m.transpose].map{|x|x.map(&:max).join[/1.*/]=~/0*$/}}

Experimente online!

GB
fonte