import re
from functools import reduce

subs = {
    "ac": "ca",
    "ad": "da",
    "bc": "cb",
    "bd": "db",
    "ce": "eca",
    "de": "edb",
    "cca": "ccae"
}

rev_subs = {v: k for k, v in subs.items()}
subs = {**subs, **rev_subs}

print(len(subs))

keys = list(subs.keys())
all_keys = reduce(lambda x, y: x + "|" + y, keys[1:], keys[0])

visited = set()


def equivalent(curr, goal):
    if curr == goal:
        return True

    if curr in visited:
        # print("already visited: ", curr)
        return False

    visited.add(curr)

    matches = [(m.start(), m.end()) for m in re.finditer(all_keys, curr)]

    for s, e in matches:
        if equivalent(curr[:s] + subs[curr[s:e]] + curr[e:], goal):
            print("replacing: ", curr[s:e], "->",
                  subs[curr[s:e]], " in ", curr)
            return True

    return False


print(equivalent("bccdbc", "cbabd"))
print("\n\n")


print(equivalent("cadbcedb", "caccaebd"))
print("\n\n")

print(equivalent("aecdab", "cade"))
print("aecdab")