19
\$\begingroup\$

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 , so shortest answer (in bytes, per language) wins.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Related: codegolf.stackexchange.com/questions/48775/… \$\endgroup\$
    – mousetail
    Commented Nov 4, 2022 at 19:21
  • 1
    \$\begingroup\$ Suggested ambiguous test case: [xxx, xxxxx]. \$\endgroup\$
    – Arnauld
    Commented Nov 4, 2022 at 21:08
  • \$\begingroup\$ Suggested unambiguous test case: [a, ax, xx] \$\endgroup\$ Commented Nov 4, 2022 at 22:09
  • \$\begingroup\$ Suggested ambiguous test case [b+99a,100a+c,w,wb,acx,xba,aacy,ybaa,aaacz,zbaaa,aaaacd,d] (minimal ambiguous string longer than sum of substrings). \$\endgroup\$
    – loopy walt
    Commented Nov 5, 2022 at 11:55
  • \$\begingroup\$ @Arnauld Thanks, added! \$\endgroup\$ Commented Nov 5, 2022 at 19:21

9 Answers 9

8
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ Could you add a quick explanation of the faster approach? \$\endgroup\$
    – Jonah
    Commented Nov 5, 2022 at 4:28
  • 1
    \$\begingroup\$ @Jonah I've added a commented version. \$\endgroup\$
    – Arnauld
    Commented Nov 5, 2022 at 10:54
8
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Function saves a few: Try it online! \$\endgroup\$
    – naffetS
    Commented Nov 5, 2022 at 2:25
  • \$\begingroup\$ (Oops, I didn't see you already had a test suite, so I made my own) \$\endgroup\$
    – naffetS
    Commented Nov 5, 2022 at 2:26
  • \$\begingroup\$ Thanks @Sʨɠɠan I saved a bunch going to a program but further golfs meant I should've gone back! \$\endgroup\$ Commented Nov 5, 2022 at 2:41
  • \$\begingroup\$ Does that work for @Arnauld's test case 'xxxxx','xxx' (ambiguous string is longer [EDIT equal length but examples with longer can be constructed, too] than sum of atoms)? \$\endgroup\$
    – loopy walt
    Commented Nov 5, 2022 at 11:46
  • \$\begingroup\$ @loopywalt, it should (I think?) but it seems I must have deleted a 1 at some point during golfing and all tests I was using would have carried on passing; updated. \$\endgroup\$ Commented Nov 5, 2022 at 19:45
5
\$\begingroup\$

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!

\$\endgroup\$
4
  • \$\begingroup\$ for j,k in q saves a couple bytes \$\endgroup\$
    – ovs
    Commented Nov 4, 2022 at 23:53
  • \$\begingroup\$ Nice solution. I found a couple of golfs and kept going, will post separately as it was quite a bit :) \$\endgroup\$ Commented Nov 5, 2022 at 2:01
  • \$\begingroup\$ I tried to simplify this and ended up with this - does that really work? \$\endgroup\$
    – Neil
    Commented Nov 5, 2022 at 10:39
  • 1
    \$\begingroup\$ @Neil If so, that can be golfed to 104 \$\endgroup\$
    – naffetS
    Commented Nov 5, 2022 at 19:44
4
\$\begingroup\$

Charcoal, 34 bytes

WS⊞υι¹≔⮌υθFθFυ¿№θ⁺ικ⎚¿‹LιL⪫υω⊞θ⁺ικ

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...

WS⊞υι

Input the substrings.

¹

Assume they are unambiguous.

≔⮌υθFθ

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

Fυ¿№θ⁺ικ⎚

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

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

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

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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?
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.