Aus dem Chat migriert

Wenn zwei nicht leere nicht negative Ganzzahlmatrizen A und B gegeben sind , antworten Sie, wie oft A als zusammenhängende, möglicherweise überlappende Untermatrix in B auftritt .

Beispiele / Regeln

0. Es dürfen keine Submatrizen vorhanden sein

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

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

Antworten:
0

1. Untermatrizen müssen zusammenhängend sein

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

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

Antwort:
1(fett markiert)

2. Submatrizen können sich überlappen

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

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

Antwort:
2(fett und kursiv markiert)

3. Eine (Unter-) Matrix kann eine Größe von 1 zu 1 und höher haben

A :
[[3]]

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

Antwort:
3(fett markiert)

4. Matrizen können jede Form haben

A :
[[3,1,3]]

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

Antwort:
4(zwei fett, zwei kursiv)

Brachylog (v2), 10 Bytes

{{s\s\}ᵈ}ᶜ

Probieren Sie es online!

Mir gefällt, wie klar und einfach dieses Programm in Brachylog ist. Leider ist es nicht so kurz byteweise, weil die Metapredicate-Syntax drei Bytes belegt und in diesem Programm zweimal verwendet werden muss.

Erläuterung

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

Gelee , 7 Bytes

ZẆ$⁺€Ẏċ

Probieren Sie es online!

Wie es funktioniert

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.

MATL , 12 Bytes

ZyYC2MX:=XAs

Eingänge A , dann B .

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

Betrachten Sie Eingänge [1,4; 3 1], [3,1,4,5; 6,3,1,4; 5,6,3,1]. Der Stapel wird mit dem aktuellsten Element unten angezeigt.

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

05AB1E , 10 Bytes

øŒεøŒI.¢}O

Probieren Sie es 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.

Dyalog APL, 6 4 Bytes

≢∘⍸⍷

Dies ist fast ein eingebautes (danke H.PWiz und ngn ).

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

Alternative nicht eingebaut:

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

Dyadische Funktion, die das große Array rechts und das Subarray links aufnimmt.

                  *⍵       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.

Probieren Sie es hier aus .

JavaScript (ES6), 93 Byte

Übernimmt die Eingabe als (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

Probieren Sie es online!

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}

Probieren Sie es online!

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

Probieren Sie es 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

Probieren Sie es online!

Kohle , 36 27 Bytes

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

Probieren Sie es online! Viel kürzer jetzt, da Equals wieder für Arrays funktioniert. Erläuterung:

   η                        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 

Probieren Sie es online!

Ziemliech direkt. Gehen Sie die größere Matrix durch und prüfen Sie, ob die kleinere Matrix passt.

Der einzige noch etwas knifflige Schritt ist das Listenverständnis in der 6. Zeile, das sich auf Pythons Konventionen zum Mischen von Boolescher und ganzzahliger Arithmetik stützt.

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

Probieren Sie es 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}

Probieren Sie es online!