A grammar is a set of rules that let us define a language. These are called **production rules** and can be derived into many different tools. One of them is **String Rewriting Systems** (also called Semi-Thue Systems or Markov Algorithms). Ignoring technical details, they are a set of rules that substitute ocurrences in a given string by other strings. 

The rules have the following format:

```
str1 -> str2
```

We define a rule application as the substitution of a substring following a rule. If this substring appears more than once, only one of this occurences is substituted and any of them is equally valid as an option:

```python
'a' -> 'c' # Substitution rule

'aba' # Base string
'cba' # One application on position 0
'abc' # One application on position 2
'cbc' # Two applications
```

Another valid example of rule application would be the following:

```python
# Rules
'l' -> 'de'
'm' -> 'col'
'rr' -> 'wakr'
'akr' -> 'ars'

# Application
'mrr' # Starting string
'colrr' # Second rule
'coderr' # First rule
'codewakr' # Third rule
'codewars' # Last rule 
```
Note that this example is exhaustive, but Semi-Thue Systems can be potentially infinite:

```python
# Rules
'a' -> 'aa'

# Application
'a' # Starting string
'aa' # First application
'aaa' # Second application
...
```

The so called **Word Problem** is to decide whether or not a string can be derived from another using these rules. This is an **undecidable problem**, but if we restrict it to a certain number of applications, we can give it a solution.

Your task is to write a function that solves the word problem given a maximum number of rule applications. 

**Python:** The rules are given as tuples where the left and the right handside of the rule correspond to the first and the second element respectively.

**Notes:** 
* Two rules can have the same left handside and a different right handside.
* You do not have to worry too much about performance yet. A simple, funtional answer will be enough.

Difficulty: introductory

Starter code:

def word_problem(rules:
	

Solutions:
def word_problem(rules: List[Tuple[str, str]], from_str: str, to_str: str, applications: int) -> bool:
    rec = lambda s,n: s == to_str or n and any(s[i:].startswith(x) and rec(s[:i] + y + s[i+len(x):], n-1) for i in range(len(s)) for x,y in rules)
    return rec(from_str, applications)

def word_problem(rules, start, to, N):
    q   = [(0,0,start)]
    for i,n,s in q:
        if s==to: return True
        if n<N and i<len(s):
            q.extend( (i, n+1, s[:i]+y+s[i+len(x):]) for x,y in rules if s[i:].startswith(x) )
            q.append( (i+1,n,s) )
    return False

from copy import deepcopy

def word_problem(rules: List[Tuple[str, str]], from_str: str, to_str: str, applications: int) -> bool:
    if applications == 0 or from_str == to_str:
        return from_str == to_str
    currentStrings = [from_str]
    for i in range(applications):
        # create all possible next strings from current string(s), using all rules
        nextStrings = []
        # iterate over all current strings
        for s in currentStrings:
            # determine all possible next strings
            for rule in rules:
                pos = 0
                while pos < len(s) and rule[0] in s[pos:]:
                    if s[pos:].startswith(rule[0]):
                        newString = s[:pos] + rule[1] + s[pos+len(rule[0]):]
                        if newString == to_str:
                            return True
                        if not newString in nextStrings:
                            nextStrings.append(newString)
                    pos += 1
        currentStrings = nextStrings
    return False


def word_problem(rules,f,t,a):
    if f==t:return True
    if a==0:
        return f==t
    return any(word_problem(rules,x,t,a-1)for r in rules for x in apply(r,f))

def apply(r,f):
    x,y=r
    l=len(x)
    for i in range(len(f)-l+1):
        if f[i:i+l]==x:
            yield f[:i]+y+f[i+l:]

def word_problem(
    rules: List[Tuple[str, str]], 
    from_str: str, 
    to_str: str, 
    applications: int
) -> bool:

    def recurse(from_str, applications) -> bool:
        if from_str == to_str:
            yield True
        elif applications == 0:
            yield False
        else:
            for f, t in rules:
                i = from_str.find(f)
                while i > -1:
                    yield from recurse(
                        from_str[:i] + t + from_str[i + len(f):],
                        applications - 1
                    )
                    i = from_str.find(f, i + 1)
    
    return any(recurse(from_str, applications))


import re

def replacenth(string, elem, values, i):
    where = [m.start() for m in re.finditer(elem, string)][i-1]
    before = string[:where]
    after = string[where:]
    after = after.replace(elem, values, 1)
    newString = before + after
    return newString

def string_convertor(strings_options, tuples_options):
    new_list = []
    new_list.clear()
    
    for strings in strings_options:
        for elem, values in tuples_options:
            if elem in strings:
                count_strings = strings.count(elem)
                if count_strings == 1:
                    strings_options = strings.replace(elem, values, 1)
                    new_list.append(strings_options)
                else:
                    i = 0
                    while i != count_strings:
                        strings_options = replacenth(strings, elem, values, i)
                        new_list.append(strings_options)
                        i += 1    
        
    list_string_converted = new_list
    return list_string_converted


def word_problem(rules: List[Tuple[str, str]], from_str: str, to_str: str, applications: int) -> bool:

    if applications == 0:
        if from_str == to_str:
            return True
        else:
            return False

    elif applications >= 1:
        
        list_string_converted = from_str.split()
        nb_try = 0

        while nb_try <= applications:
            try:
                list_string_converted = list(set(string_convertor(list_string_converted, rules)))
                nb_try += 1
                
                if not list_string_converted:
                    return False
                
                for elem in list_string_converted:    
                    if elem == to_str :
                        return True
                    
                    elif elem != to_str and nb_try == applications+1:
                        return False
                    else:
                        pass
            except:
                pass


import re

# def replacenth(strings, elem, values, i):
#     find = strings.find(elem)
#     # If find is not -1 we have found at least one match for the substring
#     j = find != -1
#     # loop util we find the nth or we find no match
#     while find != -1 and j != i:
#         # find + 1 means we start searching from after the last match
#         find = strings.find(elem, find + 1)
#         j += 1
#     # If i is equal to n we found nth match so replace
#     if j == i:
#         return strings[:find] + values + strings[find+len(elem):]
#     return strings

def replacenth(string, elem, values, i):
    where = [m.start() for m in re.finditer(elem, string)][i-1]
    before = string[:where]
    after = string[where:]
    after = after.replace(elem, values, 1)
    newString = before + after
    return newString

def string_convertor(strings_options, tuples_options):
    new_list = []
    new_list.clear()
    
    for strings in strings_options:
        # Try to find the second string in tuple and replace in strings_options
        for elem, values in tuples_options:
            if elem in strings:
                count_strings = strings.count(elem)
                if count_strings == 1:
                    strings_options = strings.replace(elem, values, 1)
                    new_list.append(strings_options)
                else:
                    i = 0
                    while i != count_strings:
                        strings_options = replacenth(strings, elem, values, i)
                        new_list.append(strings_options)
                        i += 1
                    
        
    list_string_converted = new_list
    return list_string_converted


def word_problem(rules: List[Tuple[str, str]], from_str: str, to_str: str, applications: int) -> bool:

    print(("From", from_str, "to", to_str, "with", applications, "applications"))
    print(("Rules :", rules))

    if applications == 0:
        if from_str == to_str:
            return True
        else:
            return False

    elif applications >= 1:
        # Call string_convertor function the same number of times we've applications
        # except if before reaching this number we run out of options
        
        list_string_converted = from_str.split()
        print((list_string_converted, " -----------"))
        nb_try = 0

        while nb_try <= applications:
            try:
                print(("-while nb :", nb_try, "list cvd :", list_string_converted))
                # call the function and use list(set()) to remove doubles in list:
                list_string_converted = list(set(string_convertor(list_string_converted, rules)))
                nb_try += 1
                
                if not list_string_converted:
                    return False
                
                for elem in list_string_converted:    
                    if elem == to_str :
                        print(("Find it!", elem))
                        return True
                    
                    elif elem != to_str and nb_try == applications+1:
                        return False
                    else:
                        pass
            except:
                print("error")



from collections import deque

def replace(s, rule):
    res = set()
    i = s.find(rule[0], 0, len(s))
    while i != -1:
        res.add(s[:i] + rule[1] + s[i+len(rule[0]):])
        i = s.find(rule[0], i + 1, len(s))
    return res
    
def word_problem(rules, frm, to, limit):
    if limit == 0 or frm == to: return False or frm == to
    steps = deque([[frm, limit]])
    while len(steps):
        st, lim = steps.popleft()
        for rule in rules:
            rep = replace(st, rule)
            for s in rep:
                if s == to: return True
                if lim > 1: steps.append([s, lim - 1])
    return False

from collections import defaultdict

def word_problem(rules, from_str, to_str, applications):
    d = defaultdict(list)
    for x, y in rules:
        d[y].append(x)
    b, visited = False, set()
    def dfs(s, p=0):
        nonlocal b
        if s == from_str:
            b = p <= applications
            return
        if p >= len(to_str) or s in visited:
            return
        for i in range(0, len(s)):
            for j in range(i+1, len(s)+1):
                k = s[i:j]
                if k in d:
                    for v in d[k]:
                        dfs(s[:i] + v + s[j:], p + 1)
        visited.add(s)
    dfs(to_str)
    return b

def word_problem(r,s1,s2,c):
    if s1 == s2: return True
    ix = {s1}
    for _ in range(c):
        xi = set()
        for s in ix:
            for x,y in r:
                if x in s:
                    i = s.find(x)
                    while i != -1:
                        ns = s[:i] + y + s[i+len(x):]
                        if ns == s2: return True
                        xi.add(ns)
                        i = s.find(x,i+1)
        ix = xi
    return False