Die analytische Sprache von John Wilkins - deterministisches Orakel

🗄️ Das Kabinett der Unterscheidungen

Geschichte

Im siebzehnten Jahrhundert versuchte John Wilkins, eine vollkommene Sprache zu entwickeln: Der Name eines Dinges sollte dessen Platz innerhalb einer Klassifikation offenbaren, die aus YES/NO-Unterscheidungen aufgebaut war.

Das Projekt wurde aufgegeben, doch ein unbekannter Schreiber sammelte weiterhin Tiere in einem gewaltigen Kabinett der Unterscheidungen. Jede Schublade verbirgt ein Lebewesen. Die Beschriftungen sind verloren gegangen, und das Messingraster an jeder Schublade beantwortet ausschließlich binäre Fragen über das darin befindliche animal.

Aus dem Archiv sind die folgenden Aufzeichnungen erhalten geblieben:

• animals_pool.txt — die 250 Tiere, die im Kabinett vorkommen können;
• questions_pool.csv — die 280 zulässigen Fragen;
• oracle_table.csv — die eingefrorenen Orakel-responses für jedes (animal, question)-Paar.

Sie müssen eine adaptive Strategie entwickeln, die das animal mit möglichst wenigen Aufrufen identifiziert.

Anpassung für die archivbasierte Auswertung

In der interaktiven Version würde das Programm nacheinander Folgendes aufrufen:

1interactor.ask(question)   # -> "yes" / "no"2interactor.guess(animal)   # -> "correct" / "wrong"

In der aktuellen Version führt die Plattform jedoch keinen Echtzeit-Interactor aus. Daher müssen Sie den Entscheidungsbaum einreichen, den Ihr Programm ausführen würde. Der Auswerter beginnt beim Knoten 0, befragt das private Orakel und folgt für jede answer dem entsprechenden Zweig.

Der Baum kann tatsächlich ein gerichteter Graph sein: Mehrere Zweige können zum selben Knoten führen. Zyklen sind nicht sinnvoll, da jeder Besuch eines Knotens einen Aufruf verbraucht und das Budget strikt ist.

Bereitgestellte Daten

animals_pool.txt

Eine animal-Bezeichnung pro Zeile. Nur diese Bezeichnungen dürfen geraten werden.

questions_pool.csv

Semantische Fragen beschreiben biologische oder ökologische Eigenschaften. Lexikalische Fragen beschreiben den im Katalog erhaltenen englischen Namen. Beide Arten sind gültige Fragen des Kabinetts.

oracle_table.csv

Das Zeichen an Position i ist die answer des Orakels auf die question in Zeile i:

• 1 = yes;
• 0 = no.

Das Orakel ist deterministisch und eingefroren. Die Tabelle stellt seine Überzeugungen dar und keine vollkommene zoologische Wissensbasis; daher können einige Antworten strittig sein. Die Lösung muss die Strategie für die tatsächlich in der Tabelle gespeicherten responses optimieren.

Was Sie einreichen müssen

Laden Sie ein Archiv mit der folgenden Struktur hoch:

1submission.zip2└── submission.csv

submission.csv muss sich im Stammverzeichnis des Archivs befinden. Das Archiv darf keine weiteren Dateien enthalten.

Die CSV-Datei muss genau die folgenden Spalten enthalten:

1id,subtaskID,answer

• id — eindeutige numerische Kennung des Knotens;
• subtaskID — immer 1;
• answer — Beschreibung des Knotens.

Der Wurzelknoten muss id = 0 haben.

Laden Sie submission.csv nicht direkt hoch. Die Plattform muss das Archiv submission.zip erhalten.

Frageknoten

1Q|question_id|yes_node|no_node

Beispiel:

10,1,Q|Q0001|1|2

Wenn die answer auf Q0001 yes lautet, fährt der Auswerter mit Knoten 1 fort; andernfalls fährt er mit Knoten 2 fort.

Rateknoten

1G|animal|wrong_node

Beispiel:

11,1,G|agouti|3

Der Auswerter fragt: „Ist das animal agouti?“ Wenn der guess correct ist, endet der Fall. Ist guess wrong, wird die Auswertung bei Knoten 3 fortgesetzt.

Der besondere Wert END bedeutet, dass die Strategie aufgibt:

12,1,G|alligator gar|END

Da das Feld answer das Zeichen | enthält, ist no besondere CSV-Escapesequenz erforderlich. Tierbezeichnungen enthalten kein |.

Budget

Für jedes verborgene animal sind höchstens 15 Aufrufe zulässig.

Jeder besuchte Knoten verbraucht genau einen Aufruf:

• Ein Q-Knoten verbraucht einen Aufruf;
• ein G-Knoten verbraucht einen Aufruf, unabhängig davon, ob der guess correct oder wrong ist.

Nach dem 15th Aufruf endet der Fall automatisch.

Wertung

Für jedes animal:

1score_case = max(0, (1 if guessed correctly, otherwise 0) - 0.02 × calls_used)

Beispiele:

• correct guess beim ersten Aufruf → 0.98;
• correct guess beim 5th Aufruf → 0.90;
• correct guess beim 15th Aufruf → 0.70;
• no correct guess → 0.

Die Endpunktzahl lautet:

1100 × mean(score_case)

Die theoretische Höchstpunktzahl beträgt 98, da selbst ein sofortiger correct guess einen Aufruf verbraucht.

Validierungsbeschränkungen

• höchstens 20,000 Knoten;
• Knotenkennungen müssen nichtnegative Ganzzahlen sein, mit no Duplikaten;
• Knoten 0 muss vorhanden sein;
• question_id muss in questions_pool.csv vorhanden sein;
• die geratene animal-Bezeichnung muss exakt mit einem Eintrag aus animals_pool.txt übereinstimmen, um als correct zu gelten;
• ein Verweis auf einen nicht vorhandenen Knoten lässt den entsprechenden Pfad fehlschlagen;
• nicht erreichbare Knoten sind zulässig, vergrößern die Einreichung jedoch unnötig;
• der Auswerter führt weder Code aus dem Archiv noch Code aus den CSV-Feldern aus;
• das Archiv muss genau eine Datei namens submission.csv enthalten.

Minimalbeispiel

Inhalt von submission.csv:

1id,subtaskID,answer20,1,Q|Q0001|1|231,1,G|agouti|END42,1,G|alligator gar|END

Diese Strategie stellt eine einzige question und unternimmt anschließend einen einzigen guess. Sie löst nur die Fälle, in denen die beiden Blätter mit dem verborgenen animal übereinstimmen.

Hinweise

log2(250) ≈ 7.97. In einem idealen Baum würden ungefähr acht binäre Antworten ausreichen, um die 250 Tiere voneinander zu unterscheiden, doch die verfügbaren Fragen teilen die Kandidatenmenge nicht immer vollkommen in zwei Hälften.

Eine nützliche Strategie besteht darin:

1. die mit dem aktuellen Pfad vereinbare Tiermenge zu verwalten;
2. die question auszuwählen, die diese Menge möglichst gleichmäßig teilt;
3. die Zweige yes und no rekursiv aufzubauen;
4. guess-Knoten zu verwenden, wenn nur noch sehr wenige Kandidaten oder Aufrufe übrig sind;
5. die Wiederverwendung identischer Teilbäume zuzulassen, um die Anzahl der Knoten zu verringern.

Herkunft und Anpassung

Die Aufgabe ist eine ONIA-Anpassung des Notebooks Hausaufgabe 3 — Die analytische Sprache von John Wilkins, das im IOAI 2026-Repository veröffentlicht wurde. Der LLM-basierte Interactor wurde durch ein eingefrorenes Orakel ersetzt, damit die Auswertung schnell und deterministisch bleibt.