Prüfziffern: erst planen, dann programmieren

1. Die Geschichte

Samstagvormittag im Supermarkt. Auf einer Packung Nudeln ist der Strichcode zerknittert, und der Scanner piept nicht. Die Kassiererin tippt die dreizehn Ziffern unter den Strichen von Hand ein:

Dreizehn Ziffern sind viele, und beim Abtippen passiert schnell ein Fehler. Dann stünde auf dem Kassenbon eine andere Ware mit einem anderen Preis.

2. Der Strichcode

Der Code heißt EAN-13 (European Article Number, heute GTIN-13); er steht auf fast jeder Ware im Laden. Die ersten zwölf Ziffern sagen, aus welchem Land die Nummer kommt, welche Firma sie vergeben hat und welche Ware es ist. Die dreizehnte ist keine Information über die Ware, sondern eine Prüfziffer: Sie wird aus den anderen zwölf berechnet, nach einer Regel, die die Organisation GS1 festgelegt hat:

1. Multipliziere die zwölf Ziffern abwechselnd mit 1 und mit 3, mit 1 beginnend. Die Zahl, mit der eine Ziffer multipliziert wird, heißt ihr Gewicht.
2. Addiere die Produkte.
3. Die Prüfziffer ist, was bis zur nächsten durch 10 teilbaren Zahl fehlt. Ist die Summe schon durch 10 teilbar, ist sie 0.

Für die Ziffern 4 001234 56789 sieht das so aus:

Die Summe ist 99; bis 100 fehlt 1, also ist der ganze Code 4 001234 567891.

3. Wie die Striche die Ziffern tragen

Der Scanner liest keine Ziffern, sondern hell und dunkel. Ein Strichcode ist in 95 gleich breite Streifen geteilt, die Module. Jedes Modul ist dunkel oder hell, also eine 1 oder eine 0; ein breiter Strich sind mehrere dunkle Module nebeneinander.

Am Rand und in der Mitte stehen feste Muster: 101 links und rechts, 01010 in der Mitte. Ihre Striche reichen weiter nach unten als die anderen. An ihnen erkennt der Scanner, wo der Code anfängt, wo seine Mitte ist und wie breit ein Modul ist, egal wie weit die Packung vom Scanner entfernt ist. Dazwischen stehen links und rechts je sechs Ziffern mit je sieben Modulen.

Jede Ziffer besteht aus genau zwei dunklen und zwei hellen Abschnitten. Welches Muster zu welcher Ziffer gehört, legt GS1 in einer Tabelle fest, und zwar in drei Fassungen, L, G und R. So sieht die 4 in allen dreien aus:

R ist L mit vertauschtem Hell und Dunkel, G ist R von hinten nach vorne gelesen. Darum genügt die Tabelle für L:

Rechts von der Mitte steht jede Ziffer in R. Links steht sie in L oder in G, und L hat immer eine ungerade Zahl dunkler Module, G eine gerade.

Zähl die Ziffern unter dem Code: Links und rechts von der Mitte stehen je sechs, die 4 ganz vorne hat keine eigenen Striche. Sie steckt in der Auswahl der Fassungen in der linken Hälfte. Bei den Nudeln stehen die Ziffern 2 6 0 1 1 1 in den Fassungen L G L L G G, und dieses Muster bedeutet die 4:

Die erste Ziffer links steht dabei immer in L. Liest der Scanner einen Code von rechts nach links, etwa weil die Packung auf dem Kopf liegt, trifft er zuerst auf eine Ziffer mit einer geraden Zahl dunkler Module. Daran merkt er, dass er rückwärts liest, und dreht die Ziffern um.

4. Ein Algorithmus, drei Schreibweisen

Die Regel in Worten ist kurz, aber ein Computer braucht es genauer: Wo fängt das Zählen an? Was heißt »bis zur nächsten durch 10 teilbaren Zahl«? Bevor du programmierst, schreibst du einen Algorithmus darum so auf, dass er genau ist und trotzdem in keiner Programmiersprache: als Pseudocode oder als Struktogramm. Beides steht im Handbuch unter Pseudocode und Struktogramme, mit einem Feld zum Ausprobieren.

Ein Struktogramm lesen

Ein Struktogramm liest man von oben nach unten. Jeder Kasten ist eine Anweisung; eine Schleife hat links einen Balken, und was rechts daneben steht, wiederholt sie, solange ihre Bedingung oben wahr ist. n mod 10 ist der Rest bei der Division durch 10, n div 10 das ganzzahlige Ergebnis.

mystery(n):
    s ← 0
    while n > 0:
        s ← s + n mod 10
        n ← n div 10
    return s

Die Prüfziffer als Struktogramm

So sieht die Regel von GS1 als Struktogramm aus. digits ist eine Liste der zwölf Ziffern; die erste hat den Index 0. weight(i) ist das Gewicht der Ziffer mit dem Index i, also 1 oder 3.

check_digit(digits):
    total ← 0
    for i from 0 to 11:
        total ← total + weight(i) * digits[i]
    return (10 - total mod 10) mod 10

total mod 10 ist der Rest, und 10 - total mod 10 ist, was bis zur nächsten durch 10 teilbaren Zahl fehlt.

5. Vom Struktogramm zum Code

Einrichten

mkdir -p ~/check-digits
cd ~/check-digits
touch check_digits.rb

irb -r ./check_digits.rb

mkdir -p ~/check-digits
cd ~/check-digits
touch check_digits.py

python3 -i check_digits.py

Das Gewicht

Die Ziffern mit geradem Index (0, 2, 4, …) haben das Gewicht 1, die mit ungeradem Index das Gewicht 3.

weight(index):
    if index mod 2 == 0:
        return 1
    else:
        return 3

def weight(index)
  if index.even?
    1
  else
    3
  end
end

weight(index):
    if index mod 2 == 0:
        return 1
    else:
        return 3

def weight(index):
    if index % 2 == 0:
        return 1
    else:
        return 3

Die Prüfziffer

def check_digit(digits)
  total = 0
  (0..11).each do |i|
    total = total + weight(i) * digits[i]
  end
  (10 - total % 10) % 10
end

def check_digit(digits):
    total = 0
    for i in range(0, 12):
        total = total + weight(i) * digits[i]
    return (10 - total % 10) % 10

6. Erst planen, dann programmieren

Bisher stand der Plan schon da, und du hast ihn übersetzt. Ab jetzt planst du selbst, und zwar gleich dort, wo der Code hinkommt: Du legst die Funktion an und schreibst als Kommentare hinein, was sie Schritt für Schritt tun soll, noch ohne eine Zeile Code. Dabei klärst du drei Fragen: Was bekommt die Funktion, und was gibt sie zurück? Welche Fälle gibt es, auch solche, die nicht vorkommen sollten? Und in welcher Reihenfolge geschieht was?

Dann ersetzt du einen Kommentar nach dem anderen durch Code und probierst nach jedem Schritt aus. Die Kommentare dürfen stehen bleiben: Wer den Code später liest, sieht so, wofür jeder Teil da ist. Genauso planen viele, die beruflich programmieren; der Plan ist Pseudocode, nur eben in der Datei.

Ist der Code gültig?

Die Kasse bekommt, was die Kassiererin getippt hat, als Text, und will wissen: Ist das ein gültiger Code? Er ist es, wenn er aus genau 13 Ziffern besteht und die letzte die Prüfziffer der ersten zwölf ist.

def valid_ean?(code)
  # nicht genau 13 Zeichen: false
  # ein Zeichen ist keine Ziffer: false
  # die 13 Zeichen als Zahlen
  # gültig, wenn die Prüfziffer der ersten zwölf gleich der dreizehnten ist
end

def valid_ean?(code)
  # nicht genau 13 Zeichen: false
  return false unless code.length == 13
  # ein Zeichen ist keine Ziffer: false
  return false unless code.chars.all? { |c| ('0'..'9').include?(c) }

  # die 13 Zeichen als Zahlen
  digits = code.chars.map(&:to_i)
  # gültig, wenn die Prüfziffer der ersten zwölf gleich der dreizehnten ist
  check_digit(digits[0..11]) == digits[12]
end

def is_valid_ean(code):
    # nicht genau 13 Zeichen: False
    # ein Zeichen ist keine Ziffer: False
    # die 13 Zeichen als Zahlen
    # gültig, wenn die Prüfziffer der ersten zwölf gleich der dreizehnten ist
    pass

def is_valid_ean(code):
    # nicht genau 13 Zeichen: False
    if len(code) != 13:
        return False
    # ein Zeichen ist keine Ziffer: False
    if not all(c in '0123456789' for c in code):
        return False
    # die 13 Zeichen als Zahlen
    digits = [int(c) for c in code]
    # gültig, wenn die Prüfziffer der ersten zwölf gleich der dreizehnten ist
    return check_digit(digits[0:12]) == digits[12]

Bücher: die ISBN

Bücher tragen eine ISBN (International Standard Book Number). Bis 2007 hatte sie zehn Zeichen, etwa 3-499-12304-5; die Bindestriche trennen nur Gruppen und zählen nicht mit. Ihre Prüfung geht anders als beim Strichcode:

1. Multipliziere die zehn Ziffern mit den Gewichten 10, 9, 8, … bis 1: die erste mit 10, die letzte mit 1.
2. Addiere die Produkte.
3. Die ISBN ist gültig, wenn die Summe durch 11 teilbar ist.

Die letzte Ziffer ist also so gewählt, dass die Summe aufgeht. Manchmal müsste sie dafür 10 sein, und das ist keine Ziffer: Dann steht dort ein X, wie die römische Zehn. Ein X gibt es nur an dieser Stelle.

Für 3-499-12304-5 ist die Summe 3 · 10 + 4 · 9 + 9 · 8 + 9 · 7 + 1 · 6 + 2 · 5 + 3 · 4 + 0 · 3 + 4 · 2 + 5 · 1 = 242 = 22 · 11; die ISBN ist gültig.

7. Was die Prüfziffer findet

Ein häufiger Fehler beim Abtippen ist nicht die falsche Ziffer, sondern der Zahlendreher: zwei benachbarte Ziffern in der falschen Reihenfolge.

require_relative 'check_digits'

missed = 0
(0..9).each do |a|
  (0..9).each do |b|
    next if a == b

    digits = [a, b, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    code = (digits + [check_digit(digits)]).join
    swapped = code[1] + code[0] + code[2..]
    missed = missed + 1 if valid_ean?(swapped)
  end
end
puts "Unbemerkt: #{missed} von 90"

ruby swaps.rb

from check_digits import check_digit, is_valid_ean

missed = 0
for a in range(0, 10):
    for b in range(0, 10):
        if a == b:
            continue
        digits = [a, b, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        code = ''.join(str(d) for d in digits + [check_digit(digits)])
        swapped = code[1] + code[0] + code[2:]
        if is_valid_ean(swapped):
            missed = missed + 1
print(f"Unbemerkt: {missed} von 90")

python3 swaps.py

9. Zum Nachschlagen

• Pseudocode und Struktogramme im Handbuch: alle Bausteine, ein Feld zum Ausprobieren, und wie aus Pseudocode Ruby oder Python wird.
• Wie man eine Prüfziffer berechnet, bei GS1, auf Englisch: die Regel für EAN-13 und die anderen Codes von GS1.
• ISBN Users' Manual der Internationalen ISBN-Agentur, auf Englisch: wie eine ISBN aufgebaut ist und wie ihre Prüfziffer berechnet wird.