21
1
This is the 2-dimensional generalisation of this challenge.
For our purposes, one matrix (or 2D array) A is considered a submatrix of another matrix B, if A can be obtained by completely removing a number of rows and columns from B. (Note: some sources have different/more restrictive definitions.)
Here's an example:
A = [1 4 B = [1 2 3 4 5 6
2 1] 6 5 4 3 2 1
2 1 2 1 2 1
9 1 8 2 7 6]
We can delete columns 2, 3, 5, 6 and rows 2, 4 from B to obtain A:
B = [1 2 3 4 5 6 [1 _ _ 4 _ _ [1 4 = A
6 5 4 3 2 1 --> _ _ _ _ _ _ --> 2 1]
2 1 2 1 2 1 2 _ _ 1 _ _
9 1 8 2 7 6] _ _ _ _ _ _]
Note that A is still a submatrix of B if all rows or all columns of B are retained (or in fact if A = B).
The Challenge
You guessed it. Given two non-empty integer matrices A and B, determine if A is a submatrix of B.
You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.
Input may be in any convenient format. The matrices can be given as nested lists, strings using two different separators, flat lists along with the dimensions of the matrix, etc, as long as the input is not pre-processed. You may choose to take B first and A second, as long as your choice is consistent. You may assume that the elements of the matrices are positive and less then 256.
Output should be truthy if A is a submatrix of B and falsy otherwise. The specific output value does not have to be consistent.
Standard code-golf rules apply.
Test Cases
Each test case is on a separate line, A, B
.
Truthy cases:
[[1]], [[1]]
[[149, 221]], [[177, 149, 44, 221]]
[[1, 1, 2], [1, 2, 2]], [[1, 1, 1, 2, 2, 2], [3, 1, 3, 2, 3, 2], [1, 1, 2, 2, 2, 2]]
[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[1, 2, 3], [4, 7, 6], [7, 8, 9], [1, 2, 3], [4, 5, 6], [7, 8, 9]]
[[228, 66], [58, 228]], [[228, 66], [58, 228]]
[[1, 2], [2, 1]], [[1, 2, 2], [2, 1, 2], [2, 2, 1]]
[[136, 196], [252, 136]], [[136, 252, 210, 196, 79, 222], [222, 79, 196, 210, 252, 136], [252, 136, 252, 136, 252, 136], [180, 136, 56, 252, 158, 222]]
Falsy cases:
[[1]], [[2]]
[[224, 15]], [[144, 15, 12, 224]]
[[41], [150]], [[20, 41, 197, 150]]
[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[1, 2, 3], [7, 8, 9], [4, 5, 6]]
[[1, 2, 2], [2, 1, 2], [2, 2, 1]], [[1, 2], [2, 1]]
[[1, 2, 2], [2, 1, 2]], [[1, 2], [2, 1], [2, 2]]
[[1, 2], [3, 4]], [[5, 3, 4, 5], [2, 5, 5, 1], [4, 5, 5, 3], [5, 1, 2, 5]]
[[158, 112], [211, 211]], [[158, 211, 189, 112, 73, 8], [8, 73, 112, 189, 211, 158], [211, 158, 211, 158, 211, 158], [21, 158, 199, 211, 212, 8]]
11I suppose this is a single character in Jelly. – Adám – 2016-03-09T19:11:43.480
@Nᴮᶻ not in APL too? :P – Rɪᴋᴇʀ – 2016-03-10T03:42:53.053
@RikerW No, APL only has these and these single character "solutions", while Jelly keeps surprising us with new single character primitives, including most of the leftmost column here...
– Adám – 2016-03-10T13:01:45.177