# Count the contiguous submatrices

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

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

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

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

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

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

3 (marked in bold)

### 4. Matrices may be any shape

A:
[[3,1,3]]

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

4 (two bold, two italic)

# 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

Try it online!

# 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!

# 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

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

# 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!

# 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!