Standard Graph Approaches

2019J5.py

# question can be easily framed into graph pathfinding
# parse inputs
def generated_nexts(current, rules): # has to return rule_id, index and result
    for rule_index in range(len(rules)):
        a, b = rules[rule_index]
        a_length = len(a)
        for i in range(len(current) - a_length + 1): # we add one because a is the from
            if a == current[i:i + a_length]: # this is a match, we found a position to apply the rule
                result = current[:i] + b + current[i + a_length:]
                yield rule_index + 1, i + 1, result # very special, but ugly syntax (sorry D:)
                # without this yield, we can do it by initializing a list
                    # nexts = []
                    # and do nexts.append((rule_index + 1, i + 1, result))
                    # this is okay, but quite a bit slower
                # btw thing to note, we can just not use a function and do this in place on line 44.
                # this eliminates the purpose of yield and itll still give a big performance boost im pretty sure
                # but it'll make your code less readable

rules = []
for _ in range(3):
    a, b = input().split()
    rules.append((a, b))
S, I, F = input().split()

S = int(S)
# apply the graph form
# DFS is fine since we are not looking for the shortest path
# but rather a fixed length path
# defining what goes on the stack is key
stack = [(I, [])] # current, steps thus far
# let's define what is a step?
    # a step is a rule id, index, result
# let's not worry about cycles for now, since we are looked for a fixed path.
visited = set() # we're using visited because this helps us optimize some obvious bad paths
# we can add some obviously bad scenarios into visited, which i'll be skipping for now
# i THINK this is still already fast enough for this year anyway, if not feel free to optimize

while len(stack) > 0:
    current, steps = stack.pop()
    # we need to get nexts, which we can use a function for
    if len(steps) == S and current == F:
        for rule_id, index, result in steps:
            print(f"{rule_id} {index} {result}")
        break
    elif len(steps) < S: # still more steps to take
        for rule_id, index, result in generated_nexts(current, rules):
            if(result, len(steps)) not in visited: 
                new_steps = steps[:]
                new_steps.append((rule_id, index, result))
                stack.append((result, new_steps))
    # that'll be it!
    # the key thing to note, is that this is a very standard graph traversal (while loop, pop, test for success and continue searching)
    # the only thing difficult is how do we generate nexts.