Trim that distracting background off!

Question

Isn't it annoying when you're taking a picture, but the background detracts from the actual substance of the image? I'd say it is. I need to know how much I should crop so that I get rid of this problem! But - as usual - I am quite lazy, so I need someone to do this for me...

Task & Rules

Given a binary matrix representing the image, output the dimensions (width and height) of the smallest sub-matrix that contains all the \$1\$s in the original matrix. A sub-matrix is a block of adjacent entries from the original matrix. Equivalently, it is a new matrix formed by overlapping a subset of adjacent rows and a subset of adjacent columns of the original.

• It is allowed to take the width and the height of the matrix as input as well.
• The input is guaranteed to contain at least one \$1\$.
• You can take input and provide output through any standard method, while taking note that these loopholes are forbidden by default. This is code-golf, so try to complete the task in the least bytes you can manage in your language of choice.

Example

$$\left[\begin{matrix} \color{red}0&\color{red}0&\color{red}0&\color{red}0&\color{red}0&\color{red}0\\ \color{red}0&\color{blue}1&\color{blue}0&\color{blue}1&\color{blue}0&\color{blue}0\\ \color{red}0&\color{blue}1&\color{blue}1&\color{blue}0&\color{blue}1&\color{blue}1\\ \color{red}0&\color{blue}0&\color{blue}1&\color{blue}0&\color{blue}1&\color{blue}0\\ \color{red}0&\color{red}0&\color{red}0&\color{red}0&\color{red}0&\color{red}0\end{matrix}\right] \longrightarrow \left[\begin{matrix}1&0&1&0&0\\1&1&0&1&1\\0&1&0&1&0\end{matrix}\right]\longrightarrow(5,3)$$

Test cases

Input | Output

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

[[0,0,0,0,0],[0,1,0,1,0],[0,0,1,0,0]]
--> (3,2) or (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) or (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) or (3,5)

Answer 1

MATL, 5 bytes

JYaZy

Try it online! Or verify all test cases.

Explanation

JYa   % Implicit input. Unpad matrix. This removes outer zeros
Zy    % Size. Implicit display

Answer 2

APL (Dyalog Unicode), 10 bytes^SBCS

Anonymous tacit prefix function.

(1+⌈/-⌊/)⍸

Try it online!

⍸ indices of 1s.

(…) apply the following tacit function to that:

 ⌊/ the minimum (lowest y coordinate and lowest x coordinate)

 ⌈/- the maximum minus that (this gives us the range)

 1+ one plus that (to be inclusive)

Answer 3

Octave, 57 56 45 bytes

Here find does the heavy lifting: It finds the row and colum indices of the nonzero entries. Then we just have to find the difference between the maximum and the minimum (plus one) for each of those seperately.

Thanks @beaker and @AndrasDeak for -1 byte, and @LuisMendo for -11 bytes!

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

Try it online!

Answer 4

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)

Try it online!

Answer 5

Jelly, 7 bytes

S,§t€0Ẉ

Try it online!

How it works

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.

Answer 6

Python 2,  63  55 bytes

-8 with help from Vincent (take the input matrix as a Numpy array)

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

An unnamed function accepting a 2-d Numpy array of integers (in {0,1}) which returns a list of integers, [width,height].

Try it online!

---

Non-Numpy version in 63 bytes (accepting a list of lists of integers in {0,1}):

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

Try it online!

How?

Given a matrix, a, for each (v) of the transpose, zip(*a), and a itself we find the height required (given the transpose this is the width).

Mapping max across v yields a list of zeros and ones, representing if each row of v contains any ones. The string representation of this list is found using backticks (`...`), this gives a string with a leading [, then the zeros and ones delimited by , (comma+space). We slice this string starting at index one in steps of three using [1::3] getting us a string of only the zeros and ones, which allows us to use the string function strip to remove the outer zeros (strip('0')).

For example:

      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]

Answer 7

Retina 0.8.2, 83 bytes

+`^0+¶|¶0+$

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

Try it online! Explanation:

+`^0+¶|¶0+$

Delete leading and trailing zero rows.

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

Remove all 0s on the lines above the last. Remove all the 1s two, but change the digit underneath on the next line to a 1 in that case. This bitwise or's the rows together.

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

Count the number of rows as the number of newlines plus 1 and the number of columns as the number of digits between the first and last 1.

Answer 8

J, 31 bytes

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

Try it online!

Explanation:

                            ^:_ - 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?

Answer 9

q/kdb+, 16 bytes

sum@'(|/;|/')@\:

Answer 10

Mathematica, 34 bytes

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

Pure function. Takes a nested list of integers as input, and returns a list of two integers (the height followed by the width) as output. The Unicode character is U+F3C7 for \[Transpose].

Answer 11

R, 48 46 bytes

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

Try it online!

-2 bytes saved by Giuseppe.

Answer 12

05AB1E, 11 9 bytes

ζ‚Oε0Û0Üg

-2 bytes thanks to @Mr.Xcoder.

Try it online or verify all test cases.

Explanation:

ζ            # 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

Answer 13

Jelly, 9 bytes

ŒṪZṀ_ṂƊ€‘

Try it online!

Answer 14

Haskell, 76 bytes

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

Try it online!

Answer 15

Japt, 16 15 bytes

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

Try it or run all test cases

---

Explanation

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

Answer 16

Ruby, 60 bytes

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

Try it online!