*Translations appreciated*

# Overview

Your task is to decode a qr code.
You get the qr code as 2 dimensional array, filled with numbers. 1 is for a black field and 0 for a white field.
It is always a qr code of version 1 (21*21), it is always using mask 0 ((x+y)%2), it is always using byte mode and it always has error correction level H (up to 30%). The qr code won't be positioned wrong and there won't be any squares for positioning exept the three big ones in the corners.

You should return the message inside the qr code as string.  
The QR Code will always be valid and be of `version 1`, meaning the decoded message will never be more than 8 characters long. The way to decode a complete QR-code is explained below, but keep in mind that in this kata, you'll only have to decode the parts in green in the picture below:




# Input/ouput

* Input: 2D array of `0` (white) and `1` (black) values
* Output: the decoded message, according to the process described below.

```python
qrcode = [[ 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1 ],
          [ 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1 ],
          [ 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1 ],
          [ 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1 ],
          [ 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1 ],
          [ 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1 ],
          [ 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1 ],
          [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
          [ 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1 ],
          [ 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1 ],
          [ 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1 ],
          [ 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0 ],
          [ 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0 ],
          [ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0 ],
          [ 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1 ],
          [ 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0 ],
          [ 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1 ],
          [ 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0 ],
          [ 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1 ],
          [ 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0 ],
          [ 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1 ]]

return "Hello"
```
```C
int qrcode[21][21] = {{ 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1 },
                      { 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1 },
                      { 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1 },
                      { 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1 },
                      { 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1 },
                      { 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1 },
                      { 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1 },
                      { 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                      { 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1 },
                      { 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1 },
                      { 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1 },
                      { 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0 },
                      { 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0 },
                      { 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0 },
                      { 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1 },
                      { 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0 },
                      { 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1 },
                      { 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0 },
                      { 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1 },
                      { 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0 },
                      { 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1 }};

return "Hello";
```



# Decoding a QR-code

Here comes the explaination on how to decode a qr code. You can skip it, if you already know how it works:

### Postionning information

First of all we have to take a look at the big three positioning fields in the corners.



You can see on the image that these fields are connected.  
The fields are just there for the positioning and I told before that the qr code will be always positioned correctly so you can ignore them.

### Mask information

The bits next to the positioning fields give us information about the mask and the error correction level the qr code uses. I wrote above that it is always mask 0 and always error correction level H, so we can also ignore that stuff.



### Reading information

Now we start with the important stuff. Go through the qr code like the red arrow shows on this picture (btw I made it with paint so don't judge me)
- We start in the lower right corner
- Then we go one to the left
- Then we go one up and one to the right
- And so on just look the red arrow

___Important:___ Remember that everything inside the blue boxes has another purpose than encoding information, so don't forget to skip those parts.



In the image below, you may find the complete pattern to read information in a QR-code. But keep in mind you'll be handling only "QR-code version 1", so you don't need to read the full set of data (see picture at the top if needed).



### Decoding information

We have to build a bit sequence now. In order to do that we will use mask 0 definition which is `((x+y)%2)==0`, where:
- x and y are the indexes of our 2 dimensional array (0-based)
- if the condition of our mask is true, we have to convert the pixel: black -> 0 and white -> 1
- A mask is used to prevent long sequences of identical bits so that a scanner can better recognize the code

For each black field add 1 to our bit sequence and for each white field add 0 to our bit sequence, don't forget that many bits get converted because of mask 0.

Let's do the first bits together:

* We start with the first pixel (in the lower right corner, where also the red arrow begins) which is black, but we have to use mask because (20+20)%2 is 0, therefore we don't add 1 to our bit sequence but 0.
* Next field is white. This time we don't use mask because (20+19)%2 isn't 0, so we add a 0 to our bit sequence.
* Next field is black. This time we don't use mask because (19+20)%2 isn't 0, so we add a 1 to our bit sequence.

Important (!): Since we're limiting ourselves to version 1, we have to continue that process only until our bit sequence is 76 long, because the input will never be longer than eight characters.

At the end you get a bit sequence:
```
bits:      0100000000100100100001101001000011101100000100011110110000010001111011001111
legend:    MMMMssssssss...

- "M": mode bits (4 bits)
- "s": size message bits (8 bits)
- ...: message bits and error correction information
```

This bit sequence is representing the following information
* First 4 bits show mode: `0100`. This isn't important for us, because I told you before that we will use always byte mode in this kata.
* The following 8 bits show the length of the encoded word: `00000010`. This is the binary representation of number 2, so we know our word is 2 characters long.
* The following bits are data bits followed by error correction bits (but you can ignore error correction bits, because there won't be any errors). We know our word is 2 chars long, so we take the next 16 bits (because 1 char=8 bits):
  - First group of 8 bits: `01001000`. This is `72` in decimal which is ascii value of `"H"`.
  - Second group of 8 bits: `01101001`. This is `105` in decimal which is ascii value of `"i"`.

Since we don't handle in this kata error correction, we got our word/output: `"Hi"`.

Good luck :)

Source: codewars | Difficulty: EASY

Starter code: def scanner(qrcode):
	

Solutions:
def scanner(qrc):
	bits = ''.join((str(qrc[x][y] ^ ((x + y) % 2 == 0)) for (x, y) in ticTocGen()))
	size = int(bits[4:12], 2)
	return ''.join((chr(int(bits[i:i + 8], 2)) for i in range(12, 12 + 8 * size, 8)))

def ticTocGen():
	(x, y, dx) = (20, 20, -1)
	while y > 13:
		yield from ((x, y - dy) for dy in range(2))
		x += dx
		if x == 8 or x > 20:
			dx *= -1
			y -= 2
			x = x == 8 and 9 or 20


def scanner(qrcode):
	(Y, X) = (len(qrcode) - 1, len(qrcode[0]) - 1)
	(x, y, dir) = (X, Y, -1)
	bits = ''
	while len(bits) < 76:
		for i in range(2):
			bits += str(qrcode[x][y - i] ^ ((x + y - i) % 2 == 0))
		x += dir
		if x == 8 or x > X:
			dir = dir * -1
			x += dir
			y -= 2
	size = int(bits[4:12], 2)
	return ''.join((chr(int(bits[i:i + 8], 2)) for i in range(12, size * 8 + 12, 8)))


def scan_column(qrcode, x0, y0, height, bottom_to_top=True):
	result = []
	if bottom_to_top:
		height_range = list(range(0, height * -1, -1))
	else:
		height_range = list(range(height))
	for dy in height_range:
		y = y0 + dy
		x = x0
		result.append(qrcode[y][x] ^ (x + y + 1) % 2)
		x = x0 - 1
		result.append(qrcode[y][x] ^ (x + y + 1) % 2)
	return result

def byte_to_int(byte):
	return int(''.join(map(str, byte)), 2)

def raw_data_to_str(raw_data):
	return ''.join([chr(byte_to_int(byte)) for byte in raw_data])

def scanner(qrcode):
	result = []
	result += scan_column(qrcode, 20, 20, 12, bottom_to_top=True)
	result += scan_column(qrcode, 18, 9, 12, bottom_to_top=False)
	result += scan_column(qrcode, 16, 20, 12, bottom_to_top=True)
	result += scan_column(qrcode, 14, 9, 12, bottom_to_top=False)
	encoding_raw = result[:4]
	length_raw = result[4:12]
	length = byte_to_int(length_raw)
	data_raw = [result[12 + 8 * i:12 + 8 * (i + 1)] for i in range(length)]
	data = raw_data_to_str(data_raw)
	return data


def coords():
	rs = range(9, 21)
	for c in [20, 16]:
		for i in reversed(rs):
			yield (i, c)
			yield (i, c - 1)
		for i in rs:
			yield (i, c - 2)
			yield (i, c - 3)

def scanner(qrcode):
	it = (qrcode[r][c] ^ 1 - (r + c) % 2 for (r, c) in coords())
	bstring = ''.join(map(str, it))
	offset = 12
	length = int(bstring[4:offset], 2)
	bstring = bstring[offset:offset + length * 8]
	return ''.join((chr(int(''.join(xs), 2)) for xs in zip(*[iter(bstring)] * 8)))


from itertools import islice
get_byte = lambda it: int(''.join(islice(it, 8)), 2)

def scanner(qrcode):

	def next_bit():
		(i, j) = (18, 20)
		while True:
			yield str(i & 1 ^ j & 1 ^ qrcode[i][j] ^ 1)
			if j % 2 == 0 or (i == 9 and j % 4 == 3) or (i == 20 and j % 4 == 1):
				j -= 1
			else:
				i += 1 if j % 4 == 1 else -1
				j += 1
	bits = next_bit()
	return ''.join((chr(get_byte(bits)) for _ in range(get_byte(bits))))


def scanner(qrcode):
	finding_patterns = {((0, 9), (0, 9)), ((len(qrcode) - 8, len(qrcode)), (0, 9)), ((0, 9), (len(qrcode) - 8, len(qrcode)))}
	timing_patterns = {((9, len(qrcode) - 8), (6, 7)), ((6, 7), (9, len(qrcode) - 8))}
	function_patterns = {(x, y) for ((x0, x1), (y0, y1)) in finding_patterns | timing_patterns for x in range(x0, x1) for y in range(y0, y1)}
	reading = ((x, 2 * y - (y < 4) - i) for y in range(len(qrcode) // 2, 0, -1) for x in (reversed, iter)[y % 2](list(range(len(qrcode)))) for i in range(2))
	bits = ''.join((str((x + y ^ ~qrcode[x][y]) & 1) for (x, y) in reading if (x, y) not in function_patterns))
	return bytes((int(bits[i:i + 8], 2) for i in range(12, 12 + int(bits[4:12], 2) * 8, 8))).decode()


import re

def scanner(q):
	(bitseq, mask) = ([], [])
	for row in range(20, 8, -1):
		bitseq.append(q[row][20])
		mask.append((row + 20) % 2 == 0)
		bitseq.append(q[row][19])
		mask.append((row + 19) % 2 == 0)
	for row in range(9, 21, 1):
		bitseq.append(q[row][18])
		mask.append((row + 18) % 2 == 0)
		bitseq.append(q[row][17])
		mask.append((row + 17) % 2 == 0)
	for row in range(20, 8, -1):
		bitseq.append(q[row][16])
		mask.append((row + 16) % 2 == 0)
		bitseq.append(q[row][15])
		mask.append((row + 15) % 2 == 0)
	for row in range(9, 11, 1):
		bitseq.append(q[row][14])
		mask.append((row + 14) % 2 == 0)
		bitseq.append(q[row][13])
		mask.append((row + 13) % 2 == 0)
	code = [int(not x) if mask[i] else x for (i, x) in enumerate(bitseq)]
	length = int(''.join(map(str, code[4:12])), 2)
	return ''.join([chr(int(x, 2)) for x in re.findall('[01]{8}', ''.join(map(str, code[12:8 * length + 12])))])


def scanner(qrcode):
	result = ''
	dict = {1: 0, 0: 1}
	(x, y) = (20, 20)
	bool = True
	dir = 'Up'
	i = 2
	count = 0
	while count < 6:
		while x > 8 and dir == 'Up':
			if (x + y) % 2 == 0:
				result += str(dict[qrcode[x][y]])
			else:
				result += str(qrcode[x][y])
			if bool:
				y -= 1
				bool = False
			else:
				x -= 1
				y += 1
				bool = True
			if x == 8:
				x = 9
				y = 20 - i
				i += 2
				dir = 'Down'
				bool = True
		print(result)
		count += 1
		if count == 5:
			break
		else:
			while x < 21 and dir == 'Down':
				if (x + y) % 2 == 0:
					result += str(dict[qrcode[x][y]])
				else:
					result += str(qrcode[x][y])
				if bool:
					y -= 1
					bool = False
				else:
					x += 1
					y += 1
					bool = True
				if x == 21:
					x = 20
					y = 20 - i
					i += 2
					dir = 'Up'
					bool = True
			count += 1
			print(result)
	len = int(result[4:12], 2)
	ans = ''
	for i in range(len):
		ans += chr(int(result[12 + i * 8:20 + i * 8], 2))
	return ans


def scanner(qrcode):
	bitstring = ''
	row = 20
	row_iter = -1
	col = 20
	col_iter = 0
	while not (row == 13 and col == 0):
		if not (row <= 8 and col <= 8 or (row <= 8 and col >= 13) or (row >= 13 and col <= 8) or (row == 6) or (col == 6)):
			if (row + col - col_iter) % 2 == 0:
				bitstring += str(1 - qrcode[row][col - col_iter])
			else:
				bitstring += str(qrcode[row][col - col_iter])
		else:
			pass
		row = row + row_iter * col_iter
		col_iter = 1 - col_iter
		if (row == -1 or row == 21) and col_iter == 0:
			row_iter = row_iter * -1
			row += row_iter
			col -= 2
	str_length = int(bitstring[4:12], 2)
	bitstring = bitstring[12:]
	chars = []
	for b in range(0, str_length):
		byte = bitstring[b * 8:(b + 1) * 8]
		chars.append(chr(int(byte, 2)))
	return ''.join(chars)


def up(x0, y0):
	return tuple(((x, y) for y in range(y0 + 3, y0 - 1, -1) for x in (x0 + 1, x0)))

def down(x0, y0):
	return tuple(((x, y) for y in range(y0, y0 + 4) for x in (x0 + 1, x0)))

def top(x0, y0):
	return ((x0 + 3, y0 + 1), (x0 + 2, y0 + 1)) + tuple(((x, y0) for x in range(x0 + 3, x0 - 1, -1))) + ((x0 + 1, y0 + 1), (x0, y0 + 1))

def bot(x0, y0):
	return ((x0 + 3, y0), (x0 + 2, y0)) + tuple(((x, y0 + 1) for x in range(x0 + 3, x0 - 1, -1))) + ((x0 + 1, y0), (x0, y0))
modebits = ((20, 20), (19, 20), (20, 19), (19, 19))
lenbits = up(19, 15)
bits = (up(19, 11), top(17, 9), down(17, 11), down(17, 15), bot(15, 19), up(15, 15), up(15, 11), top(13, 9), down(13, 11), down(13, 15), bot(11, 19), up(11, 15), up(11, 11), up(11, 7), up(11, 2), top(9, 0), down(9, 2))

def num(code, bits):
	n = 0
	for (x, y) in bits:
		n = (n << 1) + (code[y][x] ^ (x + y) % 2 ^ 1)
	return n

def scanner(qrcode):
	mode = num(qrcode, modebits)
	length = num(qrcode, lenbits)
	print(f'mode={mode!r}, length={length!r}')
	return ''.join((chr(num(qrcode, bits[i])) for i in range(length)))