13
\$\begingroup\$

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 , 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)
\$\endgroup\$
  • 1
    \$\begingroup\$ This feels very familiar; was it in the Sandbox for a while? \$\endgroup\$ – Shaggy Oct 27 '18 at 23:00
  • 8
    \$\begingroup\$ This is indeed very close to the linked question but I think it can be considered a distant enough subset thereof because generating the matrix is not absolutely necessary for computing the actual width and height. For instance, one possible algorithm would be to count the minimal number of marginal zeros for each row and column and subtract those from the original dimensions. \$\endgroup\$ – Mr. Xcoder Oct 28 '18 at 10:08
  • \$\begingroup\$ related - Highlight the Bounding Box, Part I: Cartesian Grid \$\endgroup\$ – Jonathan Allan Oct 28 '18 at 13:57

16 Answers 16

11
\$\begingroup\$

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
\$\endgroup\$
  • 9
    \$\begingroup\$ All I see is Yahtzee. \$\endgroup\$ – flawr Oct 28 '18 at 8:49
5
\$\begingroup\$

APL (Dyalog Unicode), 10 bytesSBCS

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)

\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ 57 bytes using a numpy array. \$\endgroup\$ – Vincent Oct 29 '18 at 13:27
  • \$\begingroup\$ If we take input as a non-built-in type shouldn't we be counting some kind of import statement to allow us to do so? (It might be just that we have to title the post as "Python 2 with numpy" - I'm not entirely sure) ...if you have some time could you ask in the nineteenth byte chat room? \$\endgroup\$ – Jonathan Allan Oct 29 '18 at 13:35
  • 1
    \$\begingroup\$ ...also 55 bytes right? \$\endgroup\$ – Jonathan Allan Oct 29 '18 at 13:37
  • 1
    \$\begingroup\$ I couldn't really find a clear answer on PPCG Meta, so I'm not sure about this. And yes, 55 bytes indeed :) \$\endgroup\$ – Vincent Oct 29 '18 at 13:47
  • 1
    \$\begingroup\$ I just asked. According to this post, the import doesn't have to be included. \$\endgroup\$ – Vincent Oct 29 '18 at 14:11
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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?
\$\endgroup\$
1
\$\begingroup\$

q/kdb+, 16 bytes

sum@'(|/;|/')@\:
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

R, 48 46 bytes

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

Try it online!

-2 bytes saved by Giuseppe.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ ζ‚Oε0Û0Üg saves 2 bytes. \$\endgroup\$ – Mr. Xcoder Oct 29 '18 at 10:39
  • \$\begingroup\$ @Mr.Xcoder Ah, of course. I was already not too happy about that swap. Can't believe I hadn't thought about doing the pair first and than the sum.. >.> \$\endgroup\$ – Kevin Cruijssen Oct 29 '18 at 10:44
0
\$\begingroup\$

Jelly, 9 bytes

ŒṪZṀ_ṂƊ€‘

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Haskell, 76 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

Ruby, 60 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.