¡Recorta ese fondo que distrae!

13

¿No es molesto cuando tomas una foto, pero el fondo resta valor a la sustancia real de la imagen? Yo diría que lo es. ¡Necesito saber cuánto debo recortar para deshacerme de este problema! Pero, como siempre, soy bastante vago, así que necesito que alguien haga esto por mí ...

Tarea y Reglas

Dada una matriz binaria que representa la imagen, genera las dimensiones (ancho y alto) de la submatriz más pequeña que contiene todos los 1 s en la matriz original. Una submatriz es un bloque de entradas adyacentes de la matriz original. De manera equivalente, es una nueva matriz formada superponiendo un subconjunto de filas adyacentes y un subconjunto de columnas adyacentes del original.

  • También se permite tomar el ancho y la altura de la matriz como entrada.
  • Se garantiza que la entrada contiene al menos un 1 .
  • Puede tomar entradas y proporcionar salidas a través de cualquier método estándar , mientras toma nota de que estas lagunas están prohibidas de manera predeterminada. Este es el , así que intente completar la tarea en la menor cantidad de bytes que pueda administrar en el idioma que elija.

Ejemplo

[000000010100011011001010000000][101001101101010](5,3)

Casos de prueba

Entrada | Salida

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

[[0,0,0,0,0], [0,1,0,1,0], [0,0,1,0,0]]
-> (3,2) o (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) o (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) o (3,5)
Sr. Xcoder
fuente
1
Esto se siente muy familiar; ¿Estuvo en el Sandbox por un tiempo?
Shaggy
8
De hecho, esto está muy cerca de la pregunta vinculada, pero creo que puede considerarse un subconjunto lo suficientemente distante de la misma porque generar la matriz no es absolutamente necesario para calcular el ancho y la altura reales. Por ejemplo, un posible algoritmo sería contar el número mínimo de ceros marginales para cada fila y columna y restarlos de las dimensiones originales.
Sr. Xcoder

Respuestas:

5

APL (Dyalog Unicode) , 10 SBCS de bytes

Función de prefijo tácito anónimo.

(1+⌈/-⌊/)⍸

Pruébalo en línea!

 índices de 1s.

() Aplica la siguiente función tácita a eso:

⌊/ el mínimo ( coordenada y más baja y coordenada x más baja )

⌈/- el máximo menos eso (esto nos da el rango)

1+ uno más que (para ser inclusivo)

Adán
fuente
5

Octava , 57 56 45 bytes

Aquí findrealiza el trabajo pesado: findslos índices de fila y columna de las entradas distintas de cero. Entonces solo tenemos que encontrar la diferencia entre el máximo y el mínimo (más uno) para cada uno de ellos por separado.

¡Gracias @beaker y @AndrasDeak por -1 byte, y @LuisMendo por -11 bytes!

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

Pruébalo en línea!

falla
fuente
3

Jalea , 7 bytes

S,§t€0Ẉ

Pruébalo en línea!

Cómo 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
fuente
3

Python 2 ,  63  55 bytes

-8 con ayuda de Vincent (tome la matriz de entrada como una matriz de Numpy)

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

Una función sin nombre aceptar un 2-d Numpy matriz de enteros (en {0,1}) que devuelve una lista de números enteros, [width,height].

Pruébalo en línea!


Versión no Numpy en 63 bytes (aceptando una lista de listas de enteros en {0,1}):

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

Pruébalo en línea!

¿Cómo?

Dada una matriz, a, forcada uno ( v) de la transpuesta, zip(*a)ya sí nos encontramos con la altura requerida (dada la transpuesta esta es la anchura).

La asignación a maxtravés de varroja una lista de ceros y unos, que representa si cada fila vcontiene alguno. La representación de cadena de esta lista se encuentra usando backticks ( `...`), esto le da una cadena con un inicio [, luego los ceros y los delimitados por , (coma + espacio). Cortamos esta cadena comenzando en el índice uno en pasos de tres usando [1::3]solo una cadena de ceros y unos, lo que nos permite usar la función de cadena strippara eliminar los ceros externos ( strip('0')).

Por ejemplo:

      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
fuente
57 bytes usando una matriz numpy.
Vincent
Si tomamos la entrada como un tipo no incorporado, ¿no deberíamos contar algún tipo de declaración de importación que nos permita hacerlo? (Puede ser que tengamos que titular la publicación como "Python 2 con numpy", no estoy completamente seguro) ... si tiene algo de tiempo, ¿podría preguntar en la sala de chat del siglo XIX?
Jonathan Allan
1
... también 55 bytes ¿verdad?
Jonathan Allan
1
Realmente no pude encontrar una respuesta clara sobre PPCG Meta , así que no estoy seguro de esto. Y sí, 55 bytes de hecho :)
Vincent
1
Yo sólo pregunté. Según esta publicación , la importación no tiene que ser incluida.
Vincent
1

Retina 0.8.2 , 83 bytes

+`^0+¶|¶0+$

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

Pruébalo en línea! Explicación:

+`^0+¶|¶0+$

Elimine las filas cero iniciales y finales.

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

Elimine todas las 0s en las líneas arriba de la última. Elimine todos los 1s dos, pero cambie el dígito debajo de la línea siguiente a a 1en ese caso. Esto es bit a bit o son las filas juntas.

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

Cuente el número de filas como el número de líneas nuevas más 1 y el número de columnas como el número de dígitos entre el primero y el último 1.

Neil
fuente
1

J , 31 bytes

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

Pruébalo en línea!

Explicación:

                            ^:_ - 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
fuente
1

q / kdb +, 16 bytes

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

Mathematica, 34 bytes

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

Pura función. Toma una lista anidada de enteros como entrada y devuelve una lista de dos enteros (la altura seguida por el ancho) como salida. El carácter Unicode es U + F3C7 para \[Transpose].

LegionMammal978
fuente
1

R , 48 46 bytes

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

Pruébalo en línea!

-2 bytes guardados por Giuseppe.

Kirill L.
fuente
1

05AB1E , 11 9 bytes

ζ‚Oε0Û0Üg

-2 bytes gracias a @ Mr.Xcoder .

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

ζ            # 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
fuente
1
ζ‚Oε0Û0Ügahorra 2 bytes.
Sr. Xcoder
@ Mr.Xcoder Ah, por supuesto. Ya no estaba muy contento con ese intercambio. No puedo creer que no haya pensado en hacer el par primero y luego la suma ..>.>
Kevin Cruijssen
0

Japt, 16 15 bytes

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

Pruébalo o ejecuta todos los casos de prueba


Explicación

[   ]               :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
Lanudo
fuente