In this kata, you need to make a (simplified) LZ78 encoder and decoder.
[LZ78](https://en.wikipedia.org/wiki/LZ77_and_LZ78#LZ78) is a dictionary-based compression method created in 1978. You will find a  detailed explanation about how it works below.

The input parameter will always be a non-empty string of upper case alphabetical characters. The maximum decoded string length is 1000 characters.


# Instructions

*If anyone has any ideas on how to make the instructions shorter / clearer, that would be greatly appreciated.*

If the below explanation is too confusing, just leave a comment and I'll be happy to help.

---

The input is looked at letter by letter.
Each letter wants to be matched with the longest dictionary substring at that current time.

The output is made up of tokens.
Each token is in the format ``
where `index` is the index of the longest dictionary value that matches the current substring
and `letter` is the current letter being looked at.


Here is how the string `'ABAABABAABAB'` is encoded:


* First, a dictionary is initialised with the 0th item pointing to an empty string:

```md
Dictionary      Input             Output
0  |  ''        ABAABABAABAB
```

* The first letter is `A`. As it doesn't appear in the dictionary, we add `A` to the next avaliable index.
The token `<0, A>` is added to the output:

```md
Dictionary      Input             Output

0  |  ''        ABAABABAABAB      <0, A>
1  |  A         ^
```

* The second letter is `B`. It doesn't appear in the dictionary, so we add `B` to the next avaliable index.
The token `<0, B>` is added to the output:

```md
Dictionary      Input             Output

0  |  ''        ABAABABAABAB      <0, A> <0, B>
1  |  A          ^
2  |  B
```

* The third letter is `A` again: it already appears in the dictionary at position `1`. We add the next letter which is also `A`. `AA` doesn't appear in the dictionary, so we add it to the next avaliable index.
The token `<1, A>` is added to the output:

```md
Dictionary      Input             Output

0  |  ''        ABAABABAABAB      <0, A> <0, B> <1, A>
1  |  A           ^^
2  |  B
3  |  AA
```

* The next letter is `B` again: it already appears in the dictionary at position `2`. We add the next letter which is `A`. `BA` doesn't appear in the dictionary, so we add it to the next avaliable index.
The token `<2, A>` is added to the output:

```md
Dictionary      Input             Output

0  |  ''        ABAABABAABAB      <0, A> <0, B> <1, A> <2, A>
1  |  A             ^^
2  |  B
3  |  AA
4  |  BA
```

* The next letter is `B`: it already appears in the dictionary and at position `2`. We add the next letter which is `A`. `BA` already appears in the dictionary at position `4`. We add the next letter which is `A`. `BAA` doesn't appear in the dictionary, so we add it to the next avaliable index.
The token `<4, A>` is added to the output:

```md
Dictionary      Input             Output

0  |  ''        ABAABABAABAB      <0, A> <0, B> <1, A> <2, A> <4, A>
1  |  A               ^^^
2  |  B
3  |  AA
4  |  BA
5  |  BAA
```

* The next letter is `B`. It already appears in the dictionary at position `2`. We add the next letter which is `A`. `BA` already appears in the dictionary at position `4`. We add the next letter which is `B`. `BAB` doesn't appear in the dictionary, so we add it to the next avaliable index.
The token `<4, B>` is added to the output:

```md
Dictionary      Input             Output

0  |  ''        ABAABABAABAB      <0, A> <0, B> <1, A> <2, A> <4, A> <4, B>
1  |  A                  ^^^
2  |  B
3  |  AA
4  |  BA
5  |  BAA
6  |  BAB
```

* We have now reached the end of the string. We have the output tokens: `<0, A> <0, B> <1, A> <2, A> <4, A> <4, B>`.
Now we just return the tokens without the formatting: `'0A0B1A2A4A4B'`

**Note:**

If the string ends with a match in the dictionary, the last token should only contain the index of the dictionary. For example, `'ABAABABAABABAA'` (same as the example but with `'AA'` at the end) should return `'0A0B1A2A4A4B3'` (note the final `3`).

To decode, it just works the other way around.


# Examples

Some more examples:
```
Decoded                               Encoded

ABBCBCABABCAABCAABBCAA                0A0B2C3A2A4A6B6
AAAAAAAAAAAAAAA                       0A1A2A3A4A
ABCABCABCABCABCABC                    0A0B0C1B3A2C4C7A6
ABCDDEFGABCDEDBBDEAAEDAEDCDABC        0A0B0C0D4E0F0G1B3D0E4B2D10A1E4A10D9A2C
```


Good luck :)

Difficulty: EASY

Starter code:
def encoder(data):
	

Solutions:
import re

def encoder(s):
	(d, out, it) = ({}, [], iter(s))
	for c in it:
		(i, k) = (0, c)
		while k in d:
			(i, c) = (d[k], next(it, ''))
			if not c:
				break
			k += c
		d[k] = len(d) + 1
		out.append(f'{i}{c}')
	return ''.join(out)

def decoder(s):
	d = ['']
	for m in re.finditer('(\\d+)(\\D?)', s):
		d.append(d[int(m[1])] + m[2])
	return ''.join(d)


def encoder(data):

	def get_key_by_value(value):
		for key in dictionary:
			if dictionary[key] == value:
				return key
	dictionary = {0: ''}
	dict_index = 1
	substring = ''
	encoded = []
	for char in data:
		substring += char
		if substring not in list(dictionary.values()):
			dictionary[dict_index] = substring
			encoded.append(str(get_key_by_value(substring[:-1])))
			encoded.append(substring[-1])
			dict_index += 1
			substring = ''
	if substring != '':
		encoded.append(str(get_key_by_value(substring)))
	return ''.join(encoded)

def decoder(data):
	dictionary = {0: ''}
	dict_index = 1
	decoded = []
	key = ''
	for char in data:
		if char.isdigit():
			key += char
		else:
			substring = dictionary[int(key)] + char
			dictionary[dict_index] = substring
			dict_index += 1
			decoded.append(substring)
			key = ''
	if key != '':
		decoded.append(dictionary[int(key)])
	return ''.join(decoded)


from re import findall

def encoder(data):
	base = ''
	dictionary = {base: 0}
	output = []
	for char in data:
		curr = base + char
		if curr in dictionary:
			base = curr
		else:
			output.append(f'{dictionary[base]}{char}')
			dictionary[curr] = len(dictionary)
			base = ''
	if base:
		output.append(f'{dictionary[base]}')
	return ''.join(output)

def decoder(data):
	dictionary = ['']
	for (idx, char) in findall('(\\d+)([A-Z]?)', data):
		dictionary.append(dictionary[int(idx)] + char)
	return ''.join(dictionary)


def encoder(data):
	(d, d_reverse) = ({0: ''}, {'': 0})
	(d_idx, data_idx) = (1, 0)
	while data_idx < len(data):
		if data[data_idx] not in d_reverse:
			d[d_idx] = '0' + data[data_idx]
			d_reverse[data[data_idx]] = d_idx
		else:
			start_idx = data_idx
			while data_idx + 1 < len(data) and data[start_idx:data_idx + 1] in d_reverse:
				data_idx += 1
			if data_idx == len(data) - 1:
				if data[start_idx:data_idx + 1] in d_reverse:
					d[d_idx] = str(d_reverse[data[start_idx:data_idx + 1]])
				else:
					d[d_idx] = str(d_reverse[data[start_idx:data_idx]]) + data[data_idx]
				break
			else:
				d[d_idx] = str(d_reverse[data[start_idx:data_idx]]) + data[data_idx]
				d_reverse[data[start_idx:data_idx + 1]] = d_idx
		data_idx += 1
		d_idx += 1
	return ''.join([v for (k, v) in list(d.items()) if k != 0])

def decoder(data):
	(d, s) = ([], [])
	for i in range(len(data)):
		if i == len(data) - 1 and data[i].isdigit():
			s.append(data[-1])
			d.append([int(''.join(s)), ''])
		if data[i].isalpha():
			d.append([int(''.join(s)), data[i]])
			s = []
		else:
			s.append(data[i])
	d_list = []
	for i in range(len(d)):
		if i == len(d) - 1 and (not d[i][1]):
			d_list.append(d_list[d[i][0] - 1])
			break
		if d[i][0] == 0:
			d_list.append(d[i][1])
		else:
			d_list.append(d_list[d[i][0] - 1] + d[i][1])
	return ''.join(d_list)


import re

def encoder(s):
	(d, numbers, i, li) = ({}, iter(range(1, 1000)), 0, [])
	while i < len(s):
		symbol = s[i]
		prev = 0
		while symbol in d:
			i += 1
			prev = d[symbol]
			if i == len(s):
				return ''.join(li) + str(d[symbol])
			symbol += s[i]
		d[symbol] = next(numbers)
		li.append(str(prev) + s[i])
		i += 1
	return ''.join(li)

def decoder(s):
	(parts, numbers, d, li) = (re.findall('\\d+[A-Z]', s), iter(range(1, 1000)), {}, [])
	for i in parts:
		if re.fullmatch('\\d+\\w', i):
			t = re.findall('(\\d+)(\\w)', i)
			(k, l) = (int(t[0][0]), t[0][1])
			if not k:
				d[next(numbers)] = l
				li.append(l)
			else:
				d[next(numbers)] = d[k] + l
				li.append(d[k] + l)
		else:
			li.append(d[int(i)])
	p = len(s) - len(''.join(parts))
	return ''.join(li) + (d[int(s[-p:])] if s[-p:].isdigit() else '')


def encoder(data):
	(d, c, o) = ([''], '', '')
	for i in data:
		(d, c, o) = (d, c + i, o) if c + i in d else (d + [c + i], '', o + str(d.index(c)) + i)
	return o + (str(d.index(c)) if c else '')

def decoder(data):
	(d, c, o) = ([''], '', '')
	for i in data:
		(d, c, o) = (d, c + i, o) if i in '0123456789' else (d + [d[int(c)] + i], '', o + d[int(c)] + i)
	return o + (d[int(c)] if c else '')


import re

def encoder(data):
	dct = {'': 0}
	search = ''
	output = ''
	for i in range(len(data)):
		search += data[i]
		if search not in dct:
			dct[search] = len(dct)
			output += f'{dct[search[:-1]]}{search[-1]}'
			search = ''
		try:
			search + data[i + 1]
		except IndexError:
			if search == data[-len(search):]:
				output += f'{dct[search]}'
	return output

def decoder(data):
	dct = {0: ''}
	output = ''
	lsnb = re.findall('\\d+', data)
	lsch = re.findall('[A-Z]', data)
	for i in range(len(lsnb)):
		try:
			lsch[i]
			dct[len(dct)] = dct[int(lsnb[i])] + lsch[i]
			output += dct[len(dct) - 1]
		except IndexError:
			output += dct[int(lsnb[i])]
	return output


import re

def encoder(s):
	(d, i, r) = ({'': 0}, 0, [])
	while i < len(s):
		x = ''
		while i < len(s) - 1 and x + s[i] in d:
			x += s[i]
			i += 1
		if x + s[i] not in d:
			d[x + s[i]] = len(d)
			r.append((d[x], s[i]))
		else:
			r.append((d[x + s[i]], ''))
		i += 1
	return ''.join((str(x) + y for (x, y) in r))

def decoder(s):
	(a, r) = ([''], [])
	for (x, y) in re.findall('(\\d+)(\\D*)', s):
		a.append(a[int(x)] + y)
	return ''.join(a)


import re

def encoder(data):
	dictionary = {'': 0}
	output = []
	index = 1
	longest_match = ''
	substring = ''
	for character in data:
		substring += character
		if substring not in dictionary:
			dictionary[substring] = index
			output.append((dictionary[longest_match], character))
			longest_match = ''
			substring = ''
			index += 1
		else:
			longest_match += character
	if substring in dictionary and substring != '':
		output.append((dictionary[substring], ''))
	return ''.join((str(i) + j for (i, j) in output))

def decoder(data):
	dictionary = {0: ''}
	last = re.search('(\\d*)$', data).group()
	data = re.findall('(\\d+)([A-Z])', data)
	if last != '':
		data.append((last, ''))
	index = 1
	for pair in data:
		dictionary[index] = dictionary[int(pair[0])] + pair[1]
		index += 1
	return ''.join(dictionary.values())


def encoder(data):
	(dicto, store, i, f) = ({0: ''}, '', 0, '')
	save = 0
	while i <= len(data):
		if i == len(data) and store in list(dicto.values()):
			for k in dicto:
				if dicto[k] == store and store != '':
					f += f'{k}'
			return f
		if store not in list(dicto.values()) and store != '':
			dicto[max(dicto.keys()) + 1] = store
			f += f'{save}{data[i - 1]}'
			store = ''
			if i == len(data):
				return f
			continue
		if data[i] not in list(dicto.values()) and store == '':
			save = 0
			for m in dicto:
				if dicto[m] == store:
					save = m
			dicto[max(dicto.keys()) + 1] = data[i]
			f += f'{save}{data[i]}'
			i += 1
		else:
			for m in dicto:
				if dicto[m] == store:
					save = m
				elif dicto[m] == data[i] and store == '':
					save = m
			store += data[i]
			i += 1
	return f

def decoder(data):
	(dc, dic) = ('', {0: ''})
	i = 0
	while i <= len(data) - 1:
		if data[i].isdigit() and i == len(data) - 1:
			dc += dic[int(data[i])]
			return dc
		if data[i] == '0':
			dc += data[i + 1]
			dic[max(dic.keys()) + 1] = data[i + 1]
			i += 1
		elif data[i] != '0' and data[i].isdigit() and (not data[i + 1].isdigit()):
			c = dic[int(data[i])] + data[i + 1]
			dc += c
			dic[max(dic.keys()) + 1] = c
			i += 1
		elif data[i].isdigit() and data[i + 1].isdigit():
			acc = data[i]
			while data[i + 1].isdigit():
				i += 1
				acc += data[i]
				if i + 1 == len(data):
					dc += dic[int(acc)]
					return dc
			dc += dic[int(acc)] + data[i + 1]
			dic[max(dic.keys()) + 1] = dic[int(acc)] + data[i + 1]
			i += 1
		else:
			i += 1
	return dc