import sys
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.add('?')
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):
machines, emit, text = state
return "(" + ", ".join([format_machine(strings[sidx], offset) for sidx, offset in machines]) + \
f" {' EMIT' if emit else ''} '{text}')"
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, emit, text)), ix, spans, text) for (ix, state, spans, emit, text) in active_states])
def unify_spans(spans):
res = []
for span in spans:
off, ext = span
x1, x2 = off, off + ext
print(f"Inserting span {x1},{x2}")
new_res = []
for off, ext in res:
y1, y2 = off, off + ext
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- y1))
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 - y1))
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 - x1))
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
def generate_states(*strings, mask_pattern="MASK"):
states = [((), False, '')]
active_states = [(0, (), (), False, "")]
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, spans, emit, text) in active_states:
print(f"Processing state {format_state(strings, (machines, emit, text))}")
actions = generate_actions(strings, machines)
print(f"Actions available {actions}")
for action in actions:
new_machines = []
print(f"Processing action {action}")
ended = []
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}")
ended.append(sidx)
for sidx in range(len(strings)):
if strings[sidx][0] == action:
print(f"New machine for {sidx}")
new_machines.append((sidx, 1))
new_extent = max([0] + [offset for sidx, offset in new_machines])
prev_extent = max([0] + [offset for sidx, offset in machines])
delta = new_extent - prev_extent - 1
print(f"Prev extent {prev_extent} New extent {new_extent} Delta {delta}")
new_spans = [ (offset + delta, extent) for offset, extent in spans ]
for sidx in ended:
new_spans.append((new_extent - len(strings[sidx]), len(strings[sidx])))
if emit:
new_spans.append(((new_extent - len(text) - 1), 1))
print(f"Have new spans {new_spans}")
new_unified_spans = unify_spans(new_spans)
print(f"Unified spans to give {new_unified_spans}")
emitted = []
new_filtered_spans = []
last_offset = 0
for (offset, extent) in new_unified_spans:
if offset + extent <= 0:
emitted.append((offset, extent))
else:
new_filtered_spans.append((offset, extent))
last_offset = min(offset, last_offset)
print(f"Last offset: {last_offset}")
print(f"Emitting spans {emitted}")
print(f"Kept spans {new_filtered_spans}")
new_text = text + action
text_origin = new_extent - len(new_text)
limit = min(last_offset - text_origin, -text_origin)
print(f"Had full text '{new_text}' clipped to '{new_text[limit:]}' by limit {limit}")
emitted_text = ""
if limit > 0:
if emit:
emit = False
emitted_text += mask(new_text[:limit], emitted)
print(f"Masked text is {emitted_text}")
new_text = new_text[limit:]
new_filtered_spans.sort()
print(f"Have text origin {text_origin}, nfs {new_filtered_spans[0] if len(new_filtered_spans) > 0 else 'nothing'}")
if len(new_filtered_spans) > 0 and new_filtered_spans[0][0] == text_origin:
(start, extent) = new_filtered_spans[0]
print(f"Setting EMIT flag for ({start}, {extent})")
emit = True
new_text = new_text[extent-1:]
print(f"Clipped text to {new_text}")
new_filtered_spans.pop(0)
new_machines.sort()
state = (tuple(new_machines), emit, new_text)
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, tuple(new_machines), new_filtered_spans, emit, new_text))
changes = True
links.add((old_ix, ix, action, emitted_text))
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, e) in links:
print("{} -> {} via {} emitting {}".format(
format_state(strings, states[f]),
format_state(strings, states[t]),
a,
e)
)
return states, links
if __name__ == "__main__":
s, l = generate_states("abcd", "1ab", "aa")