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.

Source: codewars | Difficulty: EASY
Tags: Mathematics

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):
		nextStrings = []
		for s in currentStrings:
			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(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:
	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:
		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))
				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