Unicode Transformation Format – 8-bit
As the name suggests UTF-8 was designed to encode data in a stream of bytes.

It works by splitting the bits up in multiples of eight. This is achieved by inserting headers to mark in how many bytes the bits were split. If the bits need to be split in two, the header `110` is added as prefix leaving five bits of the byte for the rest of the data. Followed by a continuation byte.

A continuation byte always start with `10` leaving six bits for data.
For a three-way split: the header `1110` is added with two continuation bytes and for four: `11110` with three continuation bytes. The number of ones at the start of the first byte denotes the number of bytes the data was split in.
# Task
Your task is to write two functions:
1. `to_utf8_binary`: which encodes a string to a bitstring using UTF-8 encoding.
2. `from_utf8_binary`: which does the reverse.

- Layout of UTF-8 byte sequences:
```
# BYTES  FIRST CODE POINT  LAST CODE POINT    BYTE 1      BYTE 2      BYTE 3      BYTE 4
    1                   0              127    0xxxxxxx  
    2                 128             2047    110xxxxx    10xxxxxx
    3                2048            65535    1110xxxx    10xxxxxx    10xxxxxx  
    4               65536          1114111    11110xxx    10xxxxxx    10xxxxxx    10xxxxxx
```

# Examples
```
ENCODE
 A  -> 1000001         -> 01000001
 八 -> 101000101101011 -> 1110-0101 10-000101 10-101011
 
DECODE
 110-00010 10-100111                     -> 10100111          -> §
 11110-000 10-010000 10-001010 10-001100 -> 10000001010001100 -> 𐊌
```
* Spaces and hyphens just for clarity
- https://en.wikipedia.org/wiki/UTF-8#Encoding

Difficulty: EASY
Tags: String algorithms

Starter code:
def to_utf8_binary(string):
	

Solutions:
from textwrap import wrap

def to_utf8_binary(string):
	return ''.join((format(x, 'b').rjust(8, '0') for x in bytearray(string, 'utf-8')))

def from_utf8_binary(bitstring):
	return bytearray([int(t, 2) for t in wrap(bitstring, 8)]).decode()


def to_utf8_binary(string):
	return ''.join(('{:08b}'.format(b) for b in string.encode('utf8')))

def from_utf8_binary(bitstring):
	import re
	return bytes((int(b, 2) for b in re.split('(........)', bitstring) if b)).decode('utf-8')


import re

def to_utf8_binary(string):
	s = ''
	for c in string:
		r = bin(ord(c))[2:]
		if len(r) < 8:
			s += '0' + r.zfill(7)
		elif len(r) < 12:
			t = r.zfill(11)
			s += '110{}10{}'.format(t[:5], t[5:])
		elif len(r) < 17:
			t = r.zfill(16)
			s += '1110{}10{}10{}'.format(t[:4], t[4:10], t[10:])
		elif len(r) < 22:
			t = r.zfill(21)
			s += '11110{}10{}10{}10{}'.format(t[:3], t[3:9], t[9:15], t[15:])
	return s

def from_utf8_binary(bitstring):
	s = ''
	for i in re.findall('0([01]{7})|110([01]{5})10([01]{6})|1110([01]{4})10([01]{6})10([01]{6})|11110([01]{3})10([01]{6})10([01]{6})10([01]{6})', bitstring):
		s += chr(int(''.join(i), 2))
	return s


def to_utf8_binary(s):
	return ''.join(('{:08b}'.format(x) for x in bytearray(s, 'utf-8')))

def from_utf8_binary(s):
	bs = []
	for i in range(0, len(s), 8):
		bs.append(int(s[i:i + 8], 2))
	return bytearray(bs).decode('utf-8')


def to_utf8_binary(string):
	bitstring = ''
	for char in string:
		code = ord(char)
		if code < 128:
			bitstring += ('0000000000' + bin(code)[2:])[-8:]
		elif code < 2048:
			binary = ('0' * 12 + bin(code)[2:])[-11:]
			bitstring += '110' + binary[0:5] + '10' + binary[5:11]
		elif code < 65536:
			binary = ('0' * 16 + bin(code)[2:])[-16:]
			bitstring += '1110' + binary[0:4] + '10' + binary[4:10] + '10' + binary[10:16]
		else:
			binary = ('0' * 21 + bin(code)[2:])[-21:]
			bitstring += '11110' + binary[0:3] + '10' + binary[3:9] + '10' + binary[9:15] + '10' + binary[15:21]
	return bitstring

def from_utf8_binary(bitstring):
	string = ''
	(i, t) = (0, len(bitstring))
	while i < t:
		bit_code = ''
		char_bit = bitstring[i:i + 8]
		i += 8
		if char_bit.startswith('11110'):
			bit_code += char_bit[5:8]
			for j in range(0, 3):
				char_bit = bitstring[i:i + 8]
				bit_code += char_bit[2:8]
				i += 8
		elif char_bit.startswith('1110'):
			bit_code += char_bit[4:8]
			for j in range(0, 2):
				char_bit = bitstring[i:i + 8]
				bit_code += char_bit[2:8]
				i += 8
		elif char_bit.startswith('110'):
			bit_code += char_bit[3:8]
			for j in range(0, 1):
				char_bit = bitstring[i:i + 8]
				bit_code += char_bit[2:8]
				i += 8
		else:
			bit_code = '0' + char_bit[1:8]
		string += chr(int(bit_code, 2))
	return string


def to_utf8_binary(string):
	stList = list(string)
	bincodes = [toBin(c) for c in stList]
	return ''.join(bincodes)

def toBin(string):
	print(ord(string))
	a = bin(ord(string))[2:]
	if ord(string) <= 127:
		padded = a.zfill(8)
		return padded
	elif ord(string) <= 2047:
		padded = a.zfill(11)
		return '110' + padded[:5] + '10' + padded[5:]
	elif ord(string) <= 65535:
		padded = a.zfill(16)
		part1 = '1110' + padded[:4]
		remaining = padded[4:]
		part2 = '10' + remaining[:6]
		remaining = remaining[6:]
		part3 = '10' + remaining
		return part1 + part2 + part3
	elif ord(string) <= 1114111:
		print(a)
		padded = a.zfill(21)
		part1 = '11110' + padded[:3]
		print(part1)
		remaining = padded[3:]
		part2 = '10' + remaining[:6]
		print(part2)
		remaining = remaining[6:]
		part3 = '10' + remaining[:6]
		remaining = remaining[6:]
		part4 = '10' + remaining[:6]
		return part1 + part2 + part3 + part4

def splitEveryN(n, li):
	return [li[i:i + n] for i in range(0, len(li), n)]

def getLenInByte(part):
	print(part)
	if part[0] == '0':
		return 1
	elif part[:3] == '110':
		print('two bytes')
		return 2
	elif part[:4] == '1110':
		return 3
	elif part[:5] == '11110':
		return 4

def from_utf8_binary(bitstring):
	li = splitEveryN(8, bitstring)
	i = 0
	result = []
	while i < len(li):
		bytelen = getLenInByte(li[i])
		nextbin = li[i:i + bytelen]
		joined = ''.join(nextbin)
		frombin = fromBin(joined)
		result += frombin
		i += bytelen
	return ''.join(result)

def fromBin(bitstring):
	if len(bitstring) <= 8:
		return chr(int(bitstring, 2))
	elif len(bitstring) <= 16:
		part1 = bitstring[3:8]
		part2 = bitstring[10:16]
		bi = part1 + part2
		return chr(int(bi, 2))
	elif len(bitstring) <= 24:
		part1 = bitstring[4:8]
		part2 = bitstring[10:16]
		part3 = bitstring[18:]
		return chr(int(part1 + part2 + part3, 2))
	elif len(bitstring) <= 32:
		part1 = bitstring[5:8]
		part2 = bitstring[10:16]
		part3 = bitstring[18:24]
		part4 = bitstring[26:]
		return chr(int(part1 + part2 + part3 + part4, 2))
	return ''


def utf8_char_to_binary(ch):
	string = str(bin(ord(ch)))[2:]
	if len(string) <= 7:
		return '0' + string.rjust(7, '0')
	(result, bts) = ([], 1)
	while len(string) + (bts + 1) > 8:
		bts += 1
		result.insert(0, '10' + string[-6:].rjust(6, '0'))
		string = string[:-6]
	return ''.join(['1' * bts + '0' + string.rjust(8 - bts - 1, '0')] + result)

def to_utf8_binary(string):
	return ''.join(map(utf8_char_to_binary, list(string)))

def bitstring_to_utf8_chr(bitstring):
	if len(bitstring) == 0:
		return ''
	if len(bitstring) == 8:
		return chr(int(bitstring, 2))
	else:
		binary = ''
		byte_parts = [bitstring[i:i + 8] for i in range(0, len(bitstring), 8)]
		binary += byte_parts[0][list(byte_parts[0]).index('0'):]
		for i in range(1, len(byte_parts)):
			binary += byte_parts[i][2:]
		return chr(int(binary, 2))

def from_utf8_binary(bitstring):
	bitstring = [bitstring[i:i + 8] for i in range(0, len(bitstring), 8)]
	(character_bitstring, final_string) = ('', '')
	for s in bitstring:
		if s[:2] == '10':
			character_bitstring += s
		elif s[0] == '0':
			final_string += bitstring_to_utf8_chr(character_bitstring) + bitstring_to_utf8_chr(s)
			character_bitstring = ''
		else:
			final_string += bitstring_to_utf8_chr(character_bitstring)
			character_bitstring = s
	return final_string + bitstring_to_utf8_chr(character_bitstring)


def to_utf8_binary(string):
	return ''.join((format(c, '08b') for c in string.encode()))

def from_utf8_binary(bitstring):
	bytes_ = [bitstring[i:i + 8] for i in range(0, len(bitstring), 8)]
	return bytes((int(byte, 2) for byte in bytes_)).decode()


def to_utf8_binary(string):
	return ''.join((bin(i)[2:].zfill(8) for i in string.encode('utf-8')))

def from_utf8_binary(bitstr):
	byte_str = bytes((int(bitstr[i:i + 8], 2) for i in range(0, len(bitstr), 8)))
	return byte_str.decode('utf-8')