# Uniquely removable subsequences

## Introduction

Consider a sequence of integers and one of its subsequences, say A = [4 2 2 4 4 6 5] and B = [2 4 5]. We want to remove the elements of B from A in order, and there are several ways of doing that:

A = 4 2 2 4 4 6 5
B =   2   4     5
-> 4   2   4 6

A = 4 2 2 4 4 6 5
B =     2 4     5
-> 4 2     4 6

A = 4 2 2 4 4 6 5
B =   2     4   5
-> 4   2 4   6

A = 4 2 2 4 4 6 5
B =     2   4   5
-> 4 2   4   6


In all cases, the remaining sequence is the same, [4 2 4 6]. If this happens, we say that B is uniquely removable from A.

Your inputs are two sequences of nonnegative integers, A and B, where B is guaranteed to be a subsequence of A. The inputs may be equal, and they may be empty. You can take them in any order you want, in any reasonable format.

Your output shall be a truthy value if B is uniquely removable from A, and a falsy value if not.

## Rules and scoring

You can write a full program or a function. The lowest byte count wins.

## Test cases

[] [] -> True
[0,3] [] -> True
[1,0,1] [1] -> False
[0,2] [0,2] -> True
[2,2,1,1,2,2,2] [2,1] -> True
[4,2,2,4,4,6,5] [4,5] -> False
[10,5,10,10,5,10] [10,5,10] -> False
[4,2,2,4,4,6,5] [2,4,5] -> True
[1,1,1,0,0,0,1,1,1,0] [1,0,1,1] -> True
[0,1,0,0,0,0,1,1,0,1] [1,0,1,1] -> False
[0,4,0,0,4,1,4,2,2] [0,0,0,1,4] -> True
[0,2,2,25,0,2,2,26,0,0,2] [2,0,0,0,2] -> True
[1,1,1,3,2,1,3,2,2,3,3,2] [1,1,2,3,2] -> False
[0,3,2,0,1,3,2,0,0,0,3,2] [0,1,2,0,3] -> False
[5,7,2,7,7,1,7,7,5,2,7,7,5,2,2,7,5] [2,7,5,7,7,2] -> False
[5,4,0,5,4,5,4,1,0,4,2,1,1,2,4,4,0,2,2,1] [4,0,1,1,2,1] -> False
[0,1,4,0,1,4,0,1,5,1,4,4,2,0,0,1,1,1,2,4] [0,1,0,0,2,0,1,4] -> True


a%[]=[a]
(t:z)%x@(s:y)=[a|a<-z%y,t==s]++[t:s|s<-z%x]
_%_=[]


Construct the list of all possible subtracted sequences nondeterministically and checks whether they are all equal.

Usage:

*Main> mapM_(\(a,b)->let r=(((all=<<(==).head).).(%)) a b in putStrLn$concat[show a," ",show b," -> ",show r]) [([],[]), ([0,3],[]), ([1,0,1],[1]), ([0,2],[0,2]), ([2,2,1,1,2,2,2],[2,1]), ([4,2,2,4,4,6,5],[4,5]), ([10,5,10,10,5,10],[10,5,10]), ([4,2,2,4,4,6,5],[2,4,5]), ([1,1,1,0,0,0,1,1,1,0],[1,0,1,1]), ([0,1,0,0,0,0,1,1,0,1],[1,0,1,1]), ([0,4,0,0,4,1,4,2,2],[0,0,0,1,4]), ([0,2,2,25,0,2,2,26,0,0,2],[2,0,0,0,2]), ([1,1,1,3,2,1,3,2,2,3,3,2],[1,1,2,3,2]), ([0,3,2,0,1,3,2,0,0,0,3,2],[0,1,2,0,3]), ([5,7,2,7,7,1,7,7,5,2,7,7,5,2,2,7,5],[2,7,5,7,7,2]), ([5,4,0,5,4,5,4,1,0,4,2,1,1,2,4,4,0,2,2,1],[4,0,1,1,2,1]), ([0,1,4,0,1,4,0,1,5,1,4,4,2,0,0,1,1,1,2,4],[0,1,0,0,2,0,1,4])] [] [] -> True [0,3] [] -> True [1,0,1] [1] -> False [0,2] [0,2] -> True [2,2,1,1,2,2,2] [2,1] -> True [4,2,2,4,4,6,5] [4,5] -> False [10,5,10,10,5,10] [10,5,10] -> False [4,2,2,4,4,6,5] [2,4,5] -> True [1,1,1,0,0,0,1,1,1,0] [1,0,1,1] -> True [0,1,0,0,0,0,1,1,0,1] [1,0,1,1] -> False [0,4,0,0,4,1,4,2,2] [0,0,0,1,4] -> True [0,2,2,25,0,2,2,26,0,0,2] [2,0,0,0,2] -> True [1,1,1,3,2,1,3,2,2,3,3,2] [1,1,2,3,2] -> False [0,3,2,0,1,3,2,0,0,0,3,2] [0,1,2,0,3] -> False [5,7,2,7,7,1,7,7,5,2,7,7,5,2,2,7,5] [2,7,5,7,7,2] -> False [5,4,0,5,4,5,4,1,0,4,2,1,1,2,4,4,0,2,2,1] [4,0,1,1,2,1] -> False [0,1,4,0,1,4,0,1,5,1,4,4,2,0,0,1,1,1,2,4] [0,1,0,0,2,0,1,4] -> True  Thanks to @Zgarb for saving 6 bytes! • You can rearrange things and have x%_=x for the second case of %. Also, I think the main function would be shorter in pointful form. – Zgarb Dec 5 '16 at 11:50 • @Zgarb x%_=x won't work because the types won't match but _%_=[] saves a byte. – Angs Dec 5 '16 at 11:56 # JavaScript (ES6), 141 152 156 159 Recursive function - quite long f=(a,b,i=0,j=0,r=a,S=new Set)=>(1/b[j]?1/a[i]&&f(a,b,i+1,j,r,S,a[i]-b[j]||f(a,b,i+1,j+1,r=[...r],r[i]=S)):S.add(0+r.filter(x=>1/x)),S.size<2)  Less golfed f=(a, b, i = 0, // current position to match in a j = 0, // current position to match in b r = a, // current result so far, A with elements of B removed - start == A S = new Set // set of possible "A removed B" ) => ( 1 / b[j] // check if j is still inside B ? 1 / a[i] // if i is inside A && ( // in any case try to find current element of B in the remaining part of A f(a, b, i+1, j, r, S), a[i] == b[j] // if match was found between A and B && // mark current element in a copy of r and // look for the next element of B in the remaining part of A f(a, b, i+1, j+1, r=[...r], r[i]=S), ) // else - j is not inside B, we have a solution in r // use filter to get a copy without the marked elements // (note: 1/any_number == number_not_0, 1/Object == NaN) // then convert to string, to use as a key in S : S.add(0+a.filter(x=>1/x)), S.size<2 // return true if S has only 1 element )  Test f=(a,b,i=0,j=0,r=a,S=new Set)=>(1/b[j]?1/a[i]&&f(a,b,i+1,j,r,S,a[i]-b[j]||f(a,b,i+1,j+1,r=[...r],r[i]=S)):S.add(0+r.filter(x=>1/x)),S.size<2) out=(...x)=>O.textContent+=x.join +'\n' ;[] [] -> True [0,3] [] -> True [1,0,1] [1] -> False [0,2] [0,2] -> True [2,2,1,1,2,2,2] [2,1] -> True [4,2,2,4,4,6,5] [4,5] -> False [10,5,10,10,5,10] [10,5,10] -> False [4,2,2,4,4,6,5] [2,4,5] -> True [1,1,1,0,0,0,1,1,1,0] [1,0,1,1] -> True [0,1,0,0,0,0,1,1,0,1] [1,0,1,1] -> False [0,4,0,0,4,1,4,2,2] [0,0,0,1,4] -> True [0,2,2,25,0,2,2,26,0,0,2] [2,0,0,0,2] -> True [1,1,1,3,2,1,3,2,2,3,3,2] [1,1,2,3,2] -> False [0,3,2,0,1,3,2,0,0,0,3,2] [0,1,2,0,3] -> False [5,7,2,7,7,1,7,7,5,2,7,7,5,2,2,7,5] [2,7,5,7,7,2] -> False [5,4,0,5,4,5,4,1,0,4,2,1,1,2,4,4,0,2,2,1] [4,0,1,1,2,1] -> False [0,1,4,0,1,4,0,1,5,1,4,4,2,0,0,1,1,1,2,4] [0,1,0,0,2,0,1,4] -> True .split('\n').forEach(t=>{ var [a,b,_,k]=t.match(/\S+/g) var r=f(eval(a),eval(b)) out(r==(k[0]=='T')?'OK':'KO',a,b,r,k) }) <pre id=O></pre> # Pyth - 27 bytes On mobile in school right now, so not fully golfed. JE!t{.DLQfqJ@LQT{I#{SM^UQlJ  Test Suite ## JavaScript (ES6), 116114 113 bytes Returns false or true. (a,b,p)=>((F=(a,i,m)=>1/b[i]?a.map((n,j)=>m>j|n-b[i]||F(a.filter((_,k)=>j-k),i+1,j)):p?r|=p!=a:p=a+'')(a,r=0),!r)  ### Formatted and commented ( // given: a, b, // - a, b = input arrays p // - p = reference pattern, initially undefined ) => ( // (F = ( // F is our recursive search function, with: a, // - a = current working copy of the main array i, // - i = index in 'b' m // - m = minimum index of matching values in 'a' ) => // 1 / b[i] ? // if we haven't reached the end of 'b': a.map((n, j) => // for each element 'n' at index 'j' in 'a': m > j | n - b[i] || // if 'n' is a valid matching value, F( // do a recursive call to F(), using: a.filter((_, k) => j - k), // - a copy of 'a' without the current element i + 1, // - the next index in 'b' j // - 'j' as the new minimum index in 'a' ) // ) // : // else: p ? // if the reference pattern is already set: r |= p != a // check if it's matching the current 'a' : // else: p = a + '' // set the current 'a' as the reference pattern )(a, r = 0), // initial call to F() + initialization of 'r' !r // yields the final result ) //  ### Test cases let f = (a,b,p)=>((F=(a,i,m)=>1/b[i]?a.map((n,j)=>m>j|n-b[i]||F(a.filter((_,k)=>j-k),i+1,j)):p?r|=p!=a:p=a+'')(a,r=0),!r) console.log(f([],[])); // -> true console.log(f([0,3],[])); // -> true console.log(f([1,0,1],[1])); // -> false console.log(f([0,2],[0,2])); // -> true console.log(f([2,2,1,1,2,2,2],[2,1])); // -> true console.log(f([4,2,2,4,4,6,5],[4,5])); // -> false console.log(f([10,5,10,10,5,10],[10,5,10])); // -> false console.log(f([4,2,2,4,4,6,5],[2,4,5])); // -> true console.log(f([1,1,1,0,0,0,1,1,1,0],[1,0,1,1])); // -> true console.log(f([0,1,0,0,0,0,1,1,0,1],[1,0,1,1])); // -> false console.log(f([0,4,0,0,4,1,4,2,2],[0,0,0,1,4])); // -> true console.log(f([0,2,2,25,0,2,2,26,0,0,2],[2,0,0,0,2])); // -> true console.log(f([1,1,1,3,2,1,3,2,2,3,3,2],[1,1,2,3,2])); // -> false console.log(f([0,3,2,0,1,3,2,0,0,0,3,2],[0,1,2,0,3])); // -> false console.log(f([5,7,2,7,7,1,7,7,5,2,7,7,5,2,2,7,5],[2,7,5,7,7,2])); // -> false console.log(f([5,4,0,5,4,5,4,1,0,4,2,1,1,2,4,4,0,2,2,1],[4,0,1,1,2,1])); // -> false console.log(f([0,1,4,0,1,4,0,1,5,1,4,4,2,0,0,1,1,1,2,4],[0,1,0,0,2,0,1,4])); // -> true • Wow! I tried to find a way to recurse with a reduced copy of A, but no success – edc65 Dec 7 '16 at 15:38 # MATL, 27 bytes n:inXN!"1G@&)w2G=?}x]]tvdz~  The longest test cases run out of time in the online compiler. Try it online! # JavaScript (Firefox 30+), 159 147 bytes f=(a,b,i=f(a,b,0))=>i?i.every(x=>x+""==i[0]):b+b?a+a&&[for(n of a)if(a[i++]==b[0])for(x of f(a.slice(i),b.slice(1),0))[...a.slice(0,i-1),...x]]:[a]  Here's a couple of alternate approaches, both anonymous functions: (a,b,f=(a,b,i=0)=>b+b?a+a&&[for(n of a)if(a[i++]==b[0])for(x of f(a.slice(i),b.slice(1)))[...a.slice(0,i-1),...x]]:[a],c=f(a,b))=>c.every(x=>x+""==c[0]) (a,b,f=(a,b,i=0)=>b+b?a+a&&[for(n of a)if(a[i++]==b[0])for(x of f(a.slice(i),b.slice(1)))[...a.slice(0,i-1),...x]]:[a])=>new Set(f(a,b).map(btoa)).size<2  ### Test snippet f=(a,b,i=f(a,b,0))=>i?i.every(x=>x+""==i[0]):b+b?a+a&&[for(n of a)if(a[i++]==b[0])for(x of f(a.slice(i),b.slice(1),0))[...a.slice(0,i-1),...x]]:[a] T.textContent = T.textContent.split .map(x => x +  (${f(...x.split .slice(0,2).map(eval))})).join

<pre id=T>[] [] -> True
[0,3] [] -> True
[1,0,1] [1] -> False
[0,2] [0,2] -> True
[2,2,1,1,2,2,2] [2,1] -> True
[4,2,2,4,4,6,5] [4,5] -> False
[10,5,10,10,5,10] [10,5,10] -> False
[4,2,2,4,4,6,5] [2,4,5] -> True
[1,1,1,0,0,0,1,1,1,0] [1,0,1,1] -> True
[0,1,0,0,0,0,1,1,0,1] [1,0,1,1] -> False
[0,4,0,0,4,1,4,2,2] [0,0,0,1,4] -> True
[0,2,2,25,0,2,2,26,0,0,2] [2,0,0,0,2] -> True
[1,1,1,3,2,1,3,2,2,3,3,2] [1,1,2,3,2] -> False
[0,3,2,0,1,3,2,0,0,0,3,2] [0,1,2,0,3] -> False
[5,7,2,7,7,1,7,7,5,2,7,7,5,2,2,7,5] [2,7,5,7,7,2] -> False
[5,4,0,5,4,5,4,1,0,4,2,1,1,2,4,4,0,2,2,1] [4,0,1,1,2,1] -> False
[0,1,4,0,1,4,0,1,5,1,4,4,2,0,0,1,1,1,2,4] [0,1,0,0,2,0,1,4] -> True</pre>

• I like the snippet too – edc65 Dec 5 '16 at 19:06

# Mathematica, 128 bytes

h=Length;n=ToExpression;g=ToString;y=Array;h@Union@ReplaceList[#2,n@Riffle[y["a"<>g@#<>"___"&,t=h@#+1],#]->n@y["a"<>g@#&,t]]==1&


Unnamed function taking two list arguments, where the first is the subsequence and the second is the full sequence; outputs True or False.

The core part is the following sequence, ungolfed for readability:

ReplaceList[#2, ToExpression @
Riffle[
Array["a" <> ToString@# <> "___" &, Length@# + 1]
, #
] -> ToExpression @
Array["a" <> ToString@#& , Length@# + 1 ]
]


Here # represents the subsequence—for example, {2,4,5}. The first Array command creates a list of strings like {"a1___","a2___","a3___","a4___"}, which is then Riffled together with # to yield a weird list like {"a1___",2,"a2___",4,"a3___",5,"a4___"}; then this list is cast into an actual Mathematica expression. For the example {2,4,5}, a partial evaluation of this core code is

ReplaceList[#2, {a1___,2,a2___,4,a3___,5,a4___} -> {a1,a2,a3,a4}]


which exactly gives a list of all possible ways to remove the subsequence {2,4,5} from #2 and leave the rest of the list alone.

After this list is generated, we simply remove duplicates using Union and test whether the length of the resulting output is 1 or not.