How does a computer work?
As some of you likely know, inside your computer are millions (or even billions) of little men.
Those men are constantly dashing around to find and execute simple instructions. An instruction might, for example, tell a little man to add or subtract two numbers or send a message to another little man.
Такими словами начался ICFP Contest 2026 в прошедшие выходные. Я как раз последние дни слушал книжку 1Q84, где фигурируют мистические существа, которые там называются Little People. Хорошо совпало.
Тут в соревновании нужно было писать программы в виде 2D карт: программа состоит из набора прямоугольных комнат, в каждой комнате ходит по клеточкам человечек, выполняя инструкции, записанные в этих клеточках. У человечка есть два регистра А и В для арифметических операций, вроде A = A + B, A = A * B и т.п., и еще один регистр для циклов, куда можно записать число, можно уменьшать на единицу, и можно поворачивать или нет в завивимости от того, ноль там уже или еще нет. Также есть команда поворота, где направление определяется знаком регистра А. Комнаты могут соединяться трубами, по которым человечки могут посылать друг другу числа (из регистра А). Числа по трубе идут небыстро - по клеточке за такт. Есть две особых комнаты I и O - Input и Output.
Еще там бывают экраны, где можно рисовать по пикселям картинки, но их я не касался.
Вот так, например, выглядит программа, получающая на вход число n и вычисляющая 1 + 2 + 3 + ...n.

Человечек начинает в клетке @ и двигается вправо пока команда v не повернет его вниз, а < влево.
По пути он тут выполняет следующие команды:
r: A = input number
M: B = A
*: A = A*B
+: A = A+B
M: B = A
2: A = 2
W: swap A and B
/: A = A / B
s: send A to output
Так вычисляется (n*n+n)/2, искомый ответ.
Количество очков зависит от размера программы (максимум из длины и ширины) и количества операций.
Что забавно, эта первая программа была такая простая, что все ее быстренько как-то решили и побежали дальше, не пытаясь оптимизировать. У меня она сперва помещалась в квадрат 9х9, но потом я к ней вернулся и уместил в 8х8. Такая оптимизация привела к тому, что мое решение оказалось лучше всех:

rank 1 of 267 означает, что на тот момент из решений 267 команд это мое на 1-м месте.
В других задачках мои решения были довольно посредственные, но я там и не пытался сильно оптимизировать, мне было интересно просто получить что-то работающее. Например, в другой задачке программа должна была сортировать списки чисел. Причем не один, а именно несколько разных списков по очереди. На входе список из N чисел кодировался последовательностью из N+1 чисел, где самое первое было N - длина. Тут вопрос был в том, как вообще оперировать набором чисел неизвестной заранее длины, если у человечка всего две руки, два регистра, и большинство операций задействуют их оба. Решением оказалось запихать их всех в трубу и гонять по кругу, так труба становится памятью для последовательности чисел. По правилам труба из комнаты нe может приходить в нее же, пришлось сделать вторую комнату, откуда приходящие числа по второй трубе возвращаются в исходную комнату.

В основной же комнате человечек смотрит на приходящие числа, сравнивая каждое с предыдущим и отправляя дальше меньшее из двух, так за один круг последовательность проходит через одну итерацию сортировки пузырьком. Если ни разу за проход порядок чисел не был изменен, то последовательность уже отсортирована и осталось ее отправить на выход. Но вот беда, у нас нет третьего регистра, чтобы помнить делали мы перестановку или нет. Вместо этого состояние кодируется местоположением человечка: его цикл инструкций был продублирован рядом, и исходно он бегает по первому циклу, и если делает перестановку чисел, то переходит во второй такой же цикл. Когда первый или второй цикл кончается (закончилась одна итерация обработки списка), то если это закончился первый цикл, значит ни одной перестановки чисел не было в этой итерации и можно переходить к выводу. Если же человечек закончил второй цикл, значит перестановки были, и нужно продолжать итерации, возвращаемся к первому циклу.
В еще одной задачке нужно было проверять последовательности вроде [(){}]{[(){[(]}[]]} на сбалансированность скобок. Скобок три вида, и тут нужен стек. Но сказано, что максимальная глубина вложенности во входных последовательностях - 32. А числа в регистрах 64-битные. Т.е. в регистр как раз можно уместить 32 значения от 0 до 3! Но вот беда, чтобы сравнить входной символ с константой (ASCII кодом какой-то скобки) уже нужны оба регистра. Где же хранить стек? Пришлось привлечь еще человечков.

Первый получает на вход ASCII коды - исходные данные, и посылает в следующую комнату команды из двух чисел, где первое 0 или 1 говорит кладем мы на стек или снимаем, а второе - 1-3 - тип скобки. По условию, программа должна вернуть 0 если баланс скобок сходится, или позицию (начиная с 1) символа, где скобка неправильная, или N+1 если дошли до конца и не все скобки были закрыты. Т.к. у человечка, хранящего стек, уже не было свободных рук, за позиции и вывод результата отвечал третий человечек. Занимающийся стеком человечек посылал ему 1 каждый раз, когда успешно клал значение на стек или когда снятое со стека значение совпадало с требуемым, но если что-то шло не так или в конце последовательности стек был не пустой, посылал 0 - ошибку. Третий человечек суммировал приходящие единички, чтобы отслеживать позицию, и когда видел сигналы об ошибке или конце данных, посылал на выход накопленную позицию или 0 если все ок.
Чтобы в регистр записать число от 0 до 9, достаточно просто поставить такую цифру на пути человечка. Для чисел больше 9 нужно десятичную запись числа взять в кавычки.
Еще в одной задачке на входе ничего не было, а на выход нужно было выдать конкретный текст из почти трех тысяч символов. Вручную такое писать уже не будешь, тут я подключил ИИ, чтобы тот сделал генератор последовательностей команд. Уложил их змейкой, и столкнулся с проблемой, что между кавычками не должно быть ничего кроме цифр и пустых клеток, но не только на пути человечка, а везде - как по горизонтали, так и по вертикали. В программе выше я поэтому выравнивал кавычки по вертикали. Но в программе из 9к операций так делать уже сложно (или очень неэффективно). Потому сгенерил последовательность команд, где такие константы в кавычках не используются вовсе. Такая программа помещалась в квадрат 102х102. Но так просто неинтересно, поэтому я добавил еще простенького сжатия: нашел самые повторяющиеся в тексте последовательности символов (вроде " and "), и три из них закодировал отдельно, заменив одним байтом. Такой слегка сжатый текст уже требовал чуть меньше операций, он отправлялся по трубе во вторую комнату поменьше, где те три особых байта триггерили вывод трех особых последовательностей, а остальные байты передавались на выход как есть. Получилось уместить все в 99х99.

А, еще была задачка про разворачивание списков длиной до 16, ее я решил тупо - 16 труб разной длины, первый элемент идет по самой длинной трубе и приходит последним, последний наоборот по самой короткой и приходит первым, и т.д.
Ну и вот, а за остальные задачки я не брался.