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!
17 Answers 17
Jelly, 7 bytes
ẆŒPi\ƇḢ
-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!
-
\$\begingroup\$ -1 \$\endgroup\$Unrelated String– Unrelated String2021年06月03日 05:20:51 +00:00Commented Jun 3, 2021 at 5:20
-
\$\begingroup\$ @UnrelatedString Oh smart. Thanks \$\endgroup\$2021年06月03日 05:52:24 +00:00Commented Jun 3, 2021 at 5:52
-
2\$\begingroup\$ Relevant tip for Unrelated's golf (shameless plug) \$\endgroup\$2021年06月04日 02:10:57 +00:00Commented Jun 4, 2021 at 2:10
Brachylog, 8 bytes
⟨s⊇⟩floh
⟨ ⟩f Find every
s substring of the first input
⊇ containing the second input as a substring.
lo Sort by length
h and take the first.
-
1\$\begingroup\$ not only 8 bytes all answes have 3 votes too \$\endgroup\$wasif– wasif2021年06月03日 05:27:23 +00:00Commented Jun 3, 2021 at 5:27
-
\$\begingroup\$ sorry, (unrelated string) broke the pattern \$\endgroup\$2021年06月03日 06:53:40 +00:00Commented Jun 3, 2021 at 6:53
J, 64 bytes
]{~0({.+i.@>:@g)@>@{[:(]/:(g=.{:-{.)&>)@(#~]=/:~&.>)@,@{[:<@I.=/
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 1Get 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 8Use those to index into the input:
1 3 3 5 7
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)
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)
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.
-
\$\begingroup\$
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)\$\endgroup\$tsh– tsh2021年06月03日 10:07:17 +00:00Commented Jun 3, 2021 at 10:07
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)
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.
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)
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)
Charcoal, 60 bytes
≔E⌕Aθ⊟η⟦1ι⟧ζF⮌η«FζF⌕A...θ§κ1ι⊞υ⟦−Σκλλ⟧≔υζ≔⟦⟧υ»≔⌊ζε≔⊟εδI✂θδ+δ⊟ε
Try it online! Link is to verbose version of code. Explanation:
≔E⌕Aθ⊟η⟦1ι⟧ζ
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.
F⮌η«
Loop over the remaining elements in reverse order.
Fζ
Loop over the matches so far.
F⌕A...θ§κ1ι
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.
I✂θδ+δ⊟ε
Output the slice of that length at that position.
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.
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]}
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}
-
1\$\begingroup\$ Really nice! I think you might be able to save 1 byte with a bit of rearrangement... \$\endgroup\$Dominic van Essen– Dominic van Essen2021年06月04日 16:00:45 +00:00Commented Jun 4, 2021 at 16:00
Japt, 9 bytes
ã æÈà deV
ã æÈà 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
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+ ;
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+ ;
```
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]
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.
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]
Wolfram Language (Mathematica), 67 bytes
(c=___;#1/.{c,x:Shortest[PatternSequence@@Riffle[#2,c]..],c}:>{x})&
No brutal force, just patterns usage
[0,9]? \$\endgroup\$