Count the contiguous submatrices

Question

Migrated from chat

Given two non-empty non-negative integer matrices A and B, answer the number of times A occurs as a contiguous, possibly overlapping, submatrix in B.

Examples/Rules

0. There may not be any submatrices

A:
[[3,1],
[1,4]]

B:
[[1,4],
[3,1]]

Answer:
0

1. Submatrices must be contiguous

A:
[[1,4],
[3,1]]

B:
[[3,1,4,0,5],
[6,3,1,0,4],
[5,6,3,0,1]]

Answer:
1 (marked in bold)

2. Submatrices may overlap

A:
[[1,4],
[3,1]]

B:
[[3,1,4,5],
[6,3,1,4],
[5,6,3,1]]

Answer:
2 (marked in bold and in italic respectively)

3. A (sub)matrix may be size 1-by-1 and up

A:
[[3]]

B:
[[3,1,4,5],
[6,3,1,4],
[5,6,3,1]]

Answer:
3 (marked in bold)

4. Matrices may be any shape

A:
[[3,1,3]]

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

Answer:
4 (two bold, two italic)

Answer 1

Brachylog (v2), 10 bytes

{{s\s\}ᵈ}ᶜ

Try it online!

I like how clear and straightforward this program is in Brachylog; unfortunately, it's not that short byte-wise because the metapredicate syntax takes up three bytes and has to be used twice in this program.

Explanation

{{s\s\}ᵈ}ᶜ
  s         Contiguous subset of rows
   \s\      Contiguous subset of columns (i.e. transpose, subset rows, transpose)
 {    }ᵈ    The operation above transforms the first input to the second input
{       }ᶜ  Count the number of ways in which this is possible

Answer 2

Jelly, 7 bytes

ZẆ$⁺€Ẏċ

Try it online!

How it works

ZẆ$⁺€Ẏċ  Main link. Arguments: B, A

  $      Combine the two links to the left into a monadic chain.
Z          Zip; transpose the matrix.
 Ẇ         Window; yield all contiguous subarrays of rows.
   ⁺     Duplicate the previous link chain.
    €    Map it over the result of applying it to B.
         This generates all contiguous submatrices of B, grouped by the selected
         columns of B.
     Ẏ   Tighten; dump all generated submatrices in a single array.
      ċ  Count the occurrences of A.

Answer 3

MATL, 12 bytes

ZyYC2MX:=XAs

Inputs are A, then B.

Try it online! Or verify all test cases.

Explanation

Consider inputs [1,4; 3 1], [3,1,4,5; 6,3,1,4; 5,6,3,1]. The stack is shown with the most recent element below.

Zy    % Implicit input: A. Push size as a vector of two numbers
      % STACK: [2 2]
YC    % Implicit input: B. Arrange sliding blocks of specified size as columns,
      % in column-major order
      % STACK: [3 6 1 3 4 1;
                6 5 3 6 1 3;
                1 3 4 1 5 4;
                3 6 1 3 4 1]
2M    % Push input to second to last function again; that is, A
      % STACK: [3 6 1 3 4 1;
                6 5 3 6 1 3;
                1 3 4 1 5 4;
                3 6 1 3 4 1],
               [1 4;
                3 1]                    
X:    % Linearize to a column vector, in column-major order
      % STACK: [3 6 1 3 4 1;
                6 5 3 6 1 3;
                1 3 4 1 5 4;
                3 6 1 3 4 1],
               [1;
                3;
                4;
                1]  
=     % Test for equality, element-wise with broadcast
      % STACK: [0 0 1 0 0 1
                0 0 1 0 0 1;
                0 0 1 0 0 1;
                0 0 1 0 0 1]
XA    % True for columns containing all true values
      % STACK: [0 0 1 0 0 1]
s     % Sum. Implicit display
      % STACK: 2

Answer 4

05AB1E, 10 bytes

øŒεøŒI.¢}O

Try it online!

øŒεøŒI.¢}O     Full program. Takes 2 matrices as input. First B, then A.
øŒ             For each column of B, take all its sublists.
  ε     }      And map a function through all those lists of sublists.
   øŒ          Transpose the list and again generate all its sublists.
               This essentially computes all sub-matrices of B.
     I.¢       In the current collection of sub-matrices, count the occurrences of A.
         O     At the end of the loop sum the results.

Answer 5

Dyalog APL, 6 4 bytes

≢∘⍸⍷

This is nearly a builtin (thanks H.PWiz and ngn).

  ⍷       Binary matrix containing locations of left argument in right argument
≢∘⍸       Size of the array of indices of 1s

Alternative non-builtin:

{+/,((*⍺)≡⊢)⌺(⍴⍺)*⍵}

Dyadic function that takes the big array on right and subarray on left.

                  *⍵       exp(⍵), to make ⍵ positive.
    ((*⍺)≡⊢)⌺(⍴⍺)        Stencil;
                            all subarrays of ⍵ (plus some partial subarrays
                            containing 0, which we can ignore)
               ⍴⍺             of same shape as ⍺
     (*⍺)≡⊢                   processed by checking whether they're equal to exp(⍺).
                           Result is a matrix of 0/1.
   ,                     Flatten
 +/                      Sum.

Try it here.

Answer 6

Charcoal, 36 27 bytes

ＩΣ⭆η⭆ι⁼θＥ✂ηκ⁺Ｌθκ¹✂νμ⁺Ｌ§θ⁰μ¹

Try it online! Much shorter now that Equals works for arrays again. Explanation:

   η                        Input array B
  ⭆                         Mapped over rows and joined
     ι                      Current row
    ⭆                       Mapped over columns and joined
       θ                    Input array A
      ⁼                     Is equal to
          η                 Input array B
         ✂                  Sliced
                ¹           All elements from
           κ                Current row index to
             Ｌ              Length of
              θ             Input array A
            ⁺               Plus
               κ            Current row index
        Ｅ                   Mapped over rows
                  ν         Current inner row
                 ✂          Sliced
                          ¹ All elements from
                   μ        Current column index to
                     Ｌ      Length of
                       θ    Input array A
                      §     Indexed by
                        ⁰   Literal 0
                    ⁺       Plus
                         μ  Current column index
 Σ                          Digital sum
Ｉ                           Cast to string
                            Implicitly printed

Answer 7

Clean, 118 97 95 bytes

import StdEnv,Data.List
?x=[transpose y\\z<-tails x,y<-inits z]
$a b=sum[1\\x<- ?b,y<- ?x|y==a]

Try it online!

Answer 8

JavaScript (ES6), 93 bytes

Takes input as (A)(B).

a=>b=>b.map((r,y)=>r.map((_,x)=>s+=!a.some((R,Y)=>R.some((v,X)=>v!=(b[y+Y]||0)[x+X]))),s=0)|s

Try it online!

Answer 9

R, 95 bytes

function(A,B,x=dim(A),D=dim(B)-x){for(i in 0:D)for(j in 0:D[2])F=F+all(B[1:x+i,1:x[2]+j]==A);F}

Try it online!

Answer 10

Python 2, 101 bytes

lambda a,b:sum(a==[l[j:j+len(a[0])]for l in b[i:i+len(a)]]for i,L in e(b)for j,_ in e(L))
e=enumerate

Try it online!

Answer 11

Python 2, 211 bytes

a,b=input()
l,w,L,W,c=len(a),len(a[0]),len(b),len(b[0]),0
for i in range(L):
 for j in range(W):
  if j<=W-w and i<=L-l:
   if not sum([a[x][y]!=b[i+x][j+y]for x in range(l)for y in range(w)]):
    c+=1
print c 

Try it online!

Fairly straightforward. Step through the larger matrix, and check if the smaller matrix can fit.

The only even slightly tricky step is the list comprehension in the 6th line, which relies on Python's conventions for mixing Boolean and integer arithmetic.

Answer 12

Groovy, 109 bytes

{a,b->(0..<b.size()).sum{i->(0..<b[i].size()).count{j->k=i-1
a.every{l=j;k++
it.every{(b[k]?:b)[l++]==it}}}}}

Try it online!

Answer 13

Scala, 151 bytes

(a,b)=>{(0 to b.size-a.size).map(i=>(0 to b(0).size-a(0).size).count(j=>{var k=i-1
a.forall(c=>{var l=j-1;k+=1
c.forall(d=>{l+=1
b(k)(l)==d})})})).sum}

Try it online!