Is this substring list ambiguous?

Question

Given a set of substrings, such as [ca, ar, car, rd], it's possible to create infinitely many strings by concatting them together. Some examples of this for the given substrings could be:

ca
caar
card
rdca
carrd
rdrd
...

One interesting property of this set of substrings is that any string can only be constructed in one way using them; there is no string where it's ambiguous which combination was used. As a counterexample, take the set [foo, bar, obar, fo, baz]. The string foobar could either be foo + bar or fo + obar.

Task:

Given a set of substrings, which will not contain duplicates, determine if the above property holds; that is, if for any concatenated ordering of any number of the substrings, it is unambiguously possible to determine the original order of the substrings that it was constructed out of.

In place of substrings you may use lists, with any reasonable data type in place of characters. You may also restrict the characters used in the substrings within reason, such as only using lowercase letters. Your chosen representation of the substrings must be able to represent at least a dozen "characters".

You may produce output using any of the following:

• A truthy/falsy value, with truthy representing either ambiguous or unambiguous (your choice)
• Two consistent values representing ambiguous and unambiguous
• One consistent value representing either ambiguous or unambiguous, and any other value representing the other

Test cases:

[ca, ar, car, rd]           unambiguous
[foo, bar, obar, fo, baz]   ambiguous
[a, b, c]                   unambiguous
[a, ab]                     unambiguous
[ab, bc, c]                 unambiguous
[b, ab, ba]                 ambiguous
[b, ab, ba, aa]             ambiguous
[a, aa]                     ambiguous
[abc, bcd, cda, dab, abcd]  ambiguous
[nn, no, on, oo]            unambiguous
[atombomb, at, omb]         ambiguous
[abc, dx, yz, ab, cd, xyz]  ambiguous
[xxx, xxxxx]                ambiguous
[a, ax, xx]                 unambiguous
[baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa, aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac, w, wb, acx, xba, aacy, ybaa, aaacz, zbaaa, aaaacd, d]  ambiguous

(Thanks to @Arnauld, @CursorCoercer, and @loopywalt for the last three test cases)

Scoring:

This is code-golf, so shortest answer (in bytes, per language) wins.

Answer 1

JavaScript (ES6), 110 bytes

Returns false for unambiguous or true for ambiguous.

f=(a,p='',q=p)=>p>q?f(a,q,p):p&&p==q||q.match(p)&&!p[a.map(s=>n*=s.length,n=1)|n]&&a.some(s=>s!=q&&f(a,p+s,q))

Try it online!

Commented

f = (              // f is a recursive function taking:
  a,               //   a[] = list of substrings
  p = '',          //   p = first string, initially empty
  q = p            //   q = second string, initially empty
) =>               //
p > q ?            // if p is lexicographically greater than q:
  f(a, q, p)       //   swap p and q
:                  // else:
  p && p == q ||   //   stop as successful if p is non empty and p = q
  q.match(p) &&    //   stop as failed if p cannot be found in q
  !p[              //   stop as failed if p is too long:
    a.map(s =>     //     for the upper bound, we use the product n
      n *=         //     of all substring lengths
        s.length,  //     (e.g. for two substrings whose lengths x and y
      n = 1        //     are co-prime, we may need to build strings of
    ) | n          //     length x * y to get a match)
  ] &&             //
  a.some(s =>      //   for each substring s in a[]:
    s != q &&      //     provided that s is not equal to q,
    f(a, p + s, q) //     do a recursive call where s is appended to p
  )                //   end of some()

98 bytes, much slower

f=(a,p='',q=p)=>p>q?f(a,q,p):p&&p==q||!p[a.map(s=>n*=s.length,n=1)|n]&&a.some(s=>s!=q&&f(a,p+s,q))

Try it online!

Answer 2

Python, 104 bytes

f=lambda l,x=set():l>l-(y:={a[len(b):]for a in l|x for b in[l,l|x][{a}<l]if b+"~">a>b})or y-x and f(l,y)

Attempt This Online! Takes a set of strings (ASCII characters < "~"); returns the empty set for unambiguous and True for ambiguous.

How?

Alongside the set of given "syllables" we keep a set of "tips" which are generated by building two words from the syllables such that one is a prefix of the other (and they do not start with the same syllable). The tip is the longer word with the prefix removed.

At each iteration we try generating new tips by finding syllables which are prefixed by or do prefix a previously found tip. The new tip will be the difference. If no new tips are found output unambiguous, if a syllable was created as a new tip output ambiguous, otherwise rinse and repeat.

Answer 3

Python 3,  140 133  129 bytes

This is my golf of Ajax 1234's method (it was 197 at the time) - go upvote that answer!

-7 Thanks to ovs (use for j,k in q loop in place of while q loop to remove the need for j,k=q.pop().)

-4 Thanks to Sʨɠɠan (function rather than full-program.)

def f(a):
 d={};q=[(i,[i])for i in a]
 for j,k in q:q+=[(j+i,k+[i])for i in a if''.join(a)[:1-len(j+i):k in d.setdefault(j,[k])]]

A function that accepts a list of strings and identifies ambiguity by success/failure:

• Errors when ambiguous (raises a ValueError "slice step cannot be zero") or
• Succeeding when unambiguous (returns None).

Try it online! Or see the test-suite.

Answer 4

Python3, 277 bytes:

def F(a):
 q,s=[(j,k)for j in a for k in a if j!=k and j[:len(k)]==k],[]
 for j,k in q:
  if j==k:return 0
  j,k=sorted([j,k],key=len)
  if k[len(j):]in s:continue
  for i in a:
   if all(J==K for J,K in zip(i[:len(k)-len(j)],k[len(j):])):q+=[(j+i,k)];s+=[k[len(j):]]
 return 1

Try it online!

Answer 5

Charcoal, 34 bytes

ＷＳ⊞υι¹≔⮌υθＦθＦυ¿№θ⁺ικ⎚¿‹ＬιＬ⪫υω⊞θ⁺ικ

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings and outputs a Charcoal boolean, i.e. 1 for unambiguous, nothing for ambiguous. Explanation: Originally another port of @Ajax1234's answer, but since heavily simplified (see my comment on his answer), but it still seems to work, so...

ＷＳ⊞υι

Input the substrings.

¹

Assume they are unambiguous.

≔⮌υθＦθ

Start a breadth-first search with a clone of the list of substrings.

Ｆυ¿№θ⁺ικ⎚

Loop over all of the substrings and if an ambiguous concatenation is found then clear the canvas.

¿‹ＬιＬ⪫υω⊞θ⁺ικ

Otherwise if the current string is not too long then add the concatenation to the search.

Answer 6

Python 3, 219 bytes

lambda x:any(t!=s and t==s[:len(t)]and c(s,t,x) for s in x for t in x)
def c(m,n,e,t=[]):d=m[len(n):];return d not in t and(d in e or any(s==d[:len(s)]and c(m,n+s,e,t+[d])or d==s[:len(d)]and c(n+s,m,e,t+[d])for s in e))

Try it online!

Takes a list of strings as input, returns False for unambiguous and True for ambiguous

Answer 7

05AB1E, 14 8 bytes

ā€ãJ˜DÙQ

-6 bytes by checking if the flattened list contains only unique strings (taken from @lyxal's Vyxal answer)

Outputs 0 if ambiguous and 1 if unambiguous.

Try it online or verify all test cases with \$\leq4\$ items.

Explanation:

ā         # Push a list in the range [1, (implicit) input-length]
 €        # Map over each integer:
  ã       #  Get the value'th cartesian power of the (implicit) input-list
   J      # Join each inner-most lists together to a string
    ˜     # Flatten the list of lists of strings
     DÙQ  # Verify the list doesn't contain any duplicated strings:
     D    #  Duplicate this list
      Ù   #  Uniquify the copy
       Q  #  Check if the two lists are still the same
          # (after which the result is output implicitly)

Answer 8

Vyxal r, 11 8 7 bytes

żvÞẊfÞu

Try it Online!

Two can play at the porting game, Kevin! -3 bytes by using cartesian products (taken from @KevinCruijssen's 05AB1E answer). And another -1 by using the r flag to get rid of a $ that was needed for some weird reason (bug, probably).

Outputs 1 for unambiguous, 0 for ambiguous.

Explained

żvÞẊfÞu
ż        # The range [1, len(input)]
 vÞẊ     # nth cartesian power of the input for each number in that range
    fÞu  # are all the items unique?

Answer 9

T-SQL, 156 bytes

Returns 1 when ambiguous, 0 when unambiguous

WITH C(z,y)AS(SELECT*,*FROM @
UNION ALL SELECT','+z+','+x+',',+x
FROM C,@ D WHERE z not
like'%,'+x+',%')SELECT
top 1~(-1/sum(1))FROM
C GROUP BY y ORDER BY 1

Try it online