Is Wally there?

Question

Inpired by recent Stand-up Maths' video.

Task

Wrapping a list x can be seen as inserting "line-breaks" into x every n-th element, or forming a matrix from x with n columns (feeding rows first). To be perfectly rigorous in the definition of x wrapped into a matrix, we can pad the last row with 0s.

Given a list x of positive digits and a matrix M of positive digits, determine whether x can be wrapped into any matrix that contains M as a submatrix. In other words, is there any n such that wrapping x into a matrix of n columns results in a matrix that contains M?

Rules

• Any reasonable input format is acceptable (list, string, array, etc.).
• As for output, please follow the defaults for decision-problem challenges.
• x is guaranteed to be longer than number of elements in M.
• You don't need to handle empty inputs.
• Some wrappings may result in the final line shorter - that's fine.
• This is code-golf, so make your code as short as possible.

Examples

x=1231231
M=23
  31

Possible wrappings:
n>=7
1231231

n=6
123123
1

n=5
12312
31

n=4
1231
231

n=3
123
123
1

n=2
12
31
23
1

n=1
1
2
3
1
2
3
1

Output: True (4th wrapping)

x=1231231
M=23
  32
Possible wrappings: same as above
Output: False (none of the wrappings contain M as submatrix)

Test cases

Truthy

x; M
[1,2,3,1,2,3,1]; [[2,3],[3,1]]
[3,4,5,6,7,8]; [[3,4,5],[6,7,8]]
[3,4,5,6,7,8]; [[3,4],[7,8]]
[1,2,3]; [[1,2,3]]
[1,2,3]; [[1],[2],[3]]
[1,1,2,2,3,3]; [[1],[2],[3]]
[1,1,3,4,5,6]; [[1],[4],[6]]

Falsey

x; M
[1,2,3,1,2,3,1]; [[2,3],[3,2]]
[1,1,2,2,3,3]; [[1,2,3]]
[1,2,3]; [[4,5,6]]
[1,2,3,4,5,6]; [[2,3],[4,5]]

Answer 1

J, 21 bytes

1 e.,@(E."2-@#\]\"{])

Try it online!

Bulk of the work done by E. builtin, which can search for one 2D matrix within another, and even extends to higher dimensions.

• -@#\]\"{] Every possible wrapping.
• E."2 Does the matrix match at each position? (returns 0/1 matrices)
• ,@ Flatten
• 1 e. Is 1 an element of that?

Answer 2

R, 126 121 120 bytes

Edit: -5 bytes thanks to Aaron Hayman

function(x,m,r=nrow(m)){for(o in l<-seq(x)-1)for(s in l+o)T=T&any(c(x,!x,!x)[outer(1:r,(r+s)*(1:ncol(m)-1),`+`)+o]-m)
T}

Try it online!

Outputs TRUE if wally isn't there m is not present in any wrapping of x, FALSE if it is.

Calculates the indices of positions of wally m for each possible offset (the first position in the wrapped matrix) and spacing (the width of the wrapped matrix), and checks that the elements of x at these indices are all equal to m.
To avoid lengthly calculations to keep the indices in-range, we first extend x with enough zeros to cover the biggest o & s: this is the ugly-looking (c(x,!x,!x).

Answer 3

BQN, 24 bytes^SBCS

Generates all possible wrappings and checks if the left argument is a submatrix of one.

{1∊∾(⥊𝕨⍷𝕩⥊˜⟨↑⟩∾1⊸+)¨↕≠𝕩}

Run online!

Answer 4

PARI/GP, 100 bytes

f(a,b)=sum(n=#b,#a,!!matrix(-#a\-n,n-#b+1,x,y,b==matrix(#b~,#b,i,j,if(#a>=k=(x+i-2)*n+y+j-1,a[k]))))

Attempt This Online!

Generates all possible wrappings, and all of their submatrices of the given size, and check if the second argument is one of them.

Answer 5

Desmos, 133 bytes

f(L,M,w)=0^{\sum_{m=1}^K\sum_{X=w}^m\sum_{Y=0}^K\prod_{j=0}^{M.\length-1}\{M[j+1]=L[X+Ym+1-w+\mod(j,w)+\floor(j/w)m],0\}}
K=L.length

• L: list of positive digits (x in question)
• M: matrix, flattened because Desmos doesn't have 2D arrays
• w: width of M

Outputs 0 for truthy and 1 for falsey.

Try it on Desmos!

Answer 6

Charcoal, 31 30 bytes

ＦＥθ⪪θ⊕κＰ⊙ι⊙κ⊙ι⊙ξ⁼ηＥ✂ιλ⊕π¹✂σν⊕ς

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - if it finds Wally, nothing if not. Explanation: Another answer that generates all submatrices of all wrappings.

ＦＥθ⪪θ⊕κ

Generate all wrappings of the list.

Ｐ⊙ι⊙κ⊙ι⊙ξ⁼ηＥ✂ιλ⊕π¹✂σν⊕ς

Check whether the matrix exists as a submatrix.

Unfortunately Charcoal only has 11 loop variables so I can't save a further byte like this:

⊙Ｅθ⪪θ⊕κ⊙ι⊙κ⊙ι⊙ξ⁼ηＥ✂ιλ⊕π¹✂σν⊕ς

Explanation:

  θ                             Input list
 Ｅ                              Map over digits
    θ                           Input list
   ⪪                            Wrapped to width
      κ                         Current index
     ⊕                          Incremented
⊙                               Any wrapping satisfies
        ι                       Current wrapping
       ⊙                        Any row satisfies
          λ                     Current row
         ⊙                      Any column satisifies
            ι                   Current wrapping
           ⊙                    Any row satisfies
              ξ                 Inner row
             ⊙                  Any column satisifies
                η               Input matrix
               ⁼                Equals
                   ι            Current wrapping
                  ✂   ¹         Sliced from
                    μ           Outer row index to
                      π         Inner row index
                     ⊕          Incremented
                 Ｅ              Map over rows
                         σ      Current row
                        ✂       Sliced from
                          ν     Outer column index to
                            ς   Inner column index
                           ⊕    Incremented
                                Implicitly print

Answer 7

05AB1E, 27 21 bytes

.œεεŒIнgù}øεŒIgù€Q]˜à

Try it online or or verify all test cases or try it online with step-by-step debug-lines.

Explanation:

.œ           # Get all partitions of the first (implicit) input-list
  ε          # Map over each partition:
   ε         #  Map over each inner list:
    Π       #   Get all sublists of this list
     I       #   Push the second input-matrix
      н      #   Pop and leave just its first row
       g     #   Pop and push its length to get the width of the matrix
        ù    #   Only leave all sublists of this length, to get all overlapping
             #   parts with a size equal to the width of the input-matrix
   }ø        #  After the inner map: zip/transpose; swapping rows/columns
     ε       #  Map over each list of lists:
      Π     #   Get all sublists of this list
       I     #   Push the second input-matrix again
        g    #   Pop and push its length to get the height of the matrix
         ù   #   Only leave all sublists of this length, to get all matrices
             #   with the same dimensions as the input-matrix
          €  #   Map over each inner matrix:
           Q #    Check if its equal to the second (implicit) input-matrix
  ]          # Close both maps
   ˜         # Flatten
    à        # Get the maximum to check if any were truthy