Smallest slice of array containing a number of items

Question

Take this array:

[1, 2, 6, 4, 4, 1, 0, 0, 2, 0, 4, 1, 4, 2, 4, 8, 1, 2, 4]

There are quite a few places where [1, ..., 2, ..., 4] appears, where ... is any number of items. These include [1, 2, 6, 4], [1, 0, 0, 2, 0, 4], [1, 0, 0, 2, 0, 4, 1, 4], and [1, 2, 4]. The shortest of these is simply [1, 2, 4].

Task:

Given two arrays of any (reasonable) data type you choose, find the shortest slice of the first which contains all items in the second in order. There is guaranteed to be at least one such slice.

If there are multiple, you may return any one of them. Neither array will be empty. Duplicate items may appear in the second list.

Test cases:

[1, 2]                        [1, 2]        ->  [1, 2]
[2, 1, 3, 2]                  [1, 2]        ->  [1, 3, 2]
[1, 2, 4, 8]                  [1, 4, 8]     ->  [1, 2, 4, 8]
[0, 1, 1, 0, 0, 1, 1, 1, 0]   [0, 1, 0]     ->  [0, 1, 1, 0]
[1, 5, 3, 7, 1, 3, 3, 5, 7]   [1, 3, 5, 7]  ->  [1, 3, 3, 5, 7]
[1, 2, 5, 1, 3, 5]            [1, 5]        ->  [1, 2, 5] OR [1, 3, 5]

Other:

This is code-golf, so shortest answer in bytes per language wins!

Answer 1

Jelly, 7 bytes

ẆŒPi¥ƇḢ

Try it online!

-1 byte thanks to Unrelated String

ẆŒPi¥ƇḢ   Main Link
      Ḣ   Find the first
Ẇ         slice (ordered by length)
     Ƈ    where
   i      the right list's index is truthy (occurs in)
 ŒP       the powerset (stable ordered)

1-indexing saves me a byte, thank you Dennis!

Answer 2

Brachylog, 8 bytes

⟨s⊇⟩ᶠlᵒh

Try it online!

⟨  ⟩ᶠ       Find every
 s          substring of the first input
  ⊇         containing the second input as a substring.
     lᵒ     Sort by length
       h    and take the first.

Answer 3

Husk, 8 bytes

◄Lfo€⁰ṖQ

Try it online!

yes another carriage in the 8-byte golflang answer train.

Answer 4

J, 64 bytes

]{~0({.+i.@>:@g)@>@{[:(]/:(g=.{:-{.)&>)@(#~]=/:~&.>)@,@{[:<@I.=/

Try it online!

Well 8-byte folks, let's square the byte count, shall we?

I could save bytes here by just trying every possible subset, but this approach seemed more interesting, and for most inputs is likely faster.

the idea

Consider 1 3 5 7 f 1 5 3 7 1 3 3 5 7:

• Create an equality table:

  1 0 0 0 1 0 0 0 0
  0 0 1 0 0 1 1 0 0
  0 1 0 0 0 0 0 1 0
  0 0 0 1 0 0 0 0 1
  

• Get indexes of ones:

  ┌───┬─────┬───┬───┐
  │0 4│2 5 6│1 7│3 8│
  └───┴─────┴───┴───┘
  

• Cartesian product:

  ┌───────┬───────┬───────┬───────┬
  │0 2 1 3│0 2 1 8│0 2 7 3│0 2 7 8│ ...etc...
  └───────┴───────┴───────┴───────┴
  

• Filter only elements that are ordered:

  ┌───────┬───────┬───────┬───────┬───────┐
  │0 2 7 8│0 5 7 8│0 6 7 8│4 5 7 8│4 6 7 8│
  └───────┴───────┴───────┴───────┴───────┘
  

• Sort by difference between first and last element:

  ┌───────┬───────┬───────┬───────┬───────┐
  │4 5 7 8│4 6 7 8│0 2 7 8│0 5 7 8│0 6 7 8│
  └───────┴───────┴───────┴───────┴───────┘
  

• Take first element, and construct full range between first and last:

   4 5 6 7 8
  

• Use those to index into the input:

  1 3 3 5 7
  

Answer 5

JavaScript (ES6),  89 87  83 bytes

Saved 4 bytes thanks to @tsh

Expects (haystack)(needle).

a=>b=>a.reduce((r,_,i)=>b.every(x=>j=a.indexOf(x,j)+1,j=i)/r[j-i]?a.slice(i,j):r,a)

Try it online!

Commented

a =>                  // a[] = haystack
b =>                  // b[] = needle
a.reduce((r, _, i) => // for each entry at position i in a[]:
  b.every(x =>        //   for each entry x in b[]:
    j =               //     update j to:
      a.indexOf(x, j) //       the index of x in a[], starting at j
      + 1,            //       to which we add 1
    j = i             //     starting with j = i
  )                   //   end of every()
  / r[j - i]          //   test whether r[j - i] is defined
  ?                   //   if successful:
    a.slice(i, j)     //     update r[] to the current slice of a[]
  :                   //   else:
    r,                //     leave r[] unchanged
  a                   //   start with r[] = a[]
)                     // end of reduce()

---

JavaScript (ES6),  91  89 bytes

Saved 2 bytes thanks to @tsh

Expects (needle)(haystack).

b=>g=(a,n)=>a.some((_,i)=>`${s=a.slice(i,i+n)}`.match(`^${b.join`,(.*,)*`}$`))?s:g(a,-~n)

Try it online!

How?

We turn the needle b[] into a regular expression:

RegExp(`^${b.join`,(.*,)*`}$`)

Example:

[1, 4, 8] ~> /^1,(.*,)*4,(.*,)*8$/

We recursively look for the smallest n such that there exists a slice s[] of a[] of length n that matches this regular expression.

Answer 6

JavaScript (ES6), 93 bytes

a=>b=>a.reduce(r=>1/r[p=b.map((m,j)=>t=m-a[i]?p[j]:j?p[j-1]:i),++i-t]?a.slice(t,i):r,a,i=p=0)

Try it online!

For inputs \$ a\left[1\dots N\right] \$ and \$ b\left[1\dots M\right] \$

Let matrix \$p_{N\times M}\$ be

$$ p_{i,j}=\begin{cases} i & b_j=a_i \land j=1 \\ p_{i-1,j-1} & b_j=a_i \land j>1 \land i>1 \\ p_{i-1,j} & b_j\ne a_i \land i > 1 \\ -\infty & \text{otherwise} \\ \end{cases} $$

the minimal length of output \$L\$ is

$$ L = \min_{i \in 1\dots N} i-p_{i,M}+1 $$

And the output is

$$ a\left[p_{i,M}\dots i\right] $$

where \$i\$ is the value for minimal \$L\$.

This solution works in \$ O\left(M^2\right) \$ time and \$ O\left(N\right) \$ extra memory.

Answer 7

Vyxal, 9 bytes

ÞS'ṗ⁰c;Þg

Try it Online!

       Þg # Shortest
ÞS        # sublist
  '   ;   # where
   ṗ      # powerset 
     c    # contains
    ⁰     # input

Answer 8

05AB1E, 8 bytes

Œé.ΔæX.å

Try it online or verify all test cases.

Explanation:

Π        # Get all sublists of the (implicit) input-list
 é        # Sort these sublists by smallest to largest length
  .Δ      # Find the first sublist which is truthy for:
    æ     #  Get the powerset of this sublist
     I.å  #  And check if it contains the second input-list
          # (after which this shortest found result is output implicitly)

Answer 9

Python 2, 94 bytes

Using iter to check if s is a subsequence of b is a trick I've first seen on this answer.

def f(a,b,i=0):l=len(a);s=a[i%l:][:i/l];x=iter(s);return s*all(v in x for v in b)or f(a,b,i+1)

Try it online!

Answer 10

Charcoal, 60 bytes

≔Ｅ⌕Ａθ⊟η⟦¹ι⟧ζＦ⮌η«ＦζＦ⌕Ａ…θ§κ¹ι⊞υ⟦⁻Σκλλ⟧≔υζ≔⟦⟧υ»≔⌊ζε≔⊟εδＩ✂θδ⁺δ⊟ε

Try it online! Link is to verbose version of code. Explanation:

≔Ｅ⌕Ａθ⊟η⟦¹ι⟧ζ

Get the last element of the array to match and find all of its indices in the array to search, yielding an array [1, i] for each position. These values relate to the length and start position of a slice of the array to search, initially only containing the last element of the array to match.

Ｆ⮌η«

Loop over the remaining elements in reverse order.

Ｆζ

Loop over the matches so far.

Ｆ⌕Ａ…θ§κ¹ι

Loop over all the positions of the next element in the prefix of the current match.

⊞υ⟦⁻Σκλλ⟧

Save the new match length and start position.

≔υζ≔⟦⟧υ

Move the working list back to the list of matches and clear the working list again.

»≔⌊ζε≔⊟εδ

Get the match with the shortest length and get its start position.

Ｉ✂θδ⁺δ⊟ε

Output the slice of that length at that position.

Answer 11

Retina, 34 bytes

1A`
,
.$*
~)`^
1G`¶Lw`
N$`
$.&
1G`

Try it online! Takes two newline-separated lists of distinctive words (i.e. no word is contained in another word) but link is to test suite that splits on semicolons for convenience. Explanation:

1A`

Delete the array to search.

,
.$*

Replace each comma with a regex for arbitrary content.

^
1G`¶Lw`

Prefix a command to delete the array to match and list all overlapping matches in the array to search.

~)`

Evaluate the result on the original input.

N$`
$.&

Sort the matches by length.

1G`

Take the first.

Answer 12

R, 95, 94 bytes

Assuming combn always returns sorted indexes

At the moment the assumption is valid in all R versions, but is not documented; the alternative (longer) solution is reported at the bottom of the answer

• -1 byte thanks to @Dominc van Essen

function(v,s,`+`=length){for(x in combn(+v,+s,,F))if(all(v[x]==s)&+v[T]>+(y=x:x[+x]))T=y;v[T]}

Try it online!

Unrolled code with explanation:

function(v,s){                  # take full vector v and the vector to search s
  r=v                           # init shortest slice r to full vector v
  for(x in combn(length(v),     # for each combination x of length(s) elements taken 
                 length(s),,F){ # from the vector of indexes 1:length(v)
                                # (we assume x is sorted ascending)
    a=v[x:x[+x]]                # get the slice between first and last index in x         
    if(all(v[x]==s) &           # if the values of the combinations == s and
       length(r) > length(a))   # the slice is shorter than r
      r=a                       # store the new slice
  }
  r                             # return the shortest slice
}

---

Version without assumption:

R, 107 bytes

function(v,s,r=v,`+`=length){for(x in combn(+v,+s,,F)){y=sort(x);if(all(v[x]==s)&+r>+(a=v[x:x[+x]]))r=a};r}

Try it online!

Answer 13

Japt, 9 bytes

ã æÈà deV

Try it

ã æÈà deV     :Implicit input of arrays U=haystack & V=needle
ã             :Sub-arrays of U
  æ           :Get the first that returns true
   È          :When passed through the following function
    à         :  Combinations
      d       :  Any
       eV     :    Equal to V

Answer 14

GForth, 241 bytes

: s 1 /string ;
: d 2drop ;
: o 2over ;
: h over >r begin o drop c@ scan 2>r s 2r> 2 pick 0= over 0= 2* or ?dup until nip 2nip 1+ swap r@ - r> -rot or ;
: f 2dup 2>r begin o o h dup r@ u< if 2rdrop 2>r else d then s dup 0= until d d 2r> 1+ ;

Try it online!

Formatted & commented version

also a bit ungolfed

: s 1 /string ;
: d 2drop ;
: o 2over ;

\ find the first match. if there is no match, return a string with the maximum length (-1)
: h ( target container -- caddr u )
    \ store the start address of the string on the return stack
    over >r
    begin
        \ remove characters from the front of the string until
        \ the string starts with the same character as
        \ the target string (or until it is empty)
        o drop c@ scan

        \ remove a character from the front of the target string
        2>r s 2r>

        \ some magic that gives -1 if the target string is empty,
        \ -2 if the container string is empty, and 0 otherwise
        2 pick 0= over 0= 2* or
        \ duplicate the top of the stack if it isn't zero
        ?dup
        \ exit the loop if the top of the stack is something other than zero
    until
    \ get rid of everything on the stack except for new address of the string
    \ if there was a match, this will be the address of the end of the match.
    nip 2nip
    \ use this and the saved start address to reconstruct the match.
    1+ swap r@ - r> -rot
    \ if we didn't get a match, use the magic from before to replace the length with -1
    or ;


: f ( target container -- caddr u )
    \ store the current shortest match on the return stack.
    \ since it is given that there will be a match in the array,
    \ we put that on the return stack first
    2dup 2>r

    begin
        \ find the first match, and compare its length to
        \ the length of the match on the return stack
        o o h dup r@ u< if
            \ if it is shorter, replace the string on the return stack with it
            2rdrop 2>r
        else
            \ otherwise, discard it
            d
        then
        \ remove a charachter from the front of the string
        s
        \ if there are no more charachters in the string, exit the loop
        dup 0=
    until
    \ get rid of everything and retrive the stored match
    d d 2r>
    \ there's an off by one error here somewhere. rather than fix it, just add one.
    1+ ;

```

Answer 15

R >= 4.1.0, 139 bytes

\(x,y,`~`=\(a,b)paste(a,collapse=b))(u<-combn(1:sum(x|1),2,\(z)if(grepl(y~" .* ",(v=x[z[1]:z[2]])~"  "))v,F))[order((m=lengths(u))/!!m)][1]

Try it online!

A function that takes the x as the vector to look within and y as the vector to look for. Returns a length 1 list containing the shortest matching contiguous subsequence of x. TIO link replaces \ with function since TIO is running an earlier version of R.

Answer 16

Python 3.8, 152 bytes

The other python answer is too good - but just leaving mine here anyway

from itertools import*
f=lambda a,b:min(((Y:=c[0][0]),(Z:=c[-1][0]),a[Y:Z+1],Z-Y)[::-1]for c in combinations(enumerate(a),len(b))if[*zip(*c)][1]==b)[1]

older uncondensed version

from itertools import*
def f(a,b):
    #print(*permutations(a), sep='\n')
    combis = [*combinations(enumerate(a),len(b))]
    #print(combis)
    F=[(combi[0][0],combi[-1][0]) for combi in combis if [*zip(*combi)][1]==b]
    #print(F)
    s,e = min(F, key=lambda i:i[1]-i[0])
    #print(s,e,a,a[s:e+1])
    return a[s:e+1]

Answer 17

Wolfram Language (Mathematica), 67 bytes

(c=___;#1/.{c,x:Shortest[PatternSequence@@Riffle[#2,c]..],c}:>{x})&

Try it online!

No brutal force, just patterns usage