15
\$\begingroup\$

Given a multi-dimensional rectangular array of non-negative integers, pad it with the minimal number of zeroes so that only zeroes are "touching the edges" of the array, in every dimension.

The output must remain rectangular, have the same number of dimensions as the input, and be no smaller than the input.

Example

For the input:

[[1, 3, 0],
 [2, 6, 7],
 [4, 0, 2],
 [0, 0, 0]]

Here is the array again with the elements which are "touching the edge" highlighted:

[[1, 3, 0],
 [2, 6, 7],
 [4, 0, 2],
 [0, 0, 0]]

The expected output is:

[[0, 0, 0, 0, 0],
 [0, 1, 3, 0, 0],
 [0, 2, 6, 7, 0],
 [0, 4, 0, 2, 0],
 [0, 0, 0, 0, 0]]

Notice that:

  • In the first row, even though there was already a zero on the right, we still had to add an extra zero on the right to keep the array properly rectangular
  • The bottom row was already all zeroes, so no extra row needed to be added there

For the 1-dimensional array [3, 4, 9, 0, 0], the edges are [3, 4, 9, 0, 0].


For this 3-dimensional array:

[[[4, 0, 4, 1],
  [0, 0, 5, 8],
  [6, 0, 0, 0],
  [0, 3, 7, 0]],

 [[4, 9, 8, 5],
  [0, 6, 4, 0],
  [0, 0, 0, 3],
  [0, 9, 6, 1]],

 [[0, 4, 7, 9],
  [0, 2, 0, 6],
  [0, 0, 0, 0],
  [7, 0, 3, 0]],

 [[0, 5, 3, 5],
  [0, 0, 0, 0],
  [6, 5, 3, 0],
  [4, 6, 0, 8]]]

the edges are:

[[[4, 0, 4, 1],
  [0, 0, 5, 8],
  [6, 0, 0, 0],
  [0, 3, 7, 0]],

 [[4, 9, 8, 5],
  [0, 6, 4, 0],
  [0, 0, 0, 3],
  [0, 9, 6, 1]],

 [[0, 4, 7, 9],
  [0, 2, 0, 6],
  [0, 0, 0, 0],
  [7, 0, 3, 0]],

 [[0, 5, 3, 5],
  [0, 0, 0, 0],
  [6, 5, 3, 0],
  [4, 6, 0, 8]]]

Imagine each inner 2-dimensional array as a cross-section of a 3-dimensional box. The only elements which are not touching the edges are the ones on the inside of the box.

Specification

"Touching the edges" is a hopefully fairly intuitive concept, but here is a specification:

Let's use the same example input array as above; its shape is 4, 3.

Using one-based indexing, we can index any element of the array using two integers in the ranges \$ [1, 4] \$ and \$ [1, 3] \$.

The elements which are touching the edge are those with coordinates of the form 1, y, 4, y, x, 1, or x, 3.

So, formally, we can say, for an element to be "touching the edge", at least one part of its multidimensional indices is either 1 (the minimum possible coordinate), or the maximum possible coordinate (which is the size of the array in the respective dimension).

Rules

Test cases

Input Output
[[[0]]]
[[[0]]]
[[1]]
[[0, 0, 0],
[0, 1, 0],
[0, 0, 0]]
[3, 4, 9, 0, 0]
[0, 3, 4, 9, 0, 0]
[[1, 3, 0],
[2, 6, 7],
[4, 0, 2],
[0, 0, 0]]
[[0, 0, 0, 0, 0],
[0, 1, 3, 0, 0],
[0, 2, 6, 7, 0],
[0, 4, 0, 2, 0],
[0, 0, 0, 0, 0]]
[[1, 0],
[0, 4]]
[[0, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 4, 0],
[0, 0, 0, 0]]
[[[[0, 0],
[1, 3]],

[[0, 6],
[0, 5]]],


[[[0, 0],
[0, 0]],

[[1, 0],
[2, 0]]]]
[[[[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]],

[[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]],

[[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]],

[[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]],


[[[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]],

[[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 1, 3, 0],
[0, 0, 0, 0]],

[[0, 0, 0, 0],
[0, 0, 6, 0],
[0, 0, 5, 0],
[0, 0, 0, 0]],

[[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]],


[[[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]],

[[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]],

[[0, 0, 0, 0],
[0, 1, 0, 0],
[0, 2, 0, 0],
[0, 0, 0, 0]],

[[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]],


[[[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]],

[[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]],

[[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]],

[[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]]]
\$\endgroup\$
8
  • 1
    \$\begingroup\$ Can we crop? E.g. [0,0,1,0] -> [0,1,0] instead of [0,0,1,0] \$\endgroup\$
    – Jitse
    Jun 13 at 12:28
  • 1
    \$\begingroup\$ @Jitse No, output must be at least as big as the input. \$\endgroup\$
    – pxeger
    Jun 13 at 12:29
  • 1
    \$\begingroup\$ Must we handle 4d and higher too? \$\endgroup\$
    – Jonah
    Jun 13 at 12:59
  • 1
    \$\begingroup\$ @Jonah Yes, your algorithm must work in theory for any number of dimensions, although it's fine if it's constrained by your language in practice \$\endgroup\$
    – pxeger
    Jun 13 at 13:00
  • 4
    \$\begingroup\$ Good, I think that's the interesting part. I also like the idea of the simpler challenge "list all the sides of a cube in of any dimension". \$\endgroup\$
    – Jonah
    Jun 13 at 13:07

5 Answers 5

11
\$\begingroup\$

BQN, 24 bytes

(0×⊏)⊸∾⍟(0⊸×⊸≢⊏)∘⌽⍟2∘⍉⍟=

Try it!

Explanation

(0×⊏)⊸∾⍟(0⊸×⊸≢⊏)∘⌽⍟2∘⍉⍟=
                         ⍟=  Given an N-dimensional array, do this N times:
                       ∘⍉     Rotate the array's indices (N-dimensional transpose), then
                     ⍟2       Do this twice:
                  ∘⌽           Reverse the array along its first axis, then
        ⍟                      Do X times
         (       )              where X is:
                ⊏               Take the first cell of the array
             ⊸≢                 and return 1 if it is different from
          0⊸×                   itself multiplied by zero
                               (thus, do iff the first cell is not all zeros):
     ⊸∾                         Join to the beginning of the array
(0×⊏)                           the first cell of the array multiplied by zero
\$\endgroup\$
5
\$\begingroup\$

Python NumPy, 95 bytes

lambda*a:pad(*a,[((a:=any(a,0)+0)[0].max(),a[-1].max())for _ in a[0].shape])
from numpy import*

Attempt This Online!

\$\endgroup\$
4
\$\begingroup\$

Wolfram Language (Mathematica), 71 bytes

#~ArrayPad~Sign@Table[Max/@Transpose[#,i<->1][[{1,-1}]],{i,Depth@#-1}]&

Try it online!

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

R, (was 296) 292 bytes

\(x,d=dim(x),n=length(d),a=array,e=seq(!d),m=e%%n+1,p=\(x)aperm(x,m),s=\(x,u)do.call(`[`,c(list(x),u)),u=lapply(d,\(x)quote(expr=)),r=\(x,y,z){l=dim(z);l[n]=l[n]+1;array(c(x,y),l)}){for(i in e){x=p(x);d=d[m];u[[n]]=d[n];k=s(x,u);if(any(k))x=r(x,k*0,x);u[[n]]=1;if(any(s(x,u)))x=r(k*0,x,x)};x}

Attempt This Online!

Similar to the package approach, but R arrays are stored last-dimension-first so we loop through permuting the array each time so we're considering the last dimension, then add faces where needed. Now just using base R and it works in ATO.

R+abind+rlang, 220 bytes

\(x,d=dim(x),b=\(y,z,d)abind::abind(y,z,along=d),s=\(x,u)do.call(`[`,c(list(x),u)),m=lapply(d,\(x)rlang::expr())){for(i in 1:length(d)){u=m;u[i]=d[i];g=s(x,u);if(any(g))x=b(x,g*0,i);u[i]=1;if(any(s(x,u)))x=b(g*0,x,i)};x}

Attempt This Online!

Basically loop through the dimensions and add on slices where appropriate after checking the final slice then initial slice. For loop has to use 1:length(d) rather than seq(d) in case d is a scalar.

Doesn't work in ATO but does work in rdrr.io with the following:

test1=array(c(0), dim=1)
test2=array(c(1), dim=c(1,1))
test3=array(c(3,4,9,0,0), dim = 5)
test4=array(c(1,3,0,2,6,7,4,0,2,0,0,0), dim = c(3,4))
test5=array(c(1,0,0,4), dim = c(2,2))
test6=array(c(0,0,1,3,0,6,0,5,0,0,0,0,1,0,2,0), dim = c(2,2,4))

f=function(x,d=dim(x),b=function(y,z,d)abind::abind(y,z,along=d),s=function(x,u)do.call(`[`,c(list(x),u)),m=lapply(d,function(x)rlang::expr())){for(i in 1:length(d)){u=m;u[i]=d[i];g=s(x,u);if(any(g))x=b(x,g*0,i);u[i]=1;if(any(s(x,u)))x=b(g*0,x,i)};x}

f(test1)
f(test2)
f(test3)
f(test4)
f(test5)
f(test6)
\$\endgroup\$
4
  • 1
    \$\begingroup\$ This is technically R+abind+rlang as those packages aren't present in the standard R distribution. \$\endgroup\$
    – pajonk
    Jun 14 at 6:06
  • \$\begingroup\$ See also Tips for golfing in R, as there may be some hints how to shorten your code (e.g. 1:length(d) -> seq(!d)). \$\endgroup\$
    – pajonk
    Jun 14 at 6:08
  • \$\begingroup\$ Updated with the base R solution. \$\endgroup\$
    – Cong Chen
    Jun 14 at 12:58
  • \$\begingroup\$ Technically I don't think it's necessary to reinitialise v each run of the loop, so could modify u directly. \$\endgroup\$
    – Cong Chen
    Jun 15 at 7:52
1
\$\begingroup\$

Python3, 408 bytes:

lambda a:[(a:=f(a,a,i))for i in[*range(D(a))][::-1]][-1]
I=lambda x:int==type(x)
S=lambda x:x if I(x)else sum(map(S,x))
K=lambda x,e,d,l=0:S(x[e])if d==l else any(K(i,e,d,l+1)for i in x)
B=lambda x:0 if I(x)else[B(i)for i in x]
U=lambda o,a,d:[B(a[0])]*(K(o,0,d)>0)+a+[B(a[0])]*(K(o,-1,d)>0)
D=lambda x,l=0:l if I(x)else max(D(i,l+1)for i in x)
f=lambda o,a,d,l=0:U(o,a,d)if d==l else[f(o,i,d,l+1)for i in a]

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ A low-hanging improvement is that instead of S(x[e])if d==l else ... you can do ...if d-l else S(x[e]). \$\endgroup\$
    – newbie
    Jun 13 at 21:50
  • \$\begingroup\$ Also you can do (1-I(x))and... instead of 0 if I(x)else... \$\endgroup\$
    – newbie
    Jun 13 at 21:52
  • \$\begingroup\$ You only use U once, so you can just replace the U(o,a,d) in f with [B(a[0])]*(K(o,0,d)>0)+a+[B(a[0])]*(K(o,-1,d)>0) to get rid of \nU=lambda o,a,d:. \$\endgroup\$ Jun 14 at 6:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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