Create the QR-Code
Description:
Overview
Your task is to encode a QR code. You get a string, of at most seven characters and it contains at least one letter.
You should return a QR code as a 2 dimensional array, filled with numbers, 1 is for a black field and 0 for a white field. We are limiting ourself to version 1, always usebyte mode, mask 0, and Error Correction Lvl H.
The way to encode a QR code is explained below.
Input/output
- Input: string of at most 7 characters.
- Output: 2 dimensional array, according to the process described below.
const text = "Hi";
return [[ 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, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1 ],
[ 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1 ],
[ 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1 ],
[ 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1 ],
[ 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 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, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1 ],
[ 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1 ],
[ 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1 ],
[ 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0 ],
[ 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0 ],
[ 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1 ],
[ 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1 ],
[ 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1 ],
[ 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0 ],
[ 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1 ],
[ 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0 ],
[ 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1 ]];
Debugging
It can be quite frustrating to find a mistake in a 21x21 matrix. Therefore you can use the preloaded function htmlize(), which takes a 2 dimensional array and returns a html graphical view, that you can print to the console.
console.log(htmlize(arr));
Note: htmlize() will throw an error if you don't pass a 21x21 matrix or if there is an invalid character in your matrix (anything other than 0 and 1).
Encoding a QR-code
Here comes the explaination on how to encode a QR code. You can skip it if you already know how it works.
As an example, we are going to encode the string "Hi".
Data encoding
We have to build a binary sequence which represents the data of the QR code.
First of all, we add 0100 to our bit sequence because that stands for byte mode.
bits = "0100";
Now we have to convert the length of our string to a 8 bit binary string:
The length of Hi is 2 which is 00000010 as a 8 bit binary string.
Now we append that binary string to our bit sequence:
bits = "010000000010"
Now we convert the ascii value of every char of our string to a 8 bit binary string and append it to our bit sequence:
H --> 72
72 --> 01001000
bits = "01000000001001001000"
i --> 105
105 --> 01101001
bits = "0100000000100100100001101001"
Now we have to append 0000 as a terminator to our bit sequence, but our sequence must not be longer than 72 bits!
Some examples:
- code length: 50 --> add
0000 - code length: 70 --> add
00 - code length: 71 --> add
0 - code length: 72 --> add nothing
In our example the bit sequence is 28 long, so we add 0000.
bits = "01000000001001001000011010010000"
As long as the length of our sequence isn't 72, we alternately append 11101100 and 00010001:
Append 11101100
bits = "0100000000100100100001101001000011101100"
Append 00010001
bits = "010000000010010010000110100100001110110000010001"
Append 11101100
bits = "01000000001001001000011010010000111011000001000111101100"
etc..
Now we've got our bit sequence!
bits = "010000000010010010000110100100001110110000010001111011000001000111101100"
Error Correction
It often happens that a QR Code was not scanned nicely or it is no longer recognizable in some places; therefore we need error corection bits. QR codes use the Reed-Solomon algorithm to calculate those error correction bits. This algorithm is very complex; that's the reason why this kata is blue.
For version 1, and Error Correction Lvl H, we need 17 Error Correction numbers.
First of all we have to create a message polynomial, it is structured like this:
We have to multiply this by x to the power of the number of Error Correction numbers.
We need 17 so we multiply it by x**17 to get:
Now we split the bit sequence in groups of 8 and convert it to a decimal number:
group1 = 01000000 --> 64
group2 = 00100100 --> 36
etc..
For a,b,c,d,e,f,g,h,i insert the decimal numbers.
We get:
We also need a generator polynomial. If you want to know how to create a generator polynomial, read this.
In this kata we will use the following as generator polynomial because we are limiting ourselfs to vesion 1:
Now we have to multiply the generator polynomial with the lead term of the message polynomial.
The lead term of the message polynomial is 64x**25. We need to convert the integer 64 to alpha notation by looking it up in this table.
This table is already preloaded as a const array alphaTable. Use the integer as index and it returns the alpha exponent. For example:
let alphaExponent = alphaTable[64]; // Returns 6
According to the table we can say:
We multiply the generator polynomial by adding the alpha exponents together.
We get:
IMPORTANT NOTE: it can happen that the exponent becomes bigger than 254. If that happens modulo the exponent with 255!
Now we can convert all alpha exponents back to integers. Again, we are using this table to do that and we get:
Now XOR these integer coefficients with the coefficients of the message polynomial. We get:
If we did everything correct, the lead term has a 0 as coefficient. We can discard the lead term to get the following smaller polynomial which is our new message polynomial:
Note: Very rarely it can happen that the new lead term is also 0, in that case you also have to discard the second term/new lead term. This will affect how many times you repeat the next step.
The generator polynomial is still (and always) the same:
Now perform these steps 8 more times
If you are wondering why 8 times, the length of our initial message polynomial was 9, we did it already once, eight times to go.
Be careful with the case where you had to discard two lead terms.
If it is still hard to undestand you can follow each step very precisely here. You can also input a custom message polynomial but always use 17 error blocks.
The coefficients will be our Error Correction numbers:
250 255 60 175 138 205 169 12 87 238 222 39 87 58 213 84 70.
Note: Like I told you before very rarely both lead terms can be 0 in the discard lead term step. In that case you didn't get 17 error correction numbers, but less. So always check if you got 17 numbers, if not you have to append 0 at the front of our error correction numbers.
We convert all of these numbers to 8 bit binary strings and append it to our bit sequence from the Data Encoding step. Our finished sequence is now:
bits = "0100000000100100100001101001000011101100000100011110110000010001111011001111101011111111001111001010111110001010110011011010100100001100010101111110111011011110001001110101011100111010110101010101010001000110".
Matrix placement, Format and Version Information
Every QR code has three big positioning field to enable the scanner to detect the orientation. These fields are located in the upper two and the lower left corner. They always have the same size so they should be hardcoded.
Also, the connections between the position fields are always the same.
Now we have to add the information about version, mask, and error correction level. In this kata we always use version 1 , mask 0 and error correction lvl H. Therfore you can also hardcode this information; every Qr code should look like this, before we even start to place in our data:
Insert Data
Now we start to insert our bit sequence into the QR matrix. The way we go through the matrix is very important.
We start in the lower right corner, then we go one to the left, then one to the top and one to the right, then left again and so on. It's easier to follow the red arrow on the following picture.
Important: We have to skip the positioning fields and the information about version, mask and EC lvl. Just skip everything which is in a blue box in this picture:
Here is one more picture, that shows us how to go through the matrix:
Now that we know how to go through the matrix we can start to insert our data.
Now another important thing comes into play: the mask
Normally every 1 in our bit sequence represents a black square and every 0 represents a white square but if the condition (x+y)%2==0 is true, we have to invert the color. 1 becomes a white square and 0 becomes a black square.
x is the line counter of the 21x21 matrix.
y is the column counter of the 21x21 matrix.
Ok, let's start:
First bit of our sequence is
0We start in the lower right corner, therefore x is 20 and y is 20 (matrix is 0-based)
(x+y)%2==0is true, therefore instead of a white square we place a black square in the lower right corner
Let's take the next bit, which is
1Now x is still 20 but y is now 19, because we went one to the left
(x+y)%2==0is false, so we we insert a black square
etc...
Finally we get the following QR-code, which is the representation of the string "Hi":
Similar Kata:
Stats:
| Created | Nov 6, 2020 |
| Published | Nov 7, 2020 |
| Warriors Trained | 1421 |
| Total Skips | 214 |
| Total Code Submissions | 1683 |
| Total Times Completed | 124 |
| JavaScript Completions | 25 |
| Java Completions | 31 |
| Python Completions | 56 |
| C# Completions | 19 |
| Total Stars | 206 |
| % of votes with a positive feedback rating | 88% of 46 |
| Total "Very Satisfied" Votes | 38 |
| Total "Somewhat Satisfied" Votes | 5 |
| Total "Not Satisfied" Votes | 3 |
| Total Rank Assessments | 4 |
| Average Assessed Rank | 4 kyu |
| Highest Assessed Rank | 2 kyu |
| Lowest Assessed Rank | 8 kyu |
