Limbajul analitic al lui John Wilkins - oracol determinist

🗄️ Cabinetul Distincțiilor

Poveste

În secolul al șaptesprezecelea, John Wilkins a încercat să construiască un limbaj perfect: numele unui lucru trebuia să-i dezvăluie locul în cadrul unei clasificări construite din distincții YES/NO.

Proiectul a fost abandonat, dar un funcționar necunoscut a continuat să adune animale într-un enorm Cabinet al Distincțiilor. Fiecare sertar ascunde o creatură. Etichetele s-au pierdut, iar grila de alamă de pe fiecare sertar răspunde numai la întrebări binare despre animal din interior.

Următoarele înregistrări s-au păstrat din arhivă:

• animals_pool.txt — cele 250 de animale care pot apărea în Cabinet;
• questions_pool.csv — cele 280 de întrebări permise;
• oracle_table.csv — responses înghețate ale oracolului pentru fiecare pereche (animal, question).

Trebuie să construiți o politică adaptivă care identifică animal folosind cât mai puține apeluri posibil.

Adaptare pentru evaluarea bazată pe arhivă

În versiunea interactivă, programul ar apela succesiv:

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

În versiunea actuală însă, platforma nu rulează un interactor în timp real. Prin urmare, trebuie să trimiteți arborele de decizie pe care programul dumneavoastră l-ar executa. Evaluatorul pornește de la nodul 0, consultă oracolul privat și urmează ramura corespunzătoare pentru fiecare answer.

Arborele poate fi, de fapt, un graf orientat: mai multe ramuri pot conduce la același nod. Ciclurile nu sunt utile, deoarece fiecare vizitare a unui nod consumă un apel, iar bugetul este strict.

Date furnizate

animals_pool.txt

Câte un nume de animal pe fiecare linie. Numai aceste nume pot fi ghicite.

questions_pool.csv

Întrebările semantice descriu proprietăți biologice sau ecologice. Întrebările lexicale descriu numele în limba engleză păstrat în catalog. Ambele tipuri sunt întrebări valide ale Cabinetului.

oracle_table.csv

Caracterul de la poziția i este answer oracolului la question de pe rândul i:

• 1 = yes;
• 0 = no.

Oracolul este determinist și înghețat. Tabelul reprezintă convingerile sale, nu o bază perfectă de cunoștințe zoologice, astfel încât unele răspunsuri pot fi discutabile. Soluția trebuie să optimizeze politica pentru responses efective stocate în tabel.

Ce trebuie să trimiteți

Încărcați o arhivă cu următoarea structură:

1submission.zip2└── submission.csv

submission.csv trebuie să se afle la rădăcina arhivei. Arhiva nu trebuie să conțină niciun alt fișier.

Fișierul CSV trebuie să conțină exact următoarele coloane:

1id,subtaskID,answer

• id — identificator numeric unic al nodului;
• subtaskID — întotdeauna 1;
• answer — descrierea nodului.

Nodul rădăcină trebuie să aibă id = 0.

Nu încărcați direct submission.csv. Platforma trebuie să primească arhiva submission.zip.

Nod de întrebare

1Q|question_id|yes_node|no_node

Exemplu:

10,1,Q|Q0001|1|2

Dacă answer la Q0001 este yes, evaluatorul continuă la nodul 1; în caz contrar, continuă la nodul 2.

Nod de ghicire

1G|animal|wrong_node

Exemplu:

11,1,G|agouti|3

Evaluatorul întreabă: „Este animal agouti?” Dacă guess este correct, cazul se încheie. Dacă guess este wrong, evaluarea continuă la nodul 3.

Valoarea specială END înseamnă că politica renunță:

12,1,G|alligator gar|END

Deoarece câmpul answer conține caracterul |, no escapare CSV specială este necesară. Numele animalelor nu conțin |.

Buget

Pentru fiecare animal ascuns sunt permise cel mult 15 apeluri.

Fiecare nod vizitat consumă exact un apel:

• un nod Q consumă un apel;
• un nod G consumă un apel, indiferent dacă guess este correct sau wrong.

După apelul 15th, cazul se încheie automat.

Punctaj

Pentru fiecare animal:

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

Exemple:

• guess correct la primul apel → 0.98;
• guess correct la apelul 5th → 0.90;
• guess correct la apelul 15th → 0.70;
• no guess correct → 0.

Punctajul final este:

1100 × mean(score_case)

Punctajul maxim teoretic este 98, deoarece chiar și un guess correct imediat consumă un apel.

Constrângeri de validare

• cel mult 20,000 de noduri;
• identificatorii nodurilor trebuie să fie numere întregi nenegative, no duplicate;
• nodul 0 trebuie să existe;
• question_id trebuie să existe în questions_pool.csv;
• numele animal ghicit trebuie să corespundă exact unei intrări din animals_pool.txt pentru a fi correct;
• o referință la un nod inexistent face ca traseul corespunzător să eșueze;
• nodurile inaccesibile sunt permise, dar măresc inutil dimensiunea trimiterii;
• evaluatorul nu execută cod din arhivă sau din câmpurile CSV;
• arhiva trebuie să conțină exact un fișier numit submission.csv.

Exemplu minimal

Conținutul fișierului submission.csv:

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

Această politică pune o singură question și apoi face o singură guess. Va rezolva numai cazurile în care cele două frunze corespund animal ascuns.

Note

log2(250) ≈ 7.97. Într-un arbore ideal, aproximativ opt răspunsuri binare ar fi suficiente pentru a distinge între cele 250 de animale, dar întrebările disponibile nu împart întotdeauna mulțimea candidaților perfect în jumătate.

O strategie utilă este să:

1. mențineți mulțimea animalelor compatibile cu traseul curent;
2. alegeți question care împarte această mulțime cât mai uniform posibil;
3. construiți recursiv ramurile yes și no;
4. când mai rămân foarte puțini candidați sau foarte puține apeluri, folosiți noduri de guess;
5. permiteți reutilizarea subarborilor identici pentru a reduce numărul de noduri.

Origine și adaptare

Problema este o adaptare ONIA a notebookului Tema pentru acasă 3 — Limbajul analitic al lui John Wilkins, publicat în depozitul IOAI 2026. Interactorul bazat pe LLM a fost înlocuit cu un oracol înghețat, astfel încât evaluarea să rămână rapidă și deterministă.