John Wilkins' analytiske språk - deterministisk orakel

🗄️ Distinksjonenes kabinett

Historie

I det syttende århundret forsøkte John Wilkins å konstruere et fullkomment språk: Navnet på en ting skulle avsløre dens plass i en klassifikasjon bygget opp av YES/NO-distinksjoner.

Prosjektet ble oppgitt, men en ukjent skriver fortsatte å samle dyr i et enormt Distinksjonenes kabinett. Hver skuff skjuler en skapning. Etikettene har gått tapt, og messinggitteret på hver skuff besvarer bare binære spørsmål om animal inni.

Følgende opptegnelser har overlevd fra arkivet:

• animals_pool.txt — de 250 dyrene som kan forekomme i kabinettet;
• questions_pool.csv — de 280 tillatte spørsmålene;
• oracle_table.csv — de frosne orakel-responses for hvert (animal, question)-par.

Dere må utforme en adaptiv policy som identifiserer animal med så få kall som mulig.

Tilpasning for arkivbasert evaluering

I den interaktive versjonen ville programmet etter tur kalle:

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

I den nåværende versjonen kjører plattformen imidlertid ikke en interaktor i sanntid. Derfor må dere sende inn beslutningstreet som programmet deres ville utføre. Evaluereren starter ved node 0, konsulterer det private orakelet og følger den tilsvarende grenen for hvert answer.

Treet kan faktisk være en rettet graf: Flere grener kan føre til den samme noden. Sykler er ikke nyttige, fordi hvert besøk i en node forbruker ett kall, og budsjettet er strengt.

Oppgitte data

animals_pool.txt

Ett animal navn per linje. Bare disse navnene kan gjettes.

questions_pool.csv

Semantiske spørsmål beskriver biologiske eller økologiske egenskaper. Leksikalske spørsmål beskriver det engelske navnet som er bevart i katalogen. Begge typer er gyldige spørsmål i kabinettet.

oracle_table.csv

Tegnet i posisjon i er orakelets answer på question i rad i:

• 1 = yes;
• 0 = no.

Orakelet er deterministisk og frosset. Tabellen representerer dets oppfatninger, ikke en fullkommen zoologisk kunnskapsbase, så noen svar kan være diskutable. Løsningen må optimalisere policyen for de faktiske responses som er lagret i tabellen.

Hva dere må sende inn

Last opp et arkiv med følgende struktur:

1submission.zip2└── submission.csv

submission.csv må ligge i roten av arkivet. Arkivet må ikke inneholde noen andre filer.

CSV-filen må inneholde nøyaktig følgende kolonner:

1id,subtaskID,answer

• id — unik numerisk identifikator for noden;
• subtaskID — alltid 1;
• answer — beskrivelse av noden.

Rotnoden må ha id = 0.

Ikke last opp submission.csv direkte. Plattformen må motta arkivet submission.zip.

Spørsmålsnode

1Q|question_id|yes_node|no_node

Eksempel:

10,1,Q|Q0001|1|2

Hvis answer på Q0001 er yes, fortsetter evaluereren til node 1; ellers fortsetter den til node 2.

Gjettenode

1G|animal|wrong_node

Eksempel:

11,1,G|agouti|3

Evaluereren spør: «Er animal agouti?» Hvis guess er correct, avsluttes tilfellet. Hvis guess er wrong, fortsetter evalueringen ved node 3.

Spesialverdien END betyr at policyen gir opp:

12,1,G|alligator gar|END

Fordi feltet answer inneholder tegnet |, kreves no spesiell CSV-escaping. Dyrenavn inneholder ikke |.

Budsjett

For hvert skjult animal er høyst 15 kall tillatt.

Hver besøkte node forbruker nøyaktig ett kall:

• en Q-node forbruker ett kall;
• en G-node forbruker ett kall, uavhengig av om guess er correct eller wrong.

Etter det 15th kallet avsluttes tilfellet automatisk.

Poengberegning

For hvert animal:

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

Eksempler:

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

Sluttpoengsummen er:

1100 × mean(score_case)

Den teoretiske maksimale poengsummen er 98, fordi selv en umiddelbar correct guess forbruker ett kall.

Valideringsbegrensninger

• høyst 20,000 noder;
• nodeidentifikatorer må være ikke-negative heltall no duplikater;
• node 0 må finnes;
• question_id må finnes i questions_pool.csv;
• det gjettede animal navnet må samsvare nøyaktig med en oppføring i animals_pool.txt for å være correct;
• en referanse til en ikke-eksisterende node gjør at den tilsvarende banen mislykkes;
• utilgjengelige noder er tillatt, men de øker størrelsen på innsendingen unødvendig;
• evaluereren kjører ikke kode fra arkivet eller fra CSV-feltene;
• arkivet må inneholde nøyaktig én fil med navnet submission.csv.

Minimalt eksempel

Innholdet i submission.csv:

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

Denne policyen stiller ett enkelt question og foretar deretter én enkelt guess. Den løser bare tilfellene der de to bladene samsvarer med det skjulte animal.

Merknader

log2(250) ≈ 7.97. I et ideelt tre ville omtrent åtte binære svar være nok til å skille mellom de 250 dyrene, men de tilgjengelige spørsmålene deler ikke alltid kandidatsettet fullkomment i to halvdeler.

En nyttig strategi er å:

1. vedlikeholde mengden dyr som er kompatibel med den nåværende banen;
2. velge question som deler denne mengden så jevnt som mulig;
3. konstruere grenene yes og no rekursivt;
4. bruke guess noder når svært få kandidater eller kall gjenstår;
5. tillate gjenbruk av identiske deltrær for å redusere antallet noder.

Opprinnelse og tilpasning

Problemet er en ONIA-tilpasning av notatboken Hjemmeoppgave 3 — John Wilkins' analytiske språk, publisert i IOAI 2026-repositoriet. Den LLM-baserte interaktoren ble erstattet med et frosset orakel slik at evalueringen forblir rask og deterministisk.