ICFP sacensības 2024

Komanda “Raging Mushrooms”, 26. vieta kopvērtējumā, šogad bija:
— es, Snauts, Cers un introducing Zirgonis, cerīgā vidusskolas paaudze

Nākamajā vīkendā pēc jāņiem jau divos dienā visi bija sabraukuši pie manis, jo jau trijos sākās Sacensības.

No agrākajiem pasākumiem zinot, cik vitāli svarīgi ir ērti uzdevumu un risinājumu vizualizācijas tuļķi, Cers bija gatavojies, iedziļinoties rusta bibliotēkās, visādos axumos un ramhornos, lai pie webiska skatīšanās rīka mēs tiktu ātri, lai vai kādi uzdevumi būtu šogad.

Vairāk neviens neko nozīmīgu priekš sacensībām gatavojis nebija, tamdēļ dīdījāmies, veroties pulkstenī un refrešojot sacensību lapu, it kā tas palīdzētu ātrāk uzzināt, ar ko tad mēs nodarbosimies gan tuvākās divdesmit četras stundas, gan visu nedēļas nogali kopumā.

Intro

Trijos sacensību lapā parādījās uzdevums. Bieža sacensību tēma ir variācijas par kosmosa komunikāciju ar kādu tālu civilizāciju, un tāds bija arī šīgada setings — mums tika iedota tīmekļa saite, kurā iesūtīt kaut ko, un saņemt atpakaļ atbildes no tālajiem citplanētiešiem, kopā ar padomu, ka sākumā varētu iesūtīt ķeburu “S’%4}).$%8”, un tālāk paknibināt stringu sadaļu starpzvaigžņu programmēšanas valodas “Interstellar Communication Function Program” (ICFP :) aprakstā.

Ķebura aizsūtīšana atbildē atdeva blāķi līdzīgu ķeburu pretī un, lasot ne pārāk garo specifikāciju, kļuva skaidrs, ka mēs sūtām kaut kādu kodētu tekstu (jo ķebura pirmais simbols ir S), un atbildē saņemam līdzīgu tekstu pretī, un tā izprašanai tomēr jāsāk kaut kas arī programmēt.

Cers ķērās pie rusta, Snauts — pie kommonlispa, Zirgonis — pie C++, es — pie clojure, un ātri vien atkodējās, ka ķeburos, ko nosūtījām, ir iekodēts teksts “get index”, bet atbildē saņemam šādu sveicienu:

Hello and welcome to the School of the Bound Variable!

Before taking a course, we suggest that you have a look around. You're now
looking at the [index]. To practice your communication skills, you can use
our [echo] service. Furthermore, to know how you and other students are
doing, you can look at the [scoreboard]. After looking around, you may be
admitted to your first courses, so make sure to check this page from time to
time. In the meantime, if you want to practice more advanced communication
skills, you may also take our [language_test].

Kložure + sublime text + clojure sublimed bija super-ērta vide ātriem eksperimentiem, līdz ar ko es ātri izpētīju atzīmētās saites — eho servisu, rezultātu tabulu un valodu testu.

Iebakstot eho servisam, mēs dabūjām pirmo punktu, pakustējāmies līderbordā — un sacensības sākās pa īstam.

Language test

Valodu tests atgrieza ķeburu virkni, kura nebija vairs vienkāršs teksts, bet jau programma jocīgajā ICFP valodā.

Līdz darbojoša valodas evaluatora izveidei bija vēl tālu, tomēr ātri kložurē uzrakstītais parseris parādīja, ka šī valodas testa kods veic padziļinātu pārbaudi, vai vide, kurā tas griežas, korekti veic visas operācijas (te var uz to pavērties parsēta koka izskatā) un, ja visi testi tiek izieti, tad, skat skat —

   [:str
     [:str
       "Self-check OK, send `solve language_test "
       [:int-to-string [:plus 2 [:mult 311 124753942619]]]]
     "` to claim points for it"]

likās acīmredzami, ka to varētu atrisināt arī tāpat vien, jo jānosūta teksts solve language_test, galā pieliekot par tekstu pārkodētu ekspresijas (2 + 311*124753942619) rezultātu.

Tomēr mēģinājumi iesniegt atbildi, mokot skaitli 38798476154511 caur programmas skaitļu enkodēšanas procedūru gan nedeva rezultātus, atbilde nekādi netika pieņemta. Šī šķietami vienkāršā uzdevuma izpilde tā arī palika karājoties gaisā vēl kādu laiku, līdz Snauts nepabeidza savu evaluatoru, iebraucot neacīmredzamajās specifikācijas int-to-string niansēs un tā uzzinot gala atbildi “solve language_test 4w3s0m3”.

Lambdamanis

Vai nu pēc veiksmīgas iebakstīšanas eho servisam, vai vienkārši pēc kāda laika, konstatējām, ka mūsu komandai ir pieejami arī uzdevumi lambdaman un spaceship.

Lambdamaņa uzdevums sastāvēja no 21 labirinta, caur kuriem ar burtu strīpu UDLR (uz augšu-leju-kreisi-labi) personāžam jāizstaigā visa istaba. Jo īsāks risinājums, jo labāk.

Pirmie līmeņi sastāv no vienkāršiem labirintiem, kurus triviāli ir atrisināt ar roku (L norāda sākuma pozīciju):

###.#...
...L..##
.#######

divdesmitais jau ir 256x256, lūk, kompaktas bildītes izskatā:

Pēdējais, divdesmit pirmais uzdevums bija dots tik baisas programmas izskatā, ka tai būs jāgaida vēl vairākas stundas, līdz Cers pabeigs savu ruņītāju, kurš, kaut negausīgi rija tam pieejamo atmiņu, tomēr galu galā uz “da labi, tikai trīs eiro stundā” paņemta mākoņservera ar simts gigabaitiem rama, izdvesa tajā iekodēto 200x200 karti.

Zirgonis ar Snautu metās rakstīt katrs savu labirintu staigātāju, un ātri vien pirmajiem padsmit uzdevumiem radās itin glīti risinājumi, punkti lija kā no krāna, līderbordā stabili svempāmies uz augšu un pasaule izskatījās rožaina — līdz uzmanība pievērsās nelaimīgajam sestajam uzdevumam.

Redz, sestā uzdevuma labirints ir taisna, divsimts baitus gara strīpa bez krustojumiem, kam vienīgais risinājums ir taisns skrējiens vienā virzienā. Tai pat laikā, spriedzes palielināšanai, visiem uzdevumiem vienmēr bija pieejams labākā risinājuma rezultāts, un šim uzdevumam labākais risinājums bija nevis 200, bet gan 150 baitus garš. Simtu piecdesmit! Kā tas vispār iespējams?!

Iedziļināšanās specifikācijā, šis reti sastopamais superpowers, deva atbildi — nav jau obligāti iesniegt risinājumu kā teksta virkni, jo var iesniegt programmu šai maģiskajā valodā, kura šo virkni uzģenerēs!

Ar šo atklāsmi Snauts metās rakstīt RLE kompresijas-dekompresijas algoritmu — universāla programma, kura sastāvēs no maza dekodera un konkrētā labirinta datiem, nosacīti “200L”, būs taču tik īsa — un tas bija veiksmīgs, if ļoooti netriviāls eksperiments, jo izmantojamā valoda ir balstīta uz lambda calculus (labs latviskojums šķiet “funkciju aritmētika”) kas ir visai piņķerīga teorētiskās datorzinātnes nozare, kura apraksta datora veicamās operācijas stingri matemātiskā, yet smagnēji izmantojamā formā, tālu no pierastām sintaksēm un ērtībām.

Šī tēma — arvien optimālāki un kompresējamāki lambdamaņa labirinta risinājumi jocīgajā valodā — arī bija Snauta galvenais lauciņš līdz pat sacensību beigām, un viņš regulāri priecēja mūs ar jaunām idejām un atklāsmēm, demonstrējot savus risinājumus, kuriem mēs varējām vien māt ar galvu, vērojot viņa rakstītās neuztveramās lambdu virknes un to, kā mūsu rezultāti lambdamanī neatlaidīgi uzlabojas.

Speisšips

Kosmosa kuģa uzdevums bija kā kaut kas no tradicionālās ziemassvētku koda adventes iznācis: tev ir kosmosa kuģis koordinātēs 0,0, un saraksts ar koordinātēm, kurās jāpiestāj. Katrā gājienā var palielināt vai samazināt paātrinājumu pa x vai y asīm par 1 un, iespējami optimālā maršrutā, jāapmeklē visas sarakstā norādītās koordinātes. Viss, ej un lido cauri divdesmit pieciem šādiem uzdevumiem.

Man prātā bija veids, kā to atrisināt sūdīgi, un sūdīgs, bet esošs risinājums ir jūtami labāks par labu, bet neesošu risinājumu — un mana pirmā versija bija tieši tāda. Algoritms, kurš virza kuģi pa koordinātēm secīgi no vienas kartes malas uz otru, ar vienkāršu funkciju, kura spēj no koordinātes N1 un sākotnējā paātrinājuma 0 izdot tādu paātrinājumu-palēninājumu strīpu, lai tas kaut cik ciešami aizietu uz N2 un apstātos — un tad pielietot to vienlaicīgi gan X, gan Y koordinātei.

Šis neveiklais, super-neoptimālais algoritms sagrāba kaut kādus punktus lielākajā daļā uzdevumu, un es sāku rakstīt maršruta vizualizētāju sveltē, lai, ieraudzījis kāda uzdevuma izvēlēto maršrutu, saprastu, ka, kaut arī šis piegājiens darbojas, uzvaru tas nenesīs:

Beigu beigās kosmosa kuģa navigācijas algoritma mīcīšana pārvērtās par manu galveno izpriecu sacensībās, un šim konkrētajam lambdas simbolam uz sacensību beigām viens no labākajiem maršrutiem (vai varbūt vnk glītākais, kurš man saglabājies skrīnšotu mapē, kas to vairs atceras), ir šāds:

Efišensijs

Vienam no kosmosa kuģa līmeņiem pa vidu bija maza, nevainīga izteiksme: (concat ... "[/etc/passwd]" ... ), un tas likās kā mājiens sistēmai palūgt get /etc/passwd, kas atdeva sveicienu un lūgumu ielogoties, kā arī rindiņu ar lietotāja datiem headmaster:945f3fc449518a73b9f5f32868db466c. Meklētājs pavēstīja, ka virtene ir md5(“lambda”), un mēģinājums ielogoties ar šādu lietotāju — aizsūtot “login headmaster lambda” — beidzās ar apsveikumu, un tiesībām spēlēties ar efficiency grupas uzdevumiem.

Efišensiji bija trīspadsmit programmas icfp-valodā, kuri ātrāk-kosmoss-izbeigsies-nekā-atnāks-atbilde veidā veica kādu aprēķinu, galu galā izdodot kādu milzonīgu skaitli, un mūsu uzdevums bija šos skaitļus atklāt.

Visi uzdevumi tika atrisināti vienā no diviem veidiem:

a) izpētot, ko viņi dara. Es itin labi iemanījos lasīt parsētās programmas un izlobīt no tām esenci, piemēram, no šādas drausmas izprast, ka skaitlis tiek sadalīts pa bitiem, un pārbaude sastāv no kaudzītes rūļu “24. bits = 23.bits” “29. bits != 11. bits”, un skaitlim jāatbilst visiem nosacījumiem — un uzrakstīt solveri jau bija tehnikas jautājums,

b) izmantot Cera uzrakstīto evaluatoru, sameklēt programmā lielāko skaitli, kurš atbild par kaut kādu iterāciju skaitu, un nomainīt to uz 1, 2, 3, … ruņīt programmu un meklēt likumsakarības ātri iegūtajos rezultātos. Tā konstatējām, ka viena programma ģenerē fibonači virkni, cita meklē pirmskaitļus, bet cita kaut ko nesaprotamu, tomēr tās rezultējošais skaitlis būs pavisam neliels, zem simta — atrodams ar nelielu pārlasi.

Trīs Dē

Iesūtot kosmosa kuģa risinājumus, vienubrīdi atbildēs parādījās ziņa, ka, par cik mēs esam atrisinājuši piecus kosmosa kuģus, mēs nu esam pielaisti pie 3d uzdevuma. To bija prieks uzzināt, jo turnīra tabulā redzējām komandas, kuras to sākušas risināt, bet mums vēl nebija radusies skaidrība, kā pie šiem uzdevumiem vispār piekļūt.

Trīsdē bija ezotēriska programmēšanas valoda, factorio spēles un breinfaka krustojums, kur uz rūtiņu laukuma izvietoti operatori grūstīja un bīdīja skaitļus apkārt (piemēram, strīpiņā 3>.>. uz kāsīšiem var skatīties kā uz bultiņām, kuras katrā gājienā aizgrūž trijnieku tālāk — nākamie soļi ir .>3>. un .>.>3), līdz kāds skaitlis tiek uzgrūsts uz lauciņa ar “S”, finišējot un atgriežot atbildi — vai uztrāpot uz @, un tad nostrādā “laika mašīna”, padzenot vidi atpakaļ uz kādu senāku stāvokli, bet jau ar jauniem ievaddatiem, un tamlīdzīgs ķīselis.

. 1 . 0 . A . 1 . 0 . A
A - . = . + A + . = . -
. . v . . S . . v . . S
. . . . . 0 . . . . . .
. 2 @ 3 A = . 2 @ 3 . .
. . 2 . . S . . 2 . . .

Šī valoda bija tik biedējoša, ka tam ķērāmies klāt tikai nākamajā diennaktī, uz lightning roundu (pirmajām 24 stundām) ne tikai neiesūtot nevienu šī uzdevuma risinājumu, bet pat nopietni nesākot ķerties klāt vispār.

Lai cik bailēm lielas acis, tomēr sestdien ceļa atpakaļ vairs nebija. Paknibinoties teksta editorā ar šādu brīnumu rakstīšanu, likās, ka bez īsta editora dzīves nebūs, un Cers ar savām iestrādnēm izveidoja — un turpināja visu sacensību gaitā attīstīt — ērtu webisku editoru-ruņītāju šai valodai, kurš mācēja kopēt, peistot, spert soļus uz priekšu un atpakaļu, un visādi citādi izdarīties.

Uzdevumi — kopumā divpadsmit — no sākuma izklausās īpaši triviāli, piemēram, atrast lielāko no diviem skaitļiem, aprēķināt skaitļa absolūto vērtību (-1 → 1, 20 → 20, nekas vairāk) etc, taču tos sarežģī ne tikai tas, ka visi aprēķini notiek, skaitļiem šļūkājot pa plakni, bet arī atbalstīto operāciju klāstā nav triviālas salīdzināšanas “vai X ir lielāks par Y?” — tiekai vienādība un nevienādība. Tā rezultātā if a > 0 then a else -a pārvēršas par briesmīgiem, smagnējiem cikliem un ko tik vēl ne.

Cers metās ar galvu iekšā uzdevumos, kļuva par valodas lielmeistaru un līdz sacensību beigām bija atrisinājis desmit uzdevumus no divpadsmit.

Finišs

Atšķirībā no pagājušajiem gadiem, kad pēc divdesmit četrām stundām uzdevumu noteikumi tiek modificēti, parādās jauni līmeņi u.tml., šogad tas nenotika, tikai visas uzdevumu klases tika pavērtas vaļā visiem dalībniekiem — t.i nu ikviens varēja risināt efišensijus un visu pārējo arī, ja nebija atrasti slēptie pavedieni.

Uzdevumi šogad bija daudz un dažādi, un galvenā mūsu problēma retrospektīvā bija vien tas, ka nemetāmies pie 3d jau ātrāk. Līdzīgā situācijā uzreiz jāsākt kaut ko bīdīt arī ar nejaukāko problēmu, un, iespējams, ar vairāk kopdarba — uzdevums prasīja tādu iedziļināšanos, ka atrisināt pēdējos divus uzdevumus mēs Ceram palīdzēt nevarējām, jo bijām tik ļoti pārāk tālu no izpratnes, ka saturīgi neatrisinātu arī pirmos divus.

Pēc sacensību beigām organizatori, lieki nekavējoties, publicēja katram uzdevumam labāko saņemto risinājumu. Labākie un īsākie labirintu staigātāji izrādījās variācijas par triviāliem random-walkiem, lielā garumā vazājoties nejauši izvēlētos virzienos, jo pret sienām sisties bija atļauts. Tā bija neliela vilšanās, jo iztēle bija uzzīmējusi super-optimālus risinājumus.

Bez tā — viss bija super-izcili (iekļūt divdesmitniekā būtu bijis vēl superāk un izcilāk, bet nu), nākamgad rausim atkal.