CCC 2019 Junior J5: Rule of Three Solution

https://cemc.uwaterloo.ca/contests/computing/2019/stage%201/juniorEF.pdf

1. Build two lists wordsrc and worddst to simulate a dictionary.

2. Because from source word to destination word, only can perform 15 steps, create a visited lists that are set , keep each steps words, the set will keep unique words generated from previous step.

3. Use DFS to do the generation.

4. There is auxiliary function "replace(...)", it generate a words list based source word by using the dictionary.

wordsrc = []
worddst = []

visited = [set(), set(), set(), set(), set(),set(), set(), set(), set(), set(),set(), set(), set(),set(), set(),set()]

for i in range(3):
    rss = input().split()
    wordsrc.append(rss[0])
    worddst.append(rss[1])

ss = input().split()
steps = int(ss[0])
src = ss[1]
dst = ss[2]

def replace(word, x, rn):
    list1 = []
    for i in range(len(word)):
        cpos = i
        j = 0
        while j < len(x) and cpos < len(word) and word[cpos] == x[j]:
            cpos += 1
            j += 1
        if j == len(x):
            newword = word[0:i] + worddst[rn] + word[cpos:]
            list1.append([rn+1, i+1, newword])
    return list1

def getdststring(cur,  curstep, records):
    if curstep > steps:
        return False
    if curstep == steps:
        if cur == dst:
            for x in records:
                print(x[0], x[1], x[2])
            return True
        return False
    if cur in visited[curstep]:
        return False
    for i in range(3):
        thelist = replace(cur,wordsrc[i], i)
        for y in thelist:
            tr= records.copy()
            tr.append(y)
            if getdststring(y[2], curstep+1, tr):
                return True
            else:
                visited[curstep+1].add(y[2])
    return False

getdststring(src, 0, [])