Cyclically Equivalent Words

Question

Cyclic Equivalence

Let L be a list of pairs of letters, for example [(a,b), (a,c)]. We call L a list of commutators. Two words are cyclically equivalent over L, if one can be transformed into the other using the following operations:

1. Cyclic shift: pop a letter from the beginning, and push it to the end.
2. Commutator swap: if the word begins with two letters that appear in L in either order, swap those letters.

For example, the words acabd and dcaba are cyclically equivalent over L, since we have the sequence of operations acabd -> caabd -> aabdc -> abdca -> badca -> adcab -> dcaba. However, the words acabd and acdab are not cyclically equivalent, since the letters b, c and d cannot be swapped with each other, so they can occur only in the order cbd, dcb or bdc in words that are cyclically equivalent to acbad.

The Challenge

You are given as input two words, and a list of commutators. You program should output a truth-y value (True, 1, etc.) if the words are cyclically equivalent over the list, and a false-y value (False, 0, etc.) otherwise. You don't have to output a sequence of operations in the positive case. The shortest answer (in bytes) is the winner.

Test Cases

[(a,b), (a,c)] acabd dcaba -> True
[(a,b), (a,c)] acabd acdab -> False
[(a,b), (a,d), (b,c), (b,d)] cdaddccabbdcddcababaaabbcbdccaccacdddacdbccbddaacccaddbdbbcadcccadadccbaaabdbcc ddcadbbcccdadbabcbcaadaccbbcdddaccdacddcababaaacbbdbccaccbacddadcdccaddabcbccda -> True
[(a,b), (a,d), (b,c), (b,d)] cdaddccabbdcddcababaaabbcbdcccacacdddacdbccbddaacccaddbdbbcadcccadadccbaaabdbcc ddcadbbcccdadbabcbcaadaccbbcdddaccdacddcababaaacbbdbccaccbacddadcdccaddabcbccda -> False

Clarifications

• You can write either a function or a STDIN-to-STDOUT program.
• The list of commutators can be given as a comma-separated string, a list of length-two strings, or a list of pairs of characters.
• You can assume that the input words only contain alphanumeric ASCII symbols.
• Your program should be able to process inputs of length 100 in a matter of seconds.
• Standard loopholes are disallowed.

Answer 1

Python 413

Pretty efficient, although it does sacrifice a small amount of speed for length, such as calculating things every pass of a small for loop rather than precalculating it. I̶t̶ ̶s̶t̶i̶l̶l̶ ̶o̶u̶t̶p̶u̶t̶s̶ ̶a̶l̶l̶ ̶t̶h̶e̶ ̶t̶e̶s̶t̶ ̶c̶a̶s̶e̶s̶ ̶i̶n̶ ̶w̶e̶l̶l̶ ̶u̶n̶d̶e̶r̶ ̶a̶ ̶s̶e̶c̶o̶n̶d̶.̶

Edit: I had to fix a bug which now makes it significantly less efficient for larger inputs.

X,Y,L=input();S=sorted;T=type
def E(s,c):
 l=[[]]
 for h in s:
    if h==c:l+=[h]
    elif all(h!=[b,a][j]for a,b in L for j,n in[(0,a),(1,b)]if n==c):
     if T(l[-1])==str:l+=[[]]
     l[-1]=S(l[-1]+[h])
 if T(l[0])==T(l[-1])!=str:return[l[0]+l[-1]]+l[1:-1]+[len(l[-1])]
 return l+[0]
print any(0==cmp(*[[E(s,c)for c in S(set(s))]for s in [X[j:]+X[:j],Y[i:]+Y[:i]]])for i in range(len(Y))for j in range(len(X)))

Test Cases

"acb", "abc", [('a','b')]
True (0 ms)

'acabd','dcaba',[('a','b'),('a','c')]
True (1 ms)

'acabd','acdab',[('a','b'),('a','c')]
False (2 ms)

'cdaddccabbdcddcababaaabbcbdccaccacdddacdbccbddaacccaddbdbbcadcccadadccbaaabdbcc','ddcadbbcccdadbabcbcaadaccbbcdddaccdacddcababaaacbbdbccaccbacddadcdccaddabcbccda',[('a','b'), ('a','d'), ('b','c'), ('b','d')]
True (62 ms)

'cdaddccabbdcddcababaaabbcbdcccacacdddacdbccbddaacccaddbdbbcadcccadadccbaaabdbcc','ddcadbbcccdadbabcbcaadaccbbcdddaccdacddcababaaacbbdbccaccbacddadcdccaddabcbccda',[('a','b'), ('a','d'), ('b','c'), ('b','d')]
False (6963 ms)

The basic algorithm does the following. For each letter, L, present, loop through the string constructing a list; anytime it encounters L it appends it to the list, any group of adjacent letters which can not be switched with L it appends to the list sorted, letters which can be switched with L are ignored.

For example when considering 'acabd' with the pairs [('a','b'),('a','c')], we would construct:

a : a, a, [d] 
b : [c], b, [d] *
c : c, [b,d] 
d : [a,a,b,c], d 

which is equivalent to the result we get when we apply this to 'cabad' ('dcaba' shifted)

*Note here that the [c] and [d] should be considered one list

What is basically being done, is confirming for each letter that the order of it and the letters it can't switch with are the same. Since they cannot switch, they cannot 'pass' each other, so if the first string has two as followed by two ds followed by one a followed by one d than no matter how it's manipulated it can't be transformed into a string which has three as followed by three ds. Of course the order of the letters that it can't switch with is not an issue (they might be paired with each other and switchable), but their counts are, hence the sorting of the lists before comparison. In addition it's clear that any letters that can be switched don't matter at all for the purposed of comparison.

Using this algorithm the program could be made significantly more efficient; currently it loops through every possible transposition of both strings and compares them due to some issues with comparing cases in which there were lists bordering the beginning and end.

Answer 2

Haskell, 409

not fully golfed yet.

import Data.List
r((c,h):s)|l<-r s,(x,y)<-partition(\s->any(`elem`s)[c,h])l=nub(c:h:concat x):y
r _=[]
k s d|l<-sort$nub s=r[(x,y)|x<-l,y<-l,notElem(x,y)d,notElem(y,x)d,x/=y]
m a b c|elem c[a,b]=c|0<1=' '
e s d=[nub[map(m x y)s|x<-g,y<-g,notElem(x,y)d,notElem(y,x)d,x/=y]|g<-k s d]
q a b=and$zipWith(\a b->or[n a==n[drop i s++take i s|s<-b]|i<-[0..length$a!!0]])a b
f a b d=q(e a d)(e b d)
n=map$filter(/=' ')

this works on all the test cases.