def generate_actions(strings, machines):
res = set()
for (sidx, offset) in machines:
string = strings[sidx]
if offset < len(string):
res.add(string[offset])
for s in strings:
res.add(s[0])
res = list(res)
res.sort()
return res
def format_machine(s, offset):
res = ""
for i, ch in enumerate(s):
if i == offset:
res += "|"
res += ch
if offset == len(s):
res += "|"
return res
def format_machines(strings, machines):
return ', '.join([format_machine(strings[sidx], offset) for (sidx, offset) in machines])
def format_state(strings, state):
return "(" + ", ".join([format_machine(strings[sidx], offset) for sidx, offset in state]) + ")"
def format_states(strings, states):
return ", ".join([format_state(strings, state) for state in states])
def format_active_states(strings, active_states):
return ", ".join(["{} ({})".format(format_state(strings, state), ix) for ix, state in active_states])
def generate_states(*strings):
states = [()]
active_states = [(0, ())]
links = set()
changes = True
while changes:
changes = False
new_states = []
print(f"Beginning loop, active_states\n{format_active_states(strings, active_states)}\nall states\n{format_states(strings, states)}")
for (old_ix, machines) in active_states:
print(f"Processing state {format_state(strings, machines)}")
actions = generate_actions(strings, machines)
print(f"Actions available {actions}")
for action in actions:
new_machines = []
print(f"Processing action {action}")
longest_terminator = None
for (sidx, offset) in machines:
print(f"Processing machine {format_machine(strings[sidx], offset)}")
if offset < len(strings[sidx]):
if action == strings[sidx][offset]:
print(f"Machine advances")
new_machines.append((sidx, offset+1))
if offset+1 == len(strings[sidx]):
print(f"Saw terminator for {sidx}")
longest_terminator = offset+1 if longest_terminator is None else max(offset+1, longest_terminator)
for sidx in range(len(strings)):
if strings[sidx][0] == action:
print(f"New machine for {sidx}")
new_machines.append((sidx, 1))
new_machines.sort()
state = tuple(new_machines)
print(f"New state is {format_state(strings, state)}")
try:
ix = states.index(state)
except ValueError:
print("Adding to full state list, changes = true")
ix = len(states)
states.append(state)
new_states.append((ix, state))
changes = True
links.add((old_ix, ix, action, longest_terminator))
print()
active_states = new_states
print("Done")
print()
print(strings)
print("Complete states")
for state in states:
print(format_state(strings, state))
print()
print("Links")
for (f, t, a, m) in links:
print("{} -> {} via {}{}".format(
format_state(strings, states[f]),
format_state(strings, states[t]),
a,
"" if m is None else f" ENDING {m}")
)
return states, links
def parse_with_states(inp, states, links):
state = 0
spans = []
for i, ch in enumerate(inp):
for (f, t, a, m) in links:
if f != state:
continue
if ch == a:
if m is not None:
spans.append((i+1-m, i+1))
state = t
break
else:
state = 0
return spans
def unify_spans(spans):
res = []
for span in spans:
x1, x2 = span
print(f"Inserting span {x1},{x2}")
new_res = []
for y1, y2 in res:
print(f"Merging with span {y1},{y2}")
if x1 <= y1:
if x2 < y1:
print(f"{x1},{x2} is disjoint from {y1},{y2}")
new_res.append((y1, y2))
else:
x2 = max(x2, y2)
print(f"Unified spans into {x1}, {x2}")
else:
if y2 < x1:
print(f"{x1},{x2} is disjoint from {y1},{y2}")
new_res.append((y1, y2))
else:
x1 = y1
x2 = max(x2, y2)
print(f"Unified spans into {x1}, {x2}")
print(f"Inserting span {x1}, {x2}")
new_res.append((x1, x2))
res = new_res
return res
def mask(inp, spans):
last = 0
res = ""
for x1, x2 in spans:
res += inp[last:x1]
res += "MASKED"
last = x2
res += inp[last:]
return res
if __name__ == "__main__":
s, l = generate_states("abcd", "1ab", "cde", "bce", "aa")
for case in [ "1abcdef", "1a", "qqcdeblah" ]:
spans = parse_with_states(case, s, l)
print(f"{case} yield spans {spans}")
spans = unify_spans(spans)
print(f"{case} yield unified spans {spans}")
print(f"Have masked {mask(case, spans)}")