Remove surrounding zeroes of a 2d array

Question

This is a 2-dimensional version of this question.

Given a non-empty 2-dimensional array/matrix containing only non-negative integers:

$$ \begin{bmatrix} {\color{Red}0} & {\color{Red}0} & {\color{Red}0} & {\color{Red}0} & {\color{Red}0} \\ {\color{Red}0} & {\color{Red}0} & 0 & 1 & 0 \\ {\color{Red}0} & {\color{Red}0} & 0 & 0 & 1 \\ {\color{Red}0} & {\color{Red}0} & 1 & 1 & 1 \\ {\color{Red}0} & {\color{Red}0} & {\color{Red}0} & {\color{Red}0} & {\color{Red}0} \end{bmatrix} $$

Output the array with surrounding zeroes removed, i.e. the largest contiguous subarray without surrounding zeroes:

$$ \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix} $$

Examples:

$$ \begin{bmatrix} {\color{Red}0} & {\color{Red}0} & {\color{Red}0} & {\color{Red}0} & {\color{Red}0} \\ {\color{Red}0} & {\color{Red}0} & 0 & 1 & 0 \\ {\color{Red}0} & {\color{Red}0} & 0 & 0 & 1 \\ {\color{Red}0} & {\color{Red}0} & 1 & 1 & 1 \\ {\color{Red}0} & {\color{Red}0} & {\color{Red}0} & {\color{Red}0} & {\color{Red}0} \end{bmatrix} \mapsto \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix} $$

Input:
[[0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1], [0, 0, 1, 1, 1], [0, 0, 0, 0, 0]]

Output:
[[0, 1, 0], [0, 0, 1], [1, 1, 1]]

$$ \begin{bmatrix} {\color{Red}0} & {\color{Red}0} & {\color{Red}0} & {\color{Red}0} \\ {\color{Red}0} & 0 & 0 & 3 \\ {\color{Red}0} & 0 & 0 & 0 \\ {\color{Red}0} & 5 & 0 & 0 \\ {\color{Red}0} & {\color{Red}0} & {\color{Red}0} & {\color{Red}0} \end{bmatrix} \mapsto \begin{bmatrix} 0 & 0 & 3 \\ 0 & 0 & 0 \\ 5 & 0 & 0 \end{bmatrix} $$

Input:
[[0, 0, 0, 0], [0, 0, 0, 3], [0, 0, 0, 0], [0, 5, 0, 0], [0, 0, 0, 0]]

Output:
[[0, 0, 3], [0, 0, 0], [5, 0, 0]]

$$ \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} \mapsto \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} $$

Input:
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Output:
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

$$ \begin{bmatrix} {\color{Red}0} & {\color{Red}0} & {\color{Red}0} & {\color{Red}0} \\ {\color{Red}0} & {\color{Red}0} & {\color{Red}0} & {\color{Red}0} \\ {\color{Red}0} & {\color{Red}0} & {\color{Red}0} & {\color{Red}0} \end{bmatrix} \mapsto \begin{bmatrix} \end{bmatrix} $$

Input:
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

Output:
[]

$$ \begin{bmatrix} {\color{Red}0} & {\color{Red}0} & {\color{Red}0} & {\color{Red}0} \\ 1 & 1 & 1 & 1 \\ {\color{Red}0} & {\color{Red}0} & {\color{Red}0} & {\color{Red}0} \end{bmatrix} \mapsto \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix} $$

Input:
[[0, 0, 0, 0], [1, 1, 1, 1], [0, 0, 0, 0]]

Output:
[[1, 1, 1, 1]]

$$ \begin{bmatrix} {\color{Red}0} & 1 & {\color{Red}0} & {\color{Red}0} \\ {\color{Red}0} & 1 & {\color{Red}0} & {\color{Red}0} \\ {\color{Red}0} & 1 & {\color{Red}0} & {\color{Red}0} \end{bmatrix} \mapsto \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} $$

Input:
[[0, 1, 0, 0], [0, 1, 0, 0], [0, 1, 0, 0]]

Output:
[[1], [1], [1]]

$$ \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix} \mapsto \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix} $$

Input:
[[1, 1, 1, 1], [1, 2, 3, 1], [1, 1, 1, 1]]

Output:
[[1, 1, 1, 1], [1, 2, 3, 1], [1, 1, 1, 1]]

Answer 1

Wolfram Language (Mathematica), 42 bytes

#&@@CellularAutomaton[{,{},0{,}},{#,0},0]&

Try it online!

Cellular automata are indeed the answer to life, the universe, and everything.¹

How?

CellularAutomaton accepts an input array and an optional background value. Thus, {#,0} specifies that a cellular automaton rule should be applied to the input, assuming a background of 0s.

A neat thing here is that CellularAutomaton crops the output so that no border of background cells is present (because otherwise the output lies on an infinite plane).

The code applies the rule {Null, {}, {0, 0}} -- applying the head Null to the 0-radius neighbor of each cell (i.e. only the center: the cell itself) -- exactly 0 times. The result of this is the original input, but with background removed (i.e. cropping out surrounding 0s).

---

^{1. See the bytecount of my answer? ;)}

Answer 2

JavaScript (ES6), 98 bytes

(a,z)=>(g=A=>A.slice(A.map(m=M=(r,i)=>M=(z?a:r).some(n=>z?n[i]:n)?1/m?i:m=i:M)|m,M+1))(a).map(z=g)

Try it online!

How?

To overcome the lack of a zip built-in, we define a function g() that is able to operate on either the rows or the columns of the input matrix a[ ], depending on the value of the global flag z.

g() looks for the minimum index m and maximum index M of either non-empty rows (if z is undefined) or non-empty columns (if z is defined) and returns the corresponding slice of either the matrix itself or a given row of the matrix.

To summarize:

• we first remove rows by invoking g() on the matrix with z undefined
• we then remove columns by invoking g() on each row with z defined, which leads to this rather unusual .map(z=g)

Commented

(a, z) => (               // a[] = input matrix; z is initially undefined
  g = A =>                // g() = function taking A = matrix or row
    A.slice(              //   eventually return A.slice(m, M + 1)
      A.map(m = M =       //     initialize m and M to non-numeric values
        (r, i) =>         //     for each row or cell r at position i in A:
        M = (z ? a : r)   //       iterate on either the matrix or the row
        .some(n =>        //       and test whether there's at least one
          z ? n[i] : n    //       non-zero cell in the corresponding column or row
        ) ?               //       if so:
          1 / m ? i       //         update the maximum index M (last matching index)
                : m = i   //         and minimum index m (first matching index)
        :                 //       otherwise:
          M               //         let M (and m) unchanged
      ) | m,              //     end of map(); use m as the first parameter of slice()
      M + 1               //     use M+1 as the second parameter of slice()
    )                     //   end of slice()
  )(a)                    // invoke g() on the matrix with z undefined
  .map(z = g)             // invoke g() on each row of the matrix with z defined

Answer 3

MATL, 3 bytes

JYa

Try it online! Or verify all test cases.

Explanation

J      % Push 1j
Ya     % With complex 2nd input, this unpads the matrix in the
       % 1st input (implicit). The unpad value is 0 by default
       % Display (implicit)

Answer 4

Haskell, 62 61 bytes

f.f.f.f
f=reverse.foldr(zipWith(:))e.snd.span(all(<1))
e=[]:e

Try it online!

foldr(zipWith(:))e with e=[]:e is a slightly shorter transpose, and snd.span(all(<1)) drops leading lists of zeros from a list of list. As transpose followed by reverse on a 2D list equals an rotation by 90°, the code f.f.f.f is just four times drop leading lists of zeros and rotate.

Answer 5

Pyth, 13 bytes

V2=.sCQ]m0Q;Q

Try it online!

Answer 6

Jelly, 10 bytes

œr€0z0Uµ4¡

Try it online!

Answer 7

Brachylog, 24 22 20 19 bytes

{s.h+>0∧.t+>0∧}\↰₁\

Try it online!

Outputs the result matrix as an array of arrays, or false for empty output.

(Thanks to @Fatalize for suggesting inline predicate and saving 1 byte.)

Explanation

Predicate 0 (Main):

{...}     Define and call predicate 1 to remove all-zero rows
  \       Transpose the result
   ↰₁     Call pred 1 again, now to remove all-zero columns
     \    Transpose the result to have correct output orientation

Predicate 1:

?s.h+>0∧.t+>0∧
  .           output is
 s              a subsequence of the rows of
?              the input (implicit)
   h          also, output's head element (first row)
    +>0        has a sum > 0 (i.e. has at least one non-zero value)
       ∧.t+>0  and similarly the output's tail element (last row)
∧              (don't implicitly unify that 0 with the output)

Answer 8

R, 96 100 97 bytes

function(m)m[~m,~t(m),drop=F]
"~"=function(x,z=seq(r<-rowSums(x)))z>=min(y<-which(r>0))&z<=max(y)

Try it online!

The ~ helper takes a non-negative vector and returns a vector with FALSE for the "exterior" 0s of the vector and TRUE for positives and any "interior" 0s. This function is applied to the row and column sums of the input matrix.

~ and ! use R's parser treatment of operators.

Corrected as per @DigEmAll's comment, but with some bytes golfed back from @J.Doe

Answer 9

R, 89 79 bytes

function(m,y=apply(which(m>0,T),2,range)){y[!1/y]=0;m[y:y[2],y[3]:y[4],drop=F]}

Try it online!

Thanks to @ngm for the test cases code, and @J.Doe for saving 10 bytes !

• I had to add drop=F parameter due to the default R behavior turning single row/col matrix into vectors...

Answer 10

APL (Dyalog Classic), 17 15 bytes

{⍉⌽⍵⌿⍨∨\∨/×⍵}⍣4

Try it online!

Answer 11

Python 2, 71 bytes

Returns by modifying the input. A list should be passed as input.

def f(a):exec'while a and 1>sum(a[-1]):a.pop()\na[:]=zip(*a)[::-1]\n'*4

Try it online!

---

Python 2, 77 bytes

This also modifies the input, but it works....

def f(a):exec'while a and 1>sum(a[-1]):a.pop()\na=zip(*a)[::-1]\n'*4;return a

Try it online!

Answer 12

Wolfram Language (Mathematica), 66 bytes

If[Max@#>0,ImageCrop@Image[#~ArrayPad~1,r="Real"]~ImageData~r,{}]&

Try it online!

Now works by padding the array with zeroes (thanks @JungHwanMin)!

A second thanks to @JungHwanMin for saving 4 bytes

Answer 13

J, 24 bytes

(|.@|:@}.~0=+/@{.)^:4^:_

Try it online!

Explanation

(|.@|:@}.~0=+/@{.)^:4^:_
            +/                sum
              @               of
               {.             the first row
          0=                  is zero? (1 = true, 0 = false)
       }.~                    chop off that many rows from the front
 |.@|:@                       rotate by 90 deg (transpose then reverse)
(                )^:4         repeat this process 4 times (rotating a total of 360 deg)
                     ^:_      fixpoint - repeat until no change

Answer 14

Jelly, 12 bytes

Ṗ§Ṫ¬ȧƲ¿UZµ4¡

Try it online!

As a function.

Answer 15

Wolfram Language (Mathematica), 48 bytes

Nest[Reverse@Thread@#//.{{0..},a___}->{a}&,#,4]&

Try it online!

Doing it the normal way.

Answer 16

Husk, 11 bytes

!5¡(T0mo↔↓¬

Try it online!

I feel like some bytes could be shaved off by shortening the !5¡ part.

How it works

!5¡(

Repeatedly apply the function explained below, collecting the results in an infinite list. Then, retrive the \$5^{\text{th}}\$ element. In other words, apply the function to the input 4 times.

mo↔↓¬

Map over the current version of the input and: reverse each, after having dropped the longest prefix consiting of zeroes only (dropping this prefix is performed by using Husk's ↓, which is a function that crops the longest run of consecutive elements from the beginning of the list that yield truthy results when ran through a function, namely ¬, logical not).

T0

Transpose, replacing missing entries with 0.

Answer 17

Retina, 87 bytes

/.\[(?!0,)/^+`\[0, 
[
/(?<! 0)]./^+`, 0]
]
\[(\[0(, 0)*], )+
[
(, \[0(, 0)*])+]|\[0]]
]

Try it online! Explanation:

/.\[(?!0,)/^+`

Until at least one row doesn't begin with zero...

\[0, 
[

... remove the leading zero from each row.

/(?<! 0)]./^+`

Until at least one row doesn't end with zero...

, 0]
]

... remove the trailing zero from each row.

\[(\[0(, 0)*], )+
[

Remove leading rows of zeros.

(, \[0(, 0)*])+]|\[0]]
]

Remove trailing rows of zeros, or the last remaining zero.

Answer 18

Charcoal, 48 bytes

Ｆ⁴«Ｗ∧θ¬Σ§θ±¹Σ⊟θ¿θ≔⮌Ｅ§θ⁰Ｅ觧θνλθ»⪫[]⪫Ｅθ⪫[]⪫ι, ¦, 

Try it online! Link is to verbose version of code. Includes 15 bytes for formatting. Explanation:

Ｆ⁴«

Repeat 4 times.

Ｗ∧θ¬Σ§θ±¹

Repeat while the array is not empty but its last row sums to zero...

Σ⊟θ

Remove the last row from the array and print a line of the length of its sum, i.e. nothing.

¿θ≔⮌Ｅ§θ⁰Ｅ觧θνλθ»

If the array isn't empty then transpose it.

⪫[]⪫Ｅθ⪫[]⪫ι, ¦, 

Format the array nicely for display. (Standard output would be Ｉθ instead.)

Answer 19

JavaScript, 144 140 129 127 bytes

w=>(t=w=>(q=(s=w=>w.some((r,j)=>r.find(e=>e,i=j))?w.slice(i).reverse():[[]])(s(w)))[0].map((e,j)=>q.map((e,i)=>q[i][j])))(t(w))

140 -> 129 bytes, thanks @Arnauld

Algorithm

• Do twice:
  • Find first non-zero row
  • Slice off preceding rows
  • Reverse
  • Find first non-zero row
  • Slice off preceding rows
  • Reverse
  • Transpose

f = w=>(t=w=>(q=(s=w=>w.some((r,j)=>r.find(e=>e,i=j))?w.slice(i).reverse():[[]])(s(w)))[0].map((e,j)=>q.map((e,i)=>q[i][j])))(t(w));

w1 = [[0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1], [0, 0, 1, 1, 1], [0, 0, 0, 0, 0]];
w2 = [[0, 0, 0, 0], [0, 0, 0, 3], [0, 0, 0, 0], [0, 5, 0, 0], [0, 0, 0, 0]];
w3 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
w4 = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]];

console.log(f(w1).join("\n"));
console.log(f(w2).join("\n"));
console.log(f(w3).join("\n"));
console.log(f(w4));

Answer 20

Python 2, 118 116 bytes

f=lambda a,n=4,s=sum:n and f(zip(*a[max(i for i in range(len(a))if s(s(a[:i],()))<1):][::-1]),n-1)or(s(s(a,()))>0)*a

Try it online!

---

Saved:

• -2 bytes, thanks to shooqie

Answer 21

PHP (>=5.4), 200 194 186 184 bytes

(-6 bytes by returning null instead of empty array)

(-8 bytes thanks to Titus)

(-2 bytes with calling by reference thanks to Titus)

function R(&$a){$m=$n=1e9;foreach($a as$r=>$R)foreach($R as$c=>$C)if($C){$m>$r&&$m=$r;$M>$r||$M=$r;$n>$c&&$n=$c;$N>$c||$N=$c;}for(;$m<=$M;)$o[]=array_slice($a[$m++],$n,$N-$n+1);$a=$o;}

Try it online!

How?

Finds min and max index for rows ($m & $M) and columns ($n & $N) and replaces the input with a sub array from $m,$n to $M,$N (this is a call by reference).

Answer 22

Octave, 48 49 bytes

@(a)sparse(1-min([x y v]=find(a))+x,1-min(y)+y,v)

Try it online!

Find nonzero points and rearrange them in a new sparse matrix.

Answer 23

Ruby, 73 63 bytes

->a{4.times{_,*a=a while a[0]&.sum==0;a=a.reverse.transpose};a}

Try it online!

Edit: simplified, also the previous version crashed for all 0s

How it works:

• do 4 times:
  • remove the first line while there is a first line and it's full of 0s
  • rotate the array clockwise by 90°
• return the array

Answer 24

K (ngn/k), 22 19 bytes

4{+|(+/&\~+/x)_'x}/

Try it online!

Answer 25

Octave, 78 74 bytes

function x=f(x)
for k=1:nnz(~x)*4,x=rot90(x);x=x(:,~~cumsum(any(x,1)));end

Try it online!

Explanation

This rotates the matrix by 90 degrees (x=rot90(x)) a sufficient number of times (for k=1:... end). The number of rotations is a multiple of 4, so the final matrix has the original orientation. Specifically, the number of rotations is 4 times the number of zeros in the matrix (nnz(~x)*4).

For each rotation, if there are one or more columns on the left consisting of only zeros they are removed (x=x(:,~~cumsum(any(x,1)))).

What remains of the matrix after this process is output by the function (function x=f(x)).

Answer 26

Stax, 14 bytes

Ç·W≈y§╗♦º{¬║8•

Run and debug it

Alternative, also 14 bytes

Ç·W≈x≈ƒHq♣☻»íÅ

Run and debug it

Answer 27

PHP, 188 bytes

function f(&$a){for($s=array_shift;!max($a[0]);)$s($a);for($p=array_pop;!max(end($a));)$p($a);for($w=array_walk;!max(($m=array_map)(reset,$a));)$w($a,$s);while(!max($m(end,$a)))$w($a,$p);}

call by reference.

breakdown

// call by reference
function f(&$a)
{
    // while first row is all zeroes, remove it
    while(!max($a[0]))array_shift($a);
    // while last row is all zeroes, remove it
    while(!max(end($a)))array_pop($a);
    // while first column is all zeroes, remove it
    while(!max(array_map(reset,$a)))array_walk($a,array_shift);
    // while last column is all zeroes, remove it
    while(!max(array_map(end,$a)))array_walk($a,array_pop);
}

Answer 28

Clean, 73 bytes

import StdEnv,StdLib
$ =dropWhile(all((>)1))o reverse o transpose

$o$o$o$

Try it online!

Very similar to Laikoni's Haskell answer.

Answer 29

Python 2, 86 bytes

lambda a,l=1:a if l>4else([a.pop()for b in a if sum(a[-1])<1],f(zip(*a[::-1]),l+1))[1]

Try it online!

Takes a list of lists, returns a list of tuples.

Explanation

Abuses the heck out of list comprehension. This is the equivalent expanded code:

def f(a,l=1):
    # after 4 rotations, the list is back in its original orientation, return
    if l > 4:
        return a
    else:
        # helper variable to store return values
        ret = []
        # "trim" all rows from "bottom" of list that only contain 0s
        # since we are always checking le that item in the list, don't need range(len(a))
        # since we are only removing at most one item per iteration, will never try to remove more than len(a) items
        # brackets surrounding generator force it to be consumed make a list, and therefore actually pop() list items
        ret.append([a.pop() for b in a if sum(a[-1]) < 1])
        # rotate the array, increase the number of rotations, and recursively call this function on the new array/counter
        ret.append(f(zip(*a[::-1]), l + 1)))
        # we only put both items in a list in order to stay in the one-line lambda format
        # discard the popped items and return the value from the recursive call
        return ret[1]

Answer 30

Japt -h, 23 11 bytes

4Æ=sUb_dà z

Try it

---

Explanation

                :Implicit input of 2D-array U
4Æ              :Map the range [0,4)
   s            :  Slice U from
    Ub          :   The first index in U where
      _dà      :    Any element is truthy (not zero)
          z     :  Rotate 90 degrees
  =             :  Reassign to U for the next iteration
                :Implicitly output the last element