John Wilkins analītiskā valoda - deterministisks orākuls

🗄️ Atšķirību kabinets

Stāsts

Septiņpadsmitajā gadsimtā John Wilkins mēģināja izveidot perfektu valodu: lietas nosaukumam vajadzēja atklāt tās vietu klasifikācijā, kas veidota no YES/NO atšķirībām.

Projekts tika pamests, taču kāds nezināms ierēdnis turpināja vākt dzīvniekus milzīgajā Atšķirību kabinetā. Katrā atvilktnē ir paslēpta radība. Etiķetes ir pazudušas, un misiņa režģis uz katras atvilktnes reaģē tikai uz bināriem jautājumiem par tajā esošo animal.

No arhīva ir saglabājušies šādi ieraksti:

• animals_pool.txt — 250 dzīvnieki, kas var atrasties kabinetā;
• questions_pool.csv — 280 atļautie jautājumi;
• oracle_table.csv — fiksētās orākula responses katram (animal, question) pārim.

Jums jāizveido adaptīva politika, kas identificē animal, izmantojot pēc iespējas mazāk izsaukumu.

Pielāgojums arhīvā balstītai vērtēšanai

Interaktīvajā versijā programma secīgi izsauktu:

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

Tomēr pašreizējā versijā platforma nedarbina reāllaika interaktoru. Tādēļ Jums jāiesniedz lēmumu koks, ko izpildītu Jūsu programma. Vērtētājs sāk mezglā 0, izmanto privāto orākulu un pēc katras answer dodas pa atbilstošo zaru.

Koks faktiski var būt orientēts grafs: vairāki zari var novest uz vienu un to pašu mezglu. Cikli nav lietderīgi, jo katrs mezgla apmeklējums patērē vienu izsaukumu, un budžets ir stingrs.

Dotie dati

animals_pool.txt

Katrā rindā ir viens animal nosaukums. Minējumos drīkst izmantot tikai šos nosaukumus.

questions_pool.csv

Semantiskie jautājumi apraksta bioloģiskas vai ekoloģiskas īpašības. Leksiskie jautājumi apraksta katalogā saglabāto nosaukumu angļu valodā. Atšķirību kabinetā der abu veidu jautājumi.

oracle_table.csv

Rakstzīme pozīcijā i ir orākula answer uz question rindā i:

• 1 = yes;
• 0 = no.

Orākuls ir deterministisks un fiksēts. Tabula atspoguļo tā uzskatus, nevis perfektu zooloģisko zināšanu bāzi, tādēļ dažas atbildes var būt apstrīdamas. Risinājumam politika jāoptimizē atbilstoši tabulā glabātajām faktiskajām responses.

Kas Jums jāiesniedz

Augšupielādējiet arhīvu ar šādu struktūru:

1submission.zip2└── submission.csv

submission.csv jāatrodas arhīva saknē. Arhīvā nedrīkst būt neviena cita faila.

CSV failā jābūt tieši šādām kolonnām:

1id,subtaskID,answer

• id — unikāls mezgla skaitlisks identifikators;
• subtaskID — vienmēr 1;
• answer — mezgla apraksts.

Saknes mezglam jābūt id = 0.

Neaugšupielādējiet submission.csv tieši. Platformai jāsaņem arhīvs submission.zip.

Jautājuma mezgls

1Q|question_id|yes_node|no_node

Piemērs:

10,1,Q|Q0001|1|2

Ja answer uz Q0001 ir yes, vērtētājs turpina darbu mezglā 1; pretējā gadījumā tas turpina darbu mezglā 2.

Minējuma mezgls

1G|animal|wrong_node

Piemērs:

11,1,G|agouti|3

Vērtētājs jautā: “Vai animal ir agouti?” Ja guess ir correct, gadījums beidzas. Ja guess ir wrong, vērtēšana turpinās mezglā 3.

Īpašā vērtība END nozīmē, ka politika padodas:

12,1,G|alligator gar|END

Tā kā laukā answer ir rakstzīme |, īpaša CSV ekranēšana no nepieciešama. Dzīvnieku nosaukumos nav |.

Budžets

Katram paslēptajam animal ir atļauti ne vairāk kā 15 izsaukumi.

Katrs apmeklētais mezgls patērē tieši vienu izsaukumu:

• Q mezgls patērē vienu izsaukumu;
• G mezgls patērē vienu izsaukumu neatkarīgi no tā, vai guess ir correct vai wrong.

Pēc 15th izsaukuma gadījums automātiski beidzas.

Vērtēšana

Katram animal:

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

Piemēri:

• correct guess pirmajā izsaukumā → 0.98;
• correct guess 5th izsaukumā → 0.90;
• correct guess 15th izsaukumā → 0.70;
• no correct guess → 0.

Galīgais rezultāts ir:

1100 × mean(score_case)

Teorētiski maksimālais rezultāts ir 98, jo pat tūlītējs correct guess patērē vienu izsaukumu.

Validācijas ierobežojumi

• ne vairāk kā 20,000 mezglu;
• mezglu identifikatoriem jābūt nenegatīviem veseliem skaitļiem no dublikātiem;
• mezglam 0 ir jāpastāv;
• question_id jāpastāv failā questions_pool.csv;
• lai minējums būtu correct, minētajam animal nosaukumam precīzi jāsakrīt ar ierakstu failā animals_pool.txt;
• atsauce uz neesošu mezglu izraisa attiecīgā ceļa neveiksmi;
• nesasniedzami mezgli ir atļauti, taču tie nevajadzīgi palielina iesnieguma apjomu;
• vērtētājs neizpilda kodu no arhīva vai CSV laukiem;
• arhīvā jābūt tieši vienam failam ar nosaukumu submission.csv.

Minimāls piemērs

Faila submission.csv saturs:

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

Šī politika uzdod vienu question un pēc tam izdara vienu guess. Tā atrisinās tikai tos gadījumus, kuros abas lapas atbilst paslēptajam animal.

Piezīmes

log2(250) ≈ 7.97. Ideālā kokā ar aptuveni astoņām binārām atbildēm pietiktu, lai nošķirtu 250 dzīvniekus, taču pieejamie jautājumi ne vienmēr sadala kandidātu kopu precīzi uz pusēm.

Noderīga stratēģija ir:

1. uzturēt to dzīvnieku kopu, kas atbilst pašreizējam ceļam;
2. izvēlēties question, kas šo kopu sadala pēc iespējas vienmērīgāk;
3. rekursīvi izveidot yes un no zarus;
4. ja atlicis ļoti maz kandidātu vai izsaukumu, izmantot guess mezglus;
5. atļaut atkārtoti izmantot identiskus apakškokus, lai samazinātu mezglu skaitu.

Izcelsme un pielāgojums

Šis uzdevums ir IOAI 2026 repozitorijā publicētās piezīmju grāmatas 3. mājasdarbs — John Wilkins analītiskā valoda ONIA adaptācija. Uz LLM balstītais interaktors tika aizstāts ar fiksētu orākulu, lai vērtēšana būtu ātra un deterministiska.