Programmierwettbewerbe

Wettbewerbe sind vor allem für diejenigen reizvoll, die gerne und gut programmieren können. Wer schon mit den Programmieraufgaben des schulischen Informatikunterrichts seine Not hat, für den sind Programmierwettbewerbe nicht das Richtige.

In der Regel gilt, dass Schüler, die Interesse an Programmierwettbewerben haben, eine Anschubunterstützung durch den Informatiklehrer benötigen: Durch Hinweise auf geeignete Wettbewerbe und ggf. Empfehlungen für Einstiegsaufgaben.

Offline-Wettbewerbe

Der Klassiker unter den Offline-Wettbewerben im Bereich der Informatik ist der „Bundeswettbewerb Informatik“, der seit Anfang der 80er Jahre einmal jährlich durchgeführt wird. Aus den (besten) Teilnehmern dieses Wettbewerbs rekrutiert sich jeweils die deutsche Mannschaft der „Informatik-Olympiade“.

Mit dem „Informatikbiber" und dem „Jugendwettbewerb Informatik“ sind in den letzten Jahren weitere Wettbewerbe für (jüngere) Schüler hinzugekommen, die allesamt unter dem Dach der BWINF („Bundesweite Informatikwettbewerbe“) firmieren und teilweise auch als Online-Wettbewerb geführt werden – die Grenzen sind das fließend.

Vorteil all dieser Wettbewerbe ist, dass hinter den Kulissen ein Team von Experten sitzt, die für eine hohe Qualität der Aufgaben sorgen. Weiterhin ist alles in deutscher Sprache gehalten (was im Bereich der Programmierung nicht selbstverständlich ist) und speziell an eine bestimmte Altersgruppe angepasst. Der – aus meiner Sicht leider aber wesentliche – Nachteil dieser Wettbewerbe ist, dass sie jeweils nur einmal im Jahr zu einem festen Termin stattfinden bzw. beginnen.

Online-Wettbewerbe

Innerhalb der Gruppe der Online-Wettbewerbe lässt sich noch einmal differenzieren zwischen solchen mit klar festgelegtem Anfangs- und Endtermin (die sich abgesehen von der Art der Lösungsübermittlung kaum von den klassischen Offline-Wettbewerben unterscheiden) und solchen, die dauerhaft laufen und bei denen man jederzeit einsteigen und mitmachen kann.

Von Interesse für programmierhungrige Schüler sind vor allem letztere, denn man kann quasi sofort loslegen – in der Regel nach vorheriger Registrierung (in einigen Fällen ist nicht einmal das erforderlich).

Nachteile aller mir bekannten Wettbewerbe dieser Art: Sie sind durchweg englischsprachig, eher auf Studenten und Programmierer ausgerichtet und erreichen nicht durchgängig die hohe Qualität der Aufgaben der BWINF.

Nachfolgend einige Online-Wettbewerbe, die ich aus eigener Erfahrung kenne:

SPOJ: Einer der bekanntesten Online-Wettbewerbe mit einigen tausend Aufgaben. Für die Lösung der Aufgaben kann eine große Zahl an Programmiersprachen verwendet werden. Es gibt ein aktives Forum mit Hilfestellungen. Eine Registrierung ist erforderlich.
Schwierig ist es, in der Fülle der Aufgaben geeignete zu finden, die für Schüler lösbar sind.

CodeChef: Ähnlich populär wie SPOJ. Auch hier gibt es eine Fülle an Aufgaben sowie zu typischen algorithmischen Problemen ausführliche Anleitungen. Eine Registrierung ist erforderlich. Wie bei SPOJ gilt auch hier: Schüler sind in der Regel damit überfordert, geeignete Aufgaben herauszufiltern.

Project Euler: Ebenfalls ein Klassiker, funktioniert aber nach anderem Prinzip als SPOJ oder CodeChef. Es werden keine Quelltexte eingeschickt, sondern lediglich Werte, die sich als Ergebnis einer bestimmten Aufgabe ergeben. Die ersten Aufgaben sind für Schüler noch zu schaffen, das Anforderungsniveau steigt dann aber steil an und geht klar in den universitären Bereich. Eine Registrierung ist erforderlich.

Code-Golf

Eine besondere Art der Online-Wettbewerbe ist das sog. „Code-Golfing“. Ziel ist es, eine bestimmte Programmieraufgabe mit einem möglichst kurzen Quelltext zu lösen – je kürzer der (funktionierende) Quelltext, desto mehr Punkte erhält man für die Lösung.

Zwar ist das „Code-Golfing“ im Hinblick auf die didaktischen Ziele des Informatikunterrichts eher kontraproduktiv, aber der Schwierigkeitsgrad der Aufgaben in diesen Wettbewerben ist vielfach so, dass sie für Schüler gut geeignet sind. Eine Chance auf eine gute Platzierung hat man zwar als Schüler kaum (sofern man nicht auf die Suche nach Spoilern geht und fündig wird), aber zumindest besteht eine hohe Wahrscheinlichkeit, die Aufgaben überhaupt lösen zu können.

Shortening Contest: Ein Ableger von SPOJ. Einige (wenige) Aufgaben gibt es auch in deutscher Übersetzung. Die Auswahl der Aufgaben ist relativ groß und das Qualitätsniveau ist gut. Eine Registrierung ist erforderlich.

Code Golf: Technisch und auch hinsichtlich der Aufgaben deutlich schlichter als der „Shortening Contest“. Vorteil ist allerdings, dass die Aufgaben überwiegend einfach sind, die Aufgabenbeschreibungen nur wenig Text umfassen und man auch ohne Registrierung mitmachen kann.

Typische Aufgaben der Online-Wettbewerbe funktionieren nach dem EVA-Prinzip: Das (zu entwickelnde) Programm erhält eine nach Art und Umfang spezifizierte Anzahl an Werten, verarbeitet diese gemäß Aufgabenstellung und gibt das Ergebnis dieser Verarbeitung aus.
Die Ausgabe erfolgt dabei über stdout, die Eingabe je nach Plattform über stdin oder als Kommandozeilen-Parameter. Da insbesondere JavaScript für diese Art von Ein-/Ausgabe im Unterricht nicht genutzt wird und darüber hinaus die Art und Weise, wie dies implementiert ist, auch noch von der jeweils eingesetzten JS-Engine abhängen, zeige ich nachfolgend an zwei einfachen Beispielen, wie dies in der Praxis aussehen kann.

Beispiel 1: Reverse Order

Ausgewählt habe ich die Aufgabe REVORDER aus dem Shortening Contest. Sie ist einfach zu verstehen und auch einfach zu lösen:
Die erste Zeile der Eingabe enthält die Anzahl n der danach folgenden Werte. Es folgen n weitere Eingabezeilen mit je einem Zahlenwert. Diese Zahlenwerte sollen in umgekehrter Reihenfolge untereinander wieder ausgegeben werden.

Im Auswahlfeld für die Programmiersprache stehen zwei JavaScript-Versionen zur Verfügung – ich empfehle die (aktuellere) „Spidermonkey“-Version, für die der nachfolgende Quelltext korrekt funktioniert.

Eingaben erfolgen bei SPOJ über die Standard-Eingabe (stdin), Ausgaben über die Standard-Ausgabe (stdout). Beides wird im Unterricht nicht behandelt, weil alle JavaScript-Programme im unterrichtlichen Kontext in ein HTML-Dokument eingebettet sind und im Browser ablaufen. JavaScript in der Spikermonkey-Fassung bietet mit readline() und print() zwei einfache Funktionen für die Standard-Eingabe bzw. -Ausgabe.

Eine gut lesbare (nicht kurze) Lösung in JavaScript (Spidermonkey) könnte so aussehen:

let n = Number(readline()); // Anzahl einlesen
let a = [];
for (let i=1; i<=n; i++) {
    let v = readline(); // Wert einlesen
    a.push(v);	
}
for (let i=1; i<=n; i++) {
    let v = a.pop();
    print(v); // Wert ausgeben
}

Im Auswahlfeld für die Programmiersprache stehen mindestens zwei Python-Versionen zur Verfügung. Ich empfehle jeweils die aktuellste dort verfügbare Version zu nutzen. Die Standard-Eingabe erfolgt in Python über input(), die Ausgabe über print().

Eine gut lesbare (nicht kurze) Lösung in Python 3:

n = int(input()) # Anzahl einlesen
a = []
for i in range(n):
    v = input() # Wert einlesen
    a.append(v)
for i in range(n):
    v = a.pop()
    print(v) # Wert ausgeben

ACHTUNG: Sowohl für JavaScript als auch für Python 3 gilt, dass readline() bzw. input() eine Zeichenkette als Rückgabewert liefert!
In Python muss – wenn ein Zahlenwert benötigt wird – eine explizite Typumwandlung erfolgen (Zeile 1). In JavaScript würde bei diesem Beispiel die implizite Typ­umwandlung durch den Vergleich mit i im Schleifenkopf greifen. Darauf sollte man sich aber nur verlassen, wenn man damit vertraut ist. Ansonsten ist eine explizite Typumwandlung der sichere Weg (Zeile 1).

Je nach Betriebssystem ist das lokale Testen des Codes nicht ganz so einfach – dies gilt vor allem für JavaScript. Statt sich eine entsprechende Entwicklungsumgebung lokal einzurichten, kann man auch eine Online-Entwicklungsumgebung nutzen. Empfehlenswert ist z.B. IDEone, weil dort im HIntergrund das gleiche System am Werk ist wie bei SPOJ. Man kann IDEone ohne Anmeldung nutzen – dann ist der dort eingegebene Code allerdings für die Öffentlichkeit sichtbar. Möchte man dies vermeiden, ist eine Registrierung erforderlich.

Beispiel 2: Ordinal Numbers

Da die Eingabe von Werten beim Code-Golf-Wettbewerb anders funktioniert als beim Shortening Contest, habe ich die Aufgabe Ordinal Numbers aus diesem Wettbewerb gewählt – einige der wenigen Aufgaben dieses Wettbewerbs, die überhaupt die Verarbeitung von Eingabewerten verlangt. Der größere Teil der Aufgaben produziert nur eine Ausgabe.

Eingaben werden nicht über stdin entgegen genommen, sondern (hinter den Kulissen) dem Programm per Kommandozeilen-Parameter mitgegeben, wobei die Anzahl der Eingabewerte der Anzahl der Parameter entspricht.

Die Aufgabe selbst ist einfach zu verstehen und gut zu lösen. Es gibt lediglich eine typische Stolperfalle bei dieser Aufgabe, aber da man die erwartete Ausgabe mit der vom eigenen Programm erzeugten vergleichen kann, findet man diesen Fehler – falls man ihn gemacht hat – recht schnell. Die Aufgabe:
Man erhält eine (unbekannte) Anzahl an Zahlenwerten und soll jeweils die zugehörige Ordinalzahlen in der englischen Schreibweise bilden und ausgeben. Aus 3 wird 3rd, aus 8 wird 8th usw.

Die Code-Golf-Plattform nutzt die V8-JavaScript-Engine, die z.T. andere Funktionen für die Ein- und Ausgabe unterstützt als die Spidermonkey-Version. Der gezeigte Quelltext funktioniert so korrekt mit der V8-Version. Die globale Variable arguments verweist auf ein Array, dessen Elemente die übergebenen Parameter sind. Mittels einer for-of-Schleife kann man dann z.B. der Reihe nach über diese Werte iterieren, ohne die Anzahl kennen zu müssen.

Eine gut lesbare (nicht kurze) Lösung in JavaScript (V8) könnte so aussehen:

let a = arguments; // Eingabewerte in Array a
for (let s of a) { 
    if (s.endsWith("1") && !s.endsWith("11")) {
        print(s+"st");
    } else 
    if (s.endsWith("2") && !s.endsWith("12")) {
        print(s+"nd");
    } else
    if (s.endsWith("3") && !s.endsWith("13")) {
        print(s+"rd");
    }
    else {print(s+"th");}
}

Die Verarbeitung von Kommandozeilen-Parametern erfolgt in Python über die Liste argv aus dem Modul sys, das darum importiert werden muss. Dabei gilt, dass das erste Element der Parameterliste (mit Index 0) den Namen des ausführenden Programms enthält. Die übergebenen Werte beginnen danach (ab Index 1).

Eine gut lesbare (nicht kurze) Lösung in Python 3:

import sys
a = sys.argv[1:] 
for s in a: # über Eingabewerte iterieren
   if s.endswith("1") and not s.endswith("11"): 
      print(s+"st")
   elif s.endswith("2") and not s.endswith("12"): 
      print(s+"nd")
   elif s.endswith("3") and not s.endswith("13"): 
      print(s+"rd")
   else: print(s+"th")

Wie einsteigen?

Da man bei Code-Golf direkt ohne Registrierung loslegen kann, könnte das ein erster Einstieg sein. Ich empfehle, zunächst meine Lösung zur „Ordinal-Numbers“-Aufgabe in der Programmiersprache der Wahl einzugeben und damit zu experimentieren. Eine geeignete (weil einfach zu verstehende und einfach zu lösende) Folgeaufgabe könnte dann Divisors sein: Für alle Zahlen von 1 bis 100 deren Teiler berechnen und ausgeben.