Wer wird Milliardär?

In Mausland gibt es eine beliebte Fernsehsendung namens «Wer wird Milliardär?». Es ist eine Quiz-Show, bei der die Teilnehmer bis zu einer Milliarde Maus-Dollars gewinnen können. Maus Stofl mag diese Show sehr, aber wenn er selber Fragen beantworten müsste, hätte er keine Chance, da sein Allgemeinwissen nicht ausreichend ist. Dafür kann er aber programmieren, und er fand es sehr spannnend, ein Programm zu schreiben, das Fragen von «Wer wird Milliardär?» beantworten kann.

Nun möchte er einen Wettbewerb machen zwischen mehreren solchen Programmen, um zu sehen, wie gut sein eigenes Programm ist. Deshalb bittet er dich, ein Programm zu schreiben, das mit Hilfe von Wikipedia solche Multiple Choice Fragen beantworten kann.

Am SOI-Tag wird es eine Quiz-Show geben, bei der die Programme aller Teilnehmer gegeneinander antreten werden.

Aufgabe

Schreibe ein Programm, das interaktiv eine Multiple Choice Frage (auf englisch) nach der anderen beantwortet. Der Einfachheit halber gibt es keine «Joker».

Via Standardeingabe und Standardausgabe (stdin und stdout) kommuniziert dein Programm mit dem QuizServer, einem Quizmaster-Programm, das von den SOI-Organisatoren geschrieben wurde.

Nachdem dein Programm die Frage des Quizmasters gelesen hat, darf es bis zu 25 Artikel im englischen Wikipedia nachschlagen. Dazu muss es dem Quizmaster den Titel des Artikels sagen, den es nachschlagen will, und der Quizmaster liefert ihm den Artikel (oder sagt ihm, dass es keinen Artikel mit diesem Titel gibt). Sobald dein Programm denkt, es wisse die Antwort, teilt es dem Quizmaster seine Wahl mit, und dann folgt die nächste Frage.

Wenn eine bestimmte Anzahl Fragen beantwortet sind, sagt der Quizmaster deinem Programm, es solle sich beenden, und zählt die Anzahl korrekte Antworten. Der Quizmaster stellt die selben Fragen den anderen Programmen, und am Schluss gewinnt das Programm mit den meisten korrekten Antworten.

Eingabe und Ausgabe

Die Eingabe beginnt direkt mit der ersten Frage. Alle Fragen sind in folgendem Format:

Die erste Zeile beginnt mit einem grossen Q (für «query»), gefolgt von einem einzelnen Leerzeichen, gefolgt vom Fragesatz, der mit einem Fragezeichen endet. Die nächsten vier Zeilen beginnen mit den Kleinbuchstaben a, b, c und d, jeweils gefolgt von einem einzelnen Leerzeichen und einer möglichen Antwort.

Nach dem Einlesen der Frage (immer fünf Zeilen) darf dein Programm bis zu 25 Artikel im englischen Wikipedia nachschlagen. Dazu muss es eine Zeile ausgeben, die mit einem grossen L (für «lookup») beginnt, gefolgt von einem Leerzeichen und dem Titel des Artikels, den es nachschlagen will. Der Quizmaster wird den Artikel auf Wikipedia mit dem folgenden URL holen gehen:

http://en.wikipedia.org/w/index.php?action=raw&title=DEIN_TITEL

Die Antwort wird im Wiki-Format sein, d.h. es ist nicht nötig, HTML zu parsen. Wenn der Artikel nur aus einem Redirect zu einer anderen Seite besteht, holt der Quizmaster diese andere Seite. Dies zählt als ein Lookup, nicht zwei.

Er liefert den Artikel deinem Programm in folgendem Format: Die erste Zeile beginnt mit einem grossen A (für «article»), gefolgt vom Titel des Artikels. Wenn es kein Redirect gab, dann ist der Titel genau das, was du vorher hinter dem L geschrieben hast. Dann folgt der Text von Wikipedia, wobei jede Zeile mit einem grossen C beginnt (für «content»), gefolgt von einem einzelnen Leerzeichen und dem Text. Der Artikel wird beendet durch eine Zeile, die nur aus einem grossen E besteht (für «end»). Wenn es keinen Artikel gibt mit dem Titel, den du angegeben hast, dann erhältst du keine C-Zeilen, d.h. nach der A-Zeile folgt direkt die E-Zeile. Dies zählt auch als ein Lookup, weil die Tatsache, dass ein Wort keinen Artikel auf Wikipedia hat, ist auch eine nützliche Information.

Nach höchstens 25 Lookups pro Frage muss dein Programm die Antwort ausgeben: Eine Zeile mit einem kleinen a, b, c oder d. Danach stellt der Quizmaster die nächste Frage, oder er gibt dir eine Zeile, die nur ein grosses T enthält (für «terminate»). In diesem Fall soll sich dein Programm beenden.

Beispiel-Kommunikation

Hier siehst du ein Beispiel für die Kommunikation zwischen deinem Programm und dem QuizServer (gekürzt mit … für bessere Lesbarkeit).

QuizServer:        Q In which area is the term 'Foobar' most often used?                                                                                                                     
                   a in Gabon's airport terminology                                                                                                                                          
                   b in computer programming                                                                                                                                                 
                   c in quantum physics                                                                                                                                                      
                   d in transportation business                                                                                                                                              
your program:      L Foobar                                                                                                                                                                  
QuizServer:        A Foobar                                                                                                                                                                  
                   C {{Distinguish|FUBAR}}                                                                                                                                                   
                   C {{Other uses}}                                                                                                                                                          
                   C {{Redirect|Foo|FOO (Forward Observation Officer)|Artillery observer}}                                                                                                   
                   C The terms '''foobar''' [[Wikipedia:IPA_for_English#Key|/'f??b??r/]], ...                                                                                                
                   C                                                                                                                                                                         
                   C The usage in [[computer programming]] examples and [[pseudocode]] varies; ...                                                                                           
                   C                                                                                                                                                                         
                   C == History and etymology ==                                                                                                                                             
                   C The origins of the terms are not known with certainty, ...                                                                                                              
                   E                                                                                                                                                                         
your program:      L airport terminology                                                                                                                                                     
QuizServer:        A airport terminology                                                                                                                                                     
                   E                                                                                                                                                                         
your program:      b                                                                                                                                                                         
QuizServer:        T                                                                                                                                                                         

Punkte

Ein Programm, das das obige Protokoll respektiert, und ein bisschen schlauer ist als die zur Verfügung gestellten Sample-Programme, wird mindestens 50% der Punkte erhalten. Je mehr Fragen dein Programm an der Quiz-Show der SOI-Organisatoren korrekt beantwortet, desto näher wird deine Punktezahl bei 100% sein.

Bemerkungen

Du sollst nicht die Antworten zu Fragen hardcoden, das ist nicht die Idee des Spiels.

Die Grösse deines Quellcodes sollte nicht grösser sein als 1 MB. Das erlaubt dir, eine Art Wörterbuch einzubinden, oder andere Daten, wenn du denkst, das sei hilfreich. Aber denke daran, dass du nicht Antworten hardcoden sollst.

Nachdem du etwas ausgegeben hast, musst du unbedingt ein flush auf dem stdout machen. Das ist sehr wichtig, denn sonst wird deine Ausgabe im Buffer bleiben, anstatt zum QuizServer zu gehen. In C erreichst du das mit fflush(stdout);, in C++ mit std::cout << std::endl;, und in Java mit System.out.flush();. In den anderen Sprachen gibt es ähnliche Befehle.

Beachte, dass die Limiten (bis zu 25 Lookups pro Frage, 1 MB Quellcode) sehr locker sind. Wir wählten sie so, weil wir deine Kreativität nicht beschränken wollen. Sei also nicht irritiert, wenn dein Programm diese Limiten nicht ausreizt: Wir glauben, dass es auch möglich ist, gute Programme zu schreiben, die die Limiten lange nicht ausreizen.

Du kannst dein Programm testen mit dem QuizServer, den du hier herunterladen kannst: Link

Zusammen mit dem QuizServer erhältst du ein paar Sample-Programme, wo du sehen kannst, wie du mit Input/Output umgehen musst. Wenn es kein Sample-Programm in deiner Lieblingssprache hat, dann schreibe ein email an info at soi dot ch. Grundsätzlich kannst du jede Programmiersprache verwenden, vorausgesetzt es gibt einen freien und portablen Compiler oder Interpreter. Wenn du nicht sicher bist, kannst du im Forum nachfragen.

Du kannst Standardbibliotheken verwenden wie z.B. die C++ STL oder java.lang.*. Du kannst auch andere Bibliotheken mit allgemeinen Utility-Funktionen verwenden (z.B. für String Handling), aber sie dürfen nicht speziell für künstliche Intelligenz oder Quiz-Shows gemacht sein, und sie sollten frei und portabel sein. Auch hier gilt: Wenn du nicht sicher bist, kannst du im Forum nachfragen.

Und wenn du sonst noch Fragen hast, zögere nicht, im Forum nachzufragen!

Einsendung