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:
- Cyclic shift: pop a letter from the beginning, and push it to the end.
- Commutator swap: if the word begins with two letters that appear in
Lin either order, swap those letters.
For example, the words
dcaba are cyclically equivalent over
L, since we have the sequence of operations
acabd -> caabd -> aabdc -> abdca -> badca -> adcab -> dcaba. However, the words
acdab are not cyclically equivalent, since the letters
d cannot be swapped with each other, so they can occur only in the order
bdc in words that are cyclically equivalent to
You are given as input two words, and a list of commutators. You program should output a truth-y value (
1, etc.) if the words are cyclically equivalent over the list, and a false-y value (
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.
[(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
- 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.