Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement