Problem I. 194. (October 2008)
I. 194. There are various types of barcodes, but in commerce EAN-13 (EAN = European Article Number) is most commonly used. This barcode represents a 13-digit number in the following way.
The above parts may consist of various numbers of digits. The System code refers to a country or the type of the product. For example:
|
When a new product is released, the manufacturer can obtain a new EAN-13 code from a central database.
The last digit of an EAN-13 code is the Check digit, which gives some protection against a random misprint or improper reading of the barcode. To form this checksum, we compute a weighted sum of the first 12 digits as follows: digits at odd positions are multiplied by 1, while digits at even positions are multiplied by 3, then these products are added. This sum is rounded up to the nearest whole ten number. The 13th digit is defined by the increment made in the last step.
In the above example: 5.1+9.3+0.1+7.3+4.1+6.3+0.1+8.3+0.1+3.3+5.1+9.3=140. Since 140 is already divisible by 10, no rounding up is necessary, so the increment, and hence the Check digit should be 0. This shows that the EAN-13 barcode in the example is valid.
The layout of the barcode is described below.
- Digits are encoded by black and white areas. Scanners read these.
- The first separated digit on the left determines the method of encoding. No bars correspond to it, so it is encoded differently.
- The rest of the code contains two groups of digits. In front of, behind and between the groups there are thin double lines.
- Each digit is represented by 2 lines with varying thickness, occupying 7 units of width. There can be 3 different encodings within a barcode. Let us denote these by A, B or C. The 2 lines can be converted into digits according to the table (``Szám'' means ``Digit''), where black colour is 1 and white is 0.
|
- The first group of digits (that is, digits from position 2 to position 7) are encoded either by A or B, while the second group (consisting of the last 6 digits) is encoded by scheme C.
- The first digit of the EAN-13 barcode determines the type of encodings of the six digits in the first group according to the table (``Első számjegy'' means ``First digit'').
The structure of the barcode in the example (a marmalade jar from Poland): The first digit is 5, which is not encoded by lines, but determines the encoding type of the first group according to the highlighted row of the table above.
|
Putting all these together we obtain the barcode.
Using a spreadsheet application, determine whether the EAN-13 barcode in cell A1 is valid, using the Check digit: you should write either ``valid'' or ``invalid'' into cell B1. Then you should convert the given sequence of digits into a sequence of lines encoded by 0s and 1s in cells A2:A16 (as in the Thickness column of the example above).
You should not use macros or program modules, only formulae and built-in functions. Intermediate computations should be visible, so do not hide any of them. Auxiliary tables for the conversion can be placed on separate sheets.
Your worksheet (i194.xls, i194.ods, ...) together with a short documentation (i194.txt, i194.pdf, ...) should be submitted, also containing a brief description of your solution and the name and version number of the spreadsheet application used.
(10 pont)
Deadline expired on November 17, 2008.
Sorry, the solution is available only in Hungarian. Google translation
Megoldásokról:
Sok jó megoldás mellett a feladatspecifikációt többen nem tartották be. A vonalkód működési elvét néhányan titkosításnak gondolták. Erről szó nincs. A vonalkód gyors, pontos és ellenőrzött adatrögzítő és kommunikáló eszköz. EAN 13 az UPC kód (Universal Product Code) továbbfejlesztéséből alakult ki. Ez az első világméretű termékazonosító rendszer és kódtípus. Az ellenőrző számjegyet majdnem mindenki jól határozta meg, annak ellenére, hogy a 13 jegyű szám számjegyekre bontása nem kívánt hatalmas függvényapparátust.
A vonalkód rendszer csoportjainak meghatározása kétszeres mélységű keresést igényel. Az első számjegy alapján kellett meghatározni az első számjegycsoport kódolás típusát, majd ennek és a megfelelő számjegyek ismeretében már a kódot.
A feladat Pap 987 Dávid által készített megoldása (i194.xls).
Különösen ötletes, hogy a vonalkód mintát feltételes formázás segítségével egy munkalapon megjelenítette.
Statistics:
23 students sent a solution. 10 points: Dévényi Attila, Fehér Péter, Jákli Gábor, Kővágó Zoltán, Kristóf Tamás, Molnár Gábor, Pap 999 Dávid, Szabó 295 Gábor, Szabó 928 Attila, Szendrei Péter, Tóth Szabolcs, Uray Marcell János. 9 points: Balla Attila, Debreceni Bálint, Englert Péter, Horváth 135 Loránd, Kapitány Ágoston. 7 points: 2 students. 6 points: 3 students. 2 points: 1 student.
Problems in Information Technology of KöMaL, October 2008