# Is Wally there?

Inpired by recent Stand-up Maths' video.

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.).
• 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 , 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,1,2,2,3,3]; [,,]
[1,1,3,4,5,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]]

• Suggested truthy test case: [1,1,3,4,5,6]; [,,]. (That will not work if the code just checks that the positions of 4 in [3,4] and 6 in [5,6] are the same as the position of the first 1 in [1,1].) May 5 at 10:56
• Suggested falsey test case: [1,2,3,4,5,6]; [[2,3],[4,5]]. May 5 at 11:04
• @KevinCruijssen - the rows of the wrappings are left-aligned. The case you describe wraps once between 6 and 7, and the new second row is just [7,8], underneath [3,4] (it's not a full row). May 5 at 15:26
• @DominicvanEssen Ah, I'm an idiot.. I've been using ä instead of ô in the program I had linked in my now deleted comment.. :/ Ignore what I said. (I've actually been able to find a slightly shorter approach, and have posted my answer. And I've deleted my comment above to reduce potential confusion, since I was just blind.) May 5 at 20:23
• I'm beginning to think Matt Parker needs his own tag here, given the number of challenges inspired by his videos. (I wonder if he's aware of this?) May 6 at 13:58

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

# R, 126121 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).

• Can shave off 5 by removing if and a couple of refinements Try it online! May 6 at 9:13
• @AaronHayman Thanks! Those are both really nice golfs! I don't think I'd realised that one can assign using <- within the for() bit. Nice. May 6 at 9:36
• @AaronHayman - and removing the if also lets us save another byte by reversing the output. Thanks again! May 6 at 9:53

# BQN, 24 bytesSBCS

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

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


Run online!

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

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

• You dont need the outer 0^{...}, because as long as it's truthy or falsy, it's fine May 5 at 15:48
• You can emit the first newline if you put the K=L.length before the f(...)=... May 5 at 20:22
• @Steffan the language has no convention for truthy/falsy as required by the decision-problem tag default; the only construction that can be used for list filters and the condition in piecewises is the direct result of numeric comparisons: =, > etc. May 5 at 21:15
• @Steffan Omitting the first newline doesn't work for me. As I understand it, when scoring Desmos equations, newlines typically denote "file boundaries," which means copy-paste each line separately excluding the surrounding newlines. Copying the newline before the f is not allowed because the newline would then double as a file boundary character. May 5 at 21:20

# 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


# 05AB1E, 27 21 bytes

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


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