*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 :)

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "def scanner(qrcode):\n    finding_patterns = {((0, 9), (0, 9)),\n                        ((len(qrcode)-8, len(qrcode)), (0, 9)), \n                        ((0, 9), (len(qrcode)-8, len(qrcode)))}\n    timing_patterns = {((9, len(qrcode)-8), (6, 7)), ((6, 7), (9, len(qrcode)-8))}\n    function_patterns = {\n        (x, y) for (x0, x1), (y0, y1) in finding_patterns | timing_patterns\n        for x in range(x0, x1) for y in range(y0, y1)\n    }\n    \n    reading = ((x, 2*y - (y < 4) - i)\n               for y in range(len(qrcode) // 2, 0, -1)\n               for x in (reversed, iter)[y % 2](list(range(len(qrcode))))\n               for i in range(2))\n    bits = ''.join(str((x+y ^ ~qrcode[x][y]) & 1) for (x, y) in reading\n                   if (x, y) not in function_patterns)\n    return bytes(int(bits[i: i+8], 2) for i in range(12, 12+int(bits[4:12], 2)*8, 8)).decode()\n    \n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'scanner'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 43046