Remove submatrices

Question

Given two integer matrices a and b, your challenge is to replace any occurences of b in a with a matrix of the same size filled with 0s. For example:

Given:
a: [ [1, 2, 3],
     [4, 3, 2],
     [3, 5, 4] ]
b: [ [3],
     [2] ]
b occurs once in a:
[ [1, 2, 3],
  [4, 3, 2],
  [3, 5, 4] ]
Fill that area with zeroes:
[ [1, 2, 0],
  [4, 3, 0],
  [3, 5, 4] ]
And this is your result!

You can assume occurences of b will never overlap, but there may be none. b will never be larger than a, or empty, and will only contain positive integers.

Testcases

[ [1, 2],
  [3, 4] ]
[ [1] ]
=>
[ [0 2],
  [3 4] ]

[ [4, 4, 6, 7],
  [4, 2, 4, 4],
  [7, 3, 4, 2] ]
[ [4, 4],
  [4, 2] ]
=>
[ [0, 0, 6, 7],
  [0, 0, 0, 0],
  [7, 3, 0, 0] ]

[ [1, 2] ]
[ [3, 4] ]
=>
[ [1, 2] ]

[ [1, 2],
  [3, 4] ]
[ [1, 2],
  [3, 4] ]
=>
[ [0, 0],
  [0, 0] ]

[ [1, 2],
  [2, 1] ]
[ [1],
  [2] ]
=>
[ [0, 2],
  [0, 1] ]
(suggested by tsh)

[ [2, 3, 4],
  [3, 2, 3],
  [4, 3, 2] ]
[ [2, 3],
  [3, 2] ]
=>
Undefined behaviour, will not be given (overlap)  

Answer 1

APL (Dyalog Unicode), 20 bytes

Anonymous infix lambda taking a and b as left and right argument. Requires 0-based indexing.

{0@((⍳⍴⍵)∘.+⍸⍵⍷⍺)⊢⍺}

Try it online!

{…} dfn; arguments are ⍺ and ⍵:

 ⊢⍺ on a,

 0@(…) put zeros at the following positions

  ⍵⍷⍺ indicate (Boolean matrix) locations b begins (top left corner) in a

  ⍸ indices where (list of 2-element lists) those locations are

  (…)∘.+ all summation combinations (gives 3D array of 2-element lists) with:

   ⍴⍵ the shape of b

   ⍳ all the indices of an array with that shape

Answer 2

MATLAB/Octave with Image Processing Toolbox/Package, 78 bytes

@(A,B)A.*~conv2(reshape(all(im2col(A,size(B))==B(:),1),size(A)-size(B)+1),B>0)

Try it online!

Explanation

Consider the example

A = [1 2 3
     4 3 2
     3 5 4]
B = [3
     2]

im2col(A,size(B)) takes sliding blocks of A with the size of B and arranges them as columns:

1   4   2   3   3   2
4   3   3   5   2   4

...==B(:) takes each column in the above matrix and compares it element-wise with B(:), which is B linearized into a column vector:

0   0   0   0   1   0
0   0   0   0   1   0

all(...,1)gives 1 for columns that only contain nonzeros:

0   0   0   0   1   0

reshape(...,size(A)-size(B)+1) arranges the results as a matrix, so each position corresponds to one of the original blocks in A. This matrix is smaller than A, depending on the block size:

0   0   1
0   0   0

conv2(...,B>0) gives the 2D convolution between the above matrix and a matrix of ones the same size as B. This has the effect of extending the matrix size to that of A, and enlarging each 1 above to a "patch" the same size as B:

0   0   1
0   0   1
0   0   0

A.*~... multiplies A element-wise by the above matrix negated, which acts as a mask that sets the desired entries to 0:

1   2   0
4   3   0
3   5   4

Answer 3

J, ²⁹ 27 bytes

]*1-[:+/-@,/@(#:i.)@$@[|.E.

Try it online!

It took me a while to see this approach.

At first, the problem seems easy, because J has E., which immediately finds the matches by returning a 0-1 matrix with a 1 marking the upper left corner of any match. For example:

   (,.1 4) E. i.2 3
0 1 0
0 0 0

locates 1  within 0 1 2
        4         3 4 5

In a sense the "hard work" is done, yet going from there to updating squares of the same size as our search target is surprisingly cumbersome.

The trick is to rotate "across" the search target dimension, and then "sum the planes", similar to how we find neighbor counts in the famous APL game of life.

Finally, we multiply the original matrix by the inverse of that result, putting zeros where the ones are and keeping everything else.

The rest is just implementation mechanics.

Answer 4

JavaScript (Node.js), 121 bytes

a=>b=>a.map((r,y)=>r.map((c,x)=>c*!b.some((R,Y)=>R.some((C,X)=>!b.some((S,Z)=>S.some((D,W)=>(a[y-Y+Z]||0)[x-X+W]!=D))))))

Try it online!

Answer 5

Charcoal, 55 50 bytes

ＦＬθＦＬ§θιＦ⁼ηＥ✂θι⁺ιＬη¹✂λκ⁺κＬ§η⁰ＦＬηＦＬ§η⁰§≔§θ⁺ιμ⁺κν⁰Ｉθ

Try it online! Link is to verbose version of code. Explanation:

ＦＬθＦＬ§θι

Loop over the cells of a. (The ones that are too low or to the right won't slice properly below so the resulting submatrix will never equal b.)

Ｆ⁼ηＥ✂θι⁺ιＬη¹✂λκ⁺κＬ§η⁰

If this submatrix of a equals b...

ＦＬηＦＬ§η⁰§≔§θ⁺ιμ⁺κν⁰

... then set all of its elements to zero.

Ｉθ

Output the final matrix.

I tried directly mapping over the matrix and filtering out the values that were part of a submatrix but unfortunately this is a) longer at 68 bytes and b) requires 12 loop variables, when Charcoal only has 11 (iklmnxprvst).

Answer 6

R, 115 111 bytes

(or 97 bytes in R≥4.1 by replacing the two instances of function with \)

function(a,b,`~`=which){apply(array(,dim(a)-dim(b)+1)|1~T,1,function(c)if(a[d<-t(c+t(b|1~T))-1]==b)a[d]<<-0);a}

Try it online!

Answer 7

Ruby, 128 bytes

->a,b{w=b[0].size;a.size.times{|r|a[r].size.times{|c|a[r,q=b.size].map{|z|z[c,w]}==b&&q.times{|x|w.times{|y|a[r+x][c+y]=0}}}};a}

Try it online!

Answer 8

Matlab, 153 bytes

c=size(a);
d=size(b);
e=c(1);
f=c(2);
g=d(1);
h=d(2);
for i=1:e-g+1
for j=1:f-h+1
if all(a(i:i+g-1,j:j+h-1)==b,'all')
a(i:i+g-1,j:j+h-1)=0;
end
end
end
a

I'm a bit frustrated that I wasn't able to find a vectorized solution, which would be more fitting for a Matlab solution.

Answer 9

JavaScript (ES6),  114  110 bytes

Expects (matrix)(submatrix).

m=>s=>m.map((r,y)=>r.map((v,x)=>(g=e=>+s.some((R,Y)=>R.some((V,X)=>eval("(m[y+Y]||0)[x+X]"+e))))`^V`?v:g`=0`))

Try it online!

How?

Let \$M\$ be the parent matrix and \$S\$ be the submatrix.

Given an expression \$e\$ and a reference position \$(x,y)\$ in \$M\$, the helper function \$g\$ walks through all cells \$(X,Y)\$ of \$S\$ and applies \$e\$ to the cell \$(x+X,y+Y)\$ in \$M\$. It eventually returns \$1\$ if any result is \$\neq 0\$, or \$0\$ otherwise.

g = e =>
  +s.some((R, Y) =>
    R.some((V, X) =>
      eval("(m[y+Y]||0)[x+X]" + e)
    )
  )

We first invoke \$g\$ with the expression "^V" to test whether the submatrix at \$(x,y)\$ in \$M\$ is equal to \$S\$. If it is, we invoke \$g\$ a second time with the expression "=0" to clear the submatrix.

Answer 10

Core Maude, 310 bytes

in linear
mod R is pr INT-MATRIX *(sort IntMatrix to M). op r : M M -> M . op t : Int
Int M M -> Int . var A B C D E : Int . var W X Y Z : M . ceq r((A,B)|-> E ;
X ; Y,Z)= r(Y,Z)if(C,D)|-> E ; W := Z /\ t(A - C,B - D,X,W)=/= 0 . eq r(X,Y)=
X[owise]. ceq t(A,B,X,(C,D)|-> E ; Y)= 0 if X[A + C,B + D]=/= E . endm

The result is obtained by reducing the r function with the input and pattern matrices, given as IntMatrixes, and the output is an IntMatrix.

This solution requires that all of the input matrices' entries be non-zero, due to a quirk of IntMatrixes: zero entries are omitted in the representation (since zero is the default). This is also true for the output.

Example Session

Maude> red r(
>     (0, 0) |-> 1 ; (0, 1) |-> 2 ; (0, 2) |-> 3 ;
>     (1, 0) |-> 4 ; (1, 1) |-> 3 ; (1, 2) |-> 2 ;
>     (2, 0) |-> 3 ; (2, 1) |-> 5 ; (2, 2) |-> 4,
>     (0, 0) |-> 3 ;
>     (1, 0) |-> 2
> ) .
result M: 0,0 |-> 1 ; 0,1 |-> 2 ; 1,0 |-> 4 ; 1,1 |-> 3 ; 2,0 |-> 3 ; 2,1 |-> 5
    ; 2,2 |-> 4
Maude> red r(
>     (0, 0) |-> 1 ; (0, 1) |-> 2 ;
>     (1, 0) |-> 3 ; (1, 1) |-> 4,
>     (0, 0) |-> 1
> ) .
result M: 0,1 |-> 2 ; 1,0 |-> 3 ; 1,1 |-> 4
Maude> red r(
>     (0, 0) |-> 4 ; (0, 1) |-> 4 ; (0, 2) |-> 6 ; (0, 3) |-> 7 ;
>     (1, 0) |-> 4 ; (1, 1) |-> 2 ; (1, 2) |-> 4 ; (1, 3) |-> 4 ;
>     (2, 0) |-> 7 ; (2, 1) |-> 3 ; (2, 2) |-> 4 ; (2, 3) |-> 2 ,
>     (0, 0) |-> 4 ; (0, 1) |-> 4 ;
>     (1, 0) |-> 4 ; (1, 1) |-> 2
> ) .
result M: 0,2 |-> 6 ; 0,3 |-> 7 ; 2,0 |-> 7 ; 2,1 |-> 3
Maude> red r(
>     (0, 0) |-> 1 ; (0, 1) |-> 2,
>     (0, 0) |-> 3 ; (0, 1) |-> 4
> ) .
result M: 0,0 |-> 1 ; 0,1 |-> 2
Maude> red r(
>     (0, 0) |-> 1 ; (0, 1) |-> 2 ;
>     (1, 0) |-> 3 ; (1, 1) |-> 4,
>     (0, 0) |-> 1 ; (0, 1) |-> 2 ;
>     (1, 0) |-> 3 ; (1, 1) |-> 4
> ) .
result M: zeroMatrix
Maude> red r(
>     (0, 0) |-> 1 ; (0, 1) |-> 2 ;
>     (1, 0) |-> 2 ; (1, 1) |-> 1,
>     (0, 0) |-> 1 ;
>     (1, 0) |-> 2
> ) .
result M: 0,1 |-> 2 ; 1,1 |-> 1

Ungolfed

in linear

mod R is
    pr INT-MATRIX * (sort IntMatrix to M) .

    op r : M M -> M .
    op t : Int Int M M -> Int .

    var A B C D E : Int .
    var W X Y Z : M .

    ceq r((A, B) |-> E ; X ; Y, Z) = r(Y, Z)
        if (C, D) |-> E ; W := Z
        /\ t(A - C, B - D, X, W) =/= 0 .
    eq r(X, Y) = X [owise] .

    ceq t(A, B, X, (C, D) |-> E ; Y) = 0
        if X[A + C, B + D] =/= E .
endm

We find an overlap by guess-and-check. We guess a submatrix and pick one entry from the submatrix and one from the pattern with the same value. We compute their offset and then try to find a counter-example to the match (via t). If none exists, we remove the submatrix (equivalent to setting it to zero).