Shortest restricted superstring

Question

Given two sets of strings, \$ D \$ and \$ R \$, find the shortest string which contains every string in \$ D \$, but contains none of the strings in \$ R \$.

There are almost always multiple possible outputs; you should output at least one of them, but you can output more.

You can assume this is possible with the inputs you are given; i.e., none of the strings in \$ R \$ are substrings of those in \$ D \$.

Note that the result \$ s \$ may have to include characters which are not present in any of the strings in \$ D \$. For example, when \$ D = \{\text a, \text b\} \$ and \$ R = \{\text {ab}, \text {ba}\} \$, there must be at least one other character in the output - it would have to be something like \$ \text {axb} \$ or \$ \text {bxa} \$.

Furthermore, in order to simplify dealing with the case above, you may choose a character that you can assume to never be present in the input, but is allowed in the output. For example, you may restrict your input to always use letters, but sometimes give outputs containing underscores as well as letters.

"String" here is used in an abstract sense: you may operate on actual strings of characters, but also on lists of positive integers, or any other reasonable domain.

This is code-golf, so the shortest code in bytes wins.

Test cases

\$ D \$	\$ R \$	output
(empty set)	(empty set)	(empty string)
(empty set)	a	(empty string)
a	(empty set)	a
ab, bc	(empty set)	abc
a, b	ab, ba	axb or a$b or etc.
ab, bc	abc	bcab or abbc
ab, cd	bc	cdab
ab, a	c	ab
code, golf, fig, egg	igo	codeggolfig
a, b, c	abc, bac, ca	cba or acb
a, b, c	ab, bc, ac, ba, cb, ca	a$b$c etc.

This question came to me while attempting to optimise the substring check in this answer.

Answer 1

Python, 150 bytes

f=lambda D,R,m=min:m([h for d in D for e in f(D-{d},R,sorted)for x in range(len(d)+2)if(d in(h:=(d+"_")[:x]+e))>any(r in h for r in R)]or[""],key=len)

Attempt This Online!

Old Python, 152 bytes

lambda D,R:min((g:=lambda D:[h for d in D for e in g(D-{d})for x in range(len(d)+2)if(d in(h:=(d+"_")[:x]+e))>any(r in h for r in R)]or[""])(D),key=len)

Attempt This Online!

Old Python, 158 bytes

lambda D,R:min((g:=lambda D:[h for d in D for e in g(D-{d})for x in range(len(d)+2)if d in(h:=(d+"_")[:x]+e)and not any(r in h for r in R)]or[""])(D),key=len)

Attempt This Online!

Answer 2

JavaScript (ES6),  159  157 bytes

Expects [D,R]. Assumes that the input words are made of letters and uses 0 as the separator.

f=(b,a=b[q=0],p='')=>a.map((v,i,g)=>(g=v=>f(b,a.filter((_,k)=>k-i),p+v)&&v&&g(v.slice(1)))(0+v))+[p[q.length]]||b.some((a,i)=>a.some(w=>!p.match(w)^i))?q:q=p

Try it online!

Commented

f = (                    // f is a recursive function using:
  b,                     //   b[] = [D[], R[]]
  a = b[q = 0],          //   a[] = D[],
                         //   q = final output (initially not a string)
  p = ''                 //   p = current output
) =>                     //
a.map((v, i, g) =>       // for each string v at position i in a[]:
  ( g = v =>             //   g is a recursive function taking a string v
    f(                   //     do a recursive call to f:
      b,                 //       pass b[] unchanged
      a.filter((_, k) => //       pass a copy of a[] ...
        k - i            //       ... with the i-th entry removed
      ),                 //
      p + v              //       append v to p
    )                    //     end of recursive call
    && v                 //     unless v is an empty string:
    && g(v.slice(1))     //       do a recursive call to g with v.slice(1)
  )(0 + v)               //   initial call to g with a leading "0" added to v
)                        // end of map(), whose result is coerced to a string
+ [p[q.length]] ||       // if a[] was empty and p[q.length] is undefined:
  b.some((a, i) =>       //   for each entry a[] at position i in b[]:
    a.some(w =>          //     for each string w in a[]:
      !p.match(w)        //       1 if w is not found in p / 0 otherwise
      ^ i                //       XOR'ed with the expected result
                         //       (0 for D[], 1 for R[])
    )                    //     end of inner some()
  )                      //   end of outer some()
  ? q : q = p            //   update q to p if the above test didn't fail

Answer 3

Python, 172 168 164 bytes

from itertools import*
f=lambda D,R:next(x for i in count()for x in map("".join,product(*[{"$"}.union(*D|R)]*i))if all(j-(y in x)for j,X in[(0,D),(1,R)]for y in X))

Attempt This Online!

Answer 4

05AB1E, 18 19 bytes

JDu«æ€œ˜é.Δ¹åy²å_«P

+1 byte as bug-fix for test cases that require more than 1 random filler-character (e.g. [["a","b","c"],["ab","ba","ac","ca","bc","cb"]]).

Assumes the input are lowercase letters, and uses uppercase letters as potential filler-characters if necessary (e.g. for the fifth test case).

Try it online or verify (almost) all test cases.

Explanation:

J                 # Join the (implicit) first input-list together to a string
 Du«              # Append an uppercase copy of this string
    æ             # Get the powerset of this string
     €œ           # Get the permutations of each inner string
       ˜          # Flatten this list of list of strings
        é         # Sort it by length
         .Δ       # Find the first which is truthy for:
           ¹      #  Push the first input-list
            å     #  Check for each inner string if it's a substring
           y      #  Push the string we're filtering over again
            ²     #  Push the second input-list
             å    #  Check for each inner string again if it's a substring
              _   #  Invert the booleans to check all of them were falsey
               «  #  Merge the two lists together
                P #  Check that all are truthy by taking the product
                  # (after which the found result is output implicitly)

Answer 5

Python3, 261 bytes:

E=enumerate
def f(d,c=''):
 if not d:yield c;return
 for i,a in E(d):
  j=d[:i]+d[i+1:]
  yield from[*f(j,c+a),*f(j,c+'$'+a)]
  for x,y in E(a):
   if c[-1*x:]==a[:x]:yield from f(j,c+a[x:])
lambda d,r:min([i for i in f(d)if all(m not in i for m in r)],key=len)

Try it online!

Answer 6

Python 3, 141 bytes

f=lambda d,r,s='':d[len(s):]and min([s*(all(w in s for w in d.split())-any(w in s for w in r.split()))or f(d,r,s+c)for c in{*d}],key=len)or d

Try it online!

Recursive solution trying all possible permutations and returning the shortest one. Takes each input as a single space-separated string. Also uses [space] as the special character in the output. The longest test-case times out, but should work in principle.

Answer 7

Charcoal, 32 bytes

⊞υωＦυ¿¬ⅉ¿›⬤θ№ικ⊙η№ικ⟦ι⟧Ｆ⪫θ_⊞υ⁺ικ

Try it online! Link is to verbose version of code. Brute-force, so exponentially slow in the length of the output. Uses _ as the filler character. Explanation:

⊞υωＦυ

Start a breadth-first search of all strings containing the input characters or _.

¿¬ⅉ

Stop when a string has been output.

¿›⬤θ№ικ⊙η№ικ⟦ι⟧

If the current string satisfies the inputs then print it now.

Ｆ⪫θ_⊞υ⁺ικ

Otherwise, for each character in the inputs or _, append that character to the current string and push the result to the search list.