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
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)
code-golf array-manipulation matrix search
add a comment |
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)
code-golf array-manipulation matrix search
2
Are the A matrices always square matrices, or is it coincidence that they are in all test cases?
– BMO
21 mins ago
add a comment |
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)
code-golf array-manipulation matrix search
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)
code-golf array-manipulation matrix search
code-golf array-manipulation matrix search
asked 2 hours ago
Adám
28.7k269188
28.7k269188
2
Are the A matrices always square matrices, or is it coincidence that they are in all test cases?
– BMO
21 mins ago
add a comment |
2
Are the A matrices always square matrices, or is it coincidence that they are in all test cases?
– BMO
21 mins ago
2
2
Are the A matrices always square matrices, or is it coincidence that they are in all test cases?
– BMO
21 mins ago
Are the A matrices always square matrices, or is it coincidence that they are in all test cases?
– BMO
21 mins ago
add a comment |
2 Answers
2
active
oldest
votes
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
add a comment |
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.
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "200"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f178173%2fcount-the-contiguous-submatrices%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
add a comment |
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
add a comment |
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
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
edited 1 hour ago
answered 1 hour ago
Luis Mendo
74k886291
74k886291
add a comment |
add a comment |
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.
add a comment |
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.
add a comment |
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.
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.
edited 37 mins ago
answered 43 mins ago
Dennis♦
186k32296735
186k32296735
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f178173%2fcount-the-contiguous-submatrices%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
Are the A matrices always square matrices, or is it coincidence that they are in all test cases?
– BMO
21 mins ago