John Wilkins' analytiske sprog - deterministisk orakel

🗄️ Distinktionernes kabinet

Historie

I det syttende århundrede forsøgte John Wilkins at konstruere et fuldkomment sprog: En tings navn skulle afsløre dens plads i en klassifikation bygget af YES/NO-sondringer.

Projektet blev opgivet, men en ukendt skriver fortsatte med at samle dyr i et enormt Distinktionernes kabinet. Hver skuffe skjuler et væsen. Etiketterne er gået tabt, og messinggitteret på hver skuffe besvarer kun binære spørgsmål om animal indeni.

Følgende optegnelser er bevaret fra arkivet:

• animals_pool.txt — de 250 dyr, der kan forekomme i kabinettet;
• questions_pool.csv — de 280 tilladte spørgsmål;
• oracle_table.csv — de fastfrosne orakel-responses for hvert (animal, question)-par.

I skal konstruere en adaptiv politik, der identificerer animal med så få kald som muligt.

Tilpasning til arkivbaseret evaluering

I den interaktive version ville programmet efter tur kalde:

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

I den nuværende version kører platformen imidlertid ikke en interaktor i realtid. Derfor skal I indsende det beslutningstræ, som jeres program ville udføre. Bedømmeren starter ved knude 0, konsulterer det private orakel og følger den tilsvarende gren for hvert answer.

Træet kan faktisk være en rettet graf: Flere grene kan føre til den samme knude. Cykler er ikke nyttige, fordi hvert besøg i en knude forbruger ét kald, og budgettet er strengt.

Leverede data

animals_pool.txt

Ét animal navn pr. linje. Kun disse navne må gættes.

questions_pool.csv

Semantiske spørgsmål beskriver biologiske eller økologiske egenskaber. Leksikalske spørgsmål beskriver det engelske navn, der er bevaret i kataloget. Begge typer er gyldige spørgsmål i kabinettet.

oracle_table.csv

Tegnet på position i er oraklets answer på question i række i:

• 1 = yes;
• 0 = no.

Oraklet er deterministisk og fastfrosset. Tabellen repræsenterer dets overbevisninger frem for en fuldkommen zoologisk vidensbase, så nogle svar kan være diskutable. Løsningen skal optimere politikken til de faktiske responses, der er gemt i tabellen.

Hvad I skal indsende

Upload et arkiv med følgende struktur:

1submission.zip2└── submission.csv

submission.csv skal ligge i arkivets rod. Arkivet må ikke indeholde andre filer.

CSV-filen skal indeholde præcis følgende kolonner:

1id,subtaskID,answer

• id — entydig numerisk identifikator for knuden;
• subtaskID — altid 1;
• answer — beskrivelse af knuden.

Rodknuden skal have id = 0.

Upload ikke submission.csv direkte. Platformen skal modtage arkivet submission.zip.

Spørgsmålsknude

1Q|question_id|yes_node|no_node

Eksempel:

10,1,Q|Q0001|1|2

Hvis answer på Q0001 er yes, fortsætter bedømmeren til knude 1; ellers fortsætter den til knude 2.

Gætteknude

1G|animal|wrong_node

Eksempel:

11,1,G|agouti|3

Bedømmeren spørger: »Er animal agouti?« Hvis guess er correct, slutter tilfældet. Hvis guess er wrong, fortsætter evalueringen ved knude 3.

Den særlige værdi END betyder, at politikken giver op:

12,1,G|alligator gar|END

Da feltet answer indeholder tegnet |, kræves der no særlig CSV-escaping. Dyrenavne indeholder ikke |.

Budget

For hvert skjult animal er højst 15 kald tilladt.

Hver besøgt knude forbruger præcis ét kald:

• en Q-knude forbruger ét kald;
• en G-knude forbruger ét kald, uanset om guess er correct eller wrong.

Efter det 15th kald slutter tilfældet automatisk.

Pointberegning

For hvert animal:

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

Eksempler:

• correct guess ved det første kald → 0.98;
• correct guess ved det 5th kald → 0.90;
• correct guess ved det 15th kald → 0.70;
• no correct guess → 0.

Den endelige score er:

1100 × mean(score_case)

Den teoretiske maksimumscore er 98, fordi selv et øjeblikkeligt correct guess forbruger ét kald.

Valideringsbegrænsninger

• højst 20,000 knuder;
• knudeidentifikatorer skal være ikke-negative heltal no dubletter;
• knude 0 skal findes;
• question_id skal findes i questions_pool.csv;
• det gættede animal navn skal svare præcist til en post i animals_pool.txt for at være correct;
• en henvisning til en ikke-eksisterende knude får den tilsvarende sti til at mislykkes;
• utilgængelige knuder er tilladt, men de øger unødigt indsendelsens størrelse;
• bedømmeren udfører ikke kode fra arkivet eller fra CSV-felterne;
• arkivet skal indeholde præcis én fil med navnet submission.csv.

Minimalt eksempel

Indholdet af submission.csv:

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

Denne politik stiller ét enkelt question og foretager derefter ét enkelt guess. Den løser kun de tilfælde, hvor de to blade svarer til det skjulte animal.

Bemærkninger

log2(250) ≈ 7.97. I et ideelt træ ville omtrent otte binære svar være nok til at skelne mellem de 250 dyr, men de tilgængelige spørgsmål deler ikke altid kandidatmængden fuldkomment i to halvdele.

En nyttig strategi er at:

1. vedligeholde mængden af dyr, der er forenelig med den aktuelle sti;
2. vælge det question, der deler denne mængde så jævnt som muligt;
3. konstruere grenene yes og no rekursivt;
4. bruge guess knuder, når der kun er meget få kandidater eller kald tilbage;
5. tillade genbrug af identiske undertræer for at reducere antallet af knuder.

Oprindelse og tilpasning

Problemet er en ONIA-tilpasning af notebooken Hjemmeopgave 3 — John Wilkins' analytiske sprog, der er udgivet i IOAI 2026-repositoriet. Den LLM-baserede interaktor blev erstattet med et fastfrosset orakel, så evalueringen forbliver hurtig og deterministisk.