Analytický jazyk, jehož autorem je John Wilkins - deterministické orákulum

🗄️ Kabinet rozlišení

Příběh

V sedmnáctém století se John Wilkins pokusil vytvořit dokonalý jazyk: název věci měl odhalovat její místo v klasifikaci založené na rozlišeních YES/NO.

Projekt byl opuštěn, ale neznámý písař pokračoval ve shromažďování zvířat v obrovském Kabinetu rozlišení. Každá zásuvka ukrývá tvora. Štítky se ztratily a mosazná mřížka na každé zásuvce odpovídá pouze na binární otázky týkající se animal uvnitř.

Z archivu se dochovaly následující záznamy:

• animals_pool.txt — 250 zvířat, která se mohou objevit v Kabinetu;
• questions_pool.csv — 280 povolených otázek;
• oracle_table.csv — neměnné responses orákula pro každou dvojici (animal, question).

Musíte vytvořit adaptivní strategii, která identifikuje animal pomocí co nejmenšího počtu volání.

Úprava pro vyhodnocování založené na archivu

V interaktivní verzi by program postupně volal:

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

V současné verzi však platforma nespouští interaktor v reálném čase. Proto musíte odevzdat rozhodovací strom, který by váš program vykonal. Vyhodnocovací systém začne v uzlu 0, získá odpověď ze soukromého orákula a pro každou answer pokračuje odpovídající větví.

Strom může být ve skutečnosti orientovaným grafem: více větví může vést do stejného uzlu. Cykly nejsou užitečné, protože každá návštěva uzlu spotřebuje jedno volání a rozpočet je přísný.

Poskytnutá data

animals_pool.txt

Na každém řádku je jeden název animal. Tipovat lze pouze tyto názvy.

questions_pool.csv

Sémantické otázky popisují biologické nebo ekologické vlastnosti. Lexikální otázky popisují anglický název uchovávaný v katalogu. Oba typy jsou platnými otázkami Kabinetu.

oracle_table.csv

Znak na pozici i je answer orákula na question na řádku i:

• 1 = yes;
• 0 = no.

Orákulum je deterministické a neměnné. Tabulka zachycuje jeho přesvědčení, nikoli dokonalou zoologickou znalostní bázi, takže některé odpovědi mohou být diskutabilní. Řešení musí optimalizovat strategii pro skutečné responses uložené v tabulce.

Co musíte odevzdat

Nahrajte archiv s následující strukturou:

1submission.zip2└── submission.csv

Soubor submission.csv musí být umístěn v kořenovém adresáři archivu. Archiv nesmí obsahovat žádné další soubory.

Soubor CSV musí obsahovat přesně následující sloupce:

1id,subtaskID,answer

• id — jedinečný číselný identifikátor uzlu;
• subtaskID — vždy 1;
• answer — popis uzlu.

Kořenový uzel musí mít id = 0.

Nenahrávejte přímo soubor submission.csv. Platforma musí obdržet archiv submission.zip.

Uzel otázky

1Q|question_id|yes_node|no_node

Příklad:

10,1,Q|Q0001|1|2

Pokud je answer na Q0001 yes, vyhodnocovací systém pokračuje do uzlu 1; jinak pokračuje do uzlu 2.

Uzel odhadu

1G|animal|wrong_node

Příklad:

11,1,G|agouti|3

Vyhodnocovací systém se zeptá: „Je animal agouti?“ Pokud je guess correct, případ končí. Pokud je guess wrong, vyhodnocování pokračuje v uzlu 3.

Speciální hodnota END znamená, že se strategie vzdává:

12,1,G|alligator gar|END

Protože pole answer obsahuje znak |, no vyžadováno žádné speciální escapování CSV. Názvy zvířat neobsahují znak |.

Rozpočet

Pro každé skryté animal je povoleno nejvýše 15 volání.

Každý navštívený uzel spotřebuje právě jedno volání:

• uzel Q spotřebuje jedno volání;
• uzel G spotřebuje jedno volání bez ohledu na to, zda je guess correct, nebo wrong.

Po 15th volání případ automaticky končí.

Bodování

Pro každé animal:

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

Příklady:

• correct guess při prvním volání → 0.98;
• correct guess při 5th volání → 0.90;
• correct guess při 15th volání → 0.70;
• no correct guess → 0.

Konečné skóre je:

1100 × mean(score_case)

Teoretické maximální skóre je 98, protože i okamžitý correct guess spotřebuje jedno volání.

Omezení validace

• nejvýše 20,000 uzlů;
• identifikátory uzlů musí být nezáporná celá čísla no duplicit;
• uzel 0 musí existovat;
• question_id musí existovat v souboru questions_pool.csv;
• aby byl odhad correct, musí se název tipovaného animal přesně shodovat s položkou ze souboru animals_pool.txt;
• odkaz na neexistující uzel způsobí selhání odpovídající cesty;
• nedosažitelné uzly jsou povoleny, ale zbytečně zvětšují velikost odevzdaného řešení;
• vyhodnocovací systém nespouští kód z archivu ani z polí CSV;
• archiv musí obsahovat právě jeden soubor s názvem submission.csv.

Minimální příklad

Obsah souboru submission.csv:

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

Tato strategie položí jednu question a poté provede jeden guess. Vyřeší pouze případy, ve kterých se oba listy shodují se skrytým animal.

Poznámky

log2(250) ≈ 7.97. V ideálním stromu by přibližně osm binárních odpovědí stačilo k rozlišení mezi 250 zvířaty, dostupné otázky však množinu kandidátů nerozdělují vždy dokonale na poloviny.

Užitečnou strategií je:

1. udržovat množinu zvířat kompatibilních s aktuální cestou;
2. zvolit question, která tuto množinu rozdělí co nejrovnoměrněji;
3. rekurzivně sestavit větve yes a no;
4. pokud zbývá velmi málo kandidátů nebo volání, použít uzly guess;
5. umožnit opakované použití totožných podstromů, aby se snížil počet uzlů.

Původ a úprava

Úloha je adaptací ONIA notebooku Domácí úloha 3 — Analytický jazyk, jehož autorem je John Wilkins, zveřejněného v repozitáři IOAI 2026. Interaktor založený na LLM byl nahrazen neměnným orákulem, aby vyhodnocování zůstalo rychlé a deterministické.