12
\$\begingroup\$

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 , 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]]
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Suggested truthy test case: [1,1,3,4,5,6]; [[1],[4],[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].) \$\endgroup\$
    – Arnauld
    May 5 at 10:56
  • 2
    \$\begingroup\$ Suggested falsey test case: [1,2,3,4,5,6]; [[2,3],[4,5]]. \$\endgroup\$
    – alephalpha
    May 5 at 11:04
  • 3
    \$\begingroup\$ @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). \$\endgroup\$ May 5 at 15:26
  • \$\begingroup\$ @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.) \$\endgroup\$ May 5 at 20:23
  • 2
    \$\begingroup\$ 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?) \$\endgroup\$ May 6 at 13:58

7 Answers 7

4
\$\begingroup\$

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?
\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ Can shave off 5 by removing if and a couple of refinements Try it online! \$\endgroup\$ May 6 at 9:13
  • \$\begingroup\$ @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. \$\endgroup\$ May 6 at 9:36
  • 1
    \$\begingroup\$ @AaronHayman - and removing the if also lets us save another byte by reversing the output. Thanks again! \$\endgroup\$ May 6 at 9:53
3
\$\begingroup\$

BQN, 24 bytesSBCS

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

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

Run online!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
4
  • \$\begingroup\$ You dont need the outer 0^{...}, because as long as it's truthy or falsy, it's fine \$\endgroup\$
    – Steffan
    May 5 at 15:48
  • \$\begingroup\$ You can emit the first newline if you put the K=L.length before the f(...)=... \$\endgroup\$
    – Steffan
    May 5 at 20:22
  • \$\begingroup\$ @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. \$\endgroup\$ May 5 at 21:15
  • \$\begingroup\$ @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. \$\endgroup\$ May 5 at 21:20
1
\$\begingroup\$

Charcoal, 31 30 bytes

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

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.

FEθ⪪θ⊕κ

Generate all wrappings of the list.

P⊙ι⊙κ⊙ι⊙ξ⁼ηE✂ιλ⊕π¹✂σν⊕ς

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:

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

Explanation:

  θ                             Input list
 E                              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
                 E              Map over rows
                         σ      Current row
                        ✂       Sliced from
                          ν     Outer column index to
                            ς   Inner column index
                           ⊕    Incremented
                                Implicitly print
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.