After a successful stint as painters, the denizens of Lambda land are now turning to different artistic endeavors, and starting a new career in music.
Только не Lambda land! Это был сеттинг унылейшей задачи 2017-го года, и даже весьма удачный сиквел 2019-го не смог реабилитировать сеттинг в моих глазах.
Тем не менее, я продолжил читать. Нам предстояло расположить музыкантов на сцене так, чтобы стоящие вокруг неё слушатели получили от концерта максимальное удовольствие. Оно зависело от ряда факторов:
Кроме того, одни музыканты могли «загораживать» других, а в более поздних задачах в зале появились колонны, которые тоже глушили звук.
В общем, задача на оптимизацию. Совсем не впечатлившись, я пошёл смотреть, что успели сделать мои сокомандники. (Я, как обычно, выступал с друзьями-цодингтимовцами).
Выяснилось, что у нас есть инфраструктура для скачивания задач и заливки решений, а также тупейший «солвер», который просто ставит всех музыкантов в угол сцены. Такое решение невалидно, т.к. между музыкантами должно быть не менее десяти единиц расстояния. Так что я первым делом написал чуть более умный вариант, расставлявший исполнителей на прямоугольной сетке. И сильно удивился, когда он не смог решить некоторые задачи! Оказалось, что там много музыкантов и маленькая сцена, и в прямоугольной сетке не хватает узлов. Я написал ещё один солвер, расставлявший музыкантов более плотно, и мы наконец получили свои первые очки.
Также я допилил нашу инфру, чтобы рядом с каждым нашим решением хранился JSON со скором (так как функция его расчёта заметно тормозила). Это позволяло быстрее перерешивать задачи новыми солверами. Чуть позже Гсомикс добавит в JSON поле с названием солвера, сгенерировавшего решение — а потом, с появлением улучшающих солверов, будет сокрушаться, что мы не храним там полную историю ☺ Урок на будущее: запилить такую инфраструктуру сразу, и хранить в ней как можно больше информации о том, как было получено каждое решение. Кто-то из соперников так и поступает:
[…] in the end our winning solvers looked like the following when invoked from the CLI:
greedy+shake{cap=10}+vol10+genetic+genetic
, which would translate into a chain of solver passes with greedy, shake (local optimization in real space) with cycle cap of 10 full cycles, setting volume to 10 and two genetic passes on top. We also implementedload_best
solver, so you could test end-of-chain stuff directly on the best solution in our repo […].
Наутро в командном чатике шли обсуждения каких-то диких идей с производными,
BFGS и ещё чем-то непонятным. Энтузиазма разбираться во всём этом у меня не
было, поэтому я занялся самым простым, что пришло в голову: переделал свои
вчерашние солверы, чтобы они расставляли музыкантов на сетке случайным образом.
Эти алгоритмы быстро нашли улучшения по многим задачам, и я ещё некоторое время
гонял их с xargs -P9
.
Загружая решения, я заметил, что скор задач на сайте отличается от того, что вычисляем мы. Оказалось, что мы неправильно определяем, «загородил» ли один музыкант другого. По условиям правило следующее: отрезок музыкант–слушатель не должен проходить менее чем в пяти единицах расстояния от другого музыканта. Форневер придумал элегантную реализацию: если представить, что отрезок «раздуло» на пять единиц во все стороны, то получится стадион. Нам всего лишь нужно определить, находится ли второй музыкант внутри этого стадиона. В расчёты закралась ошибка: мы проверяли расстояние до прямой музыкант–слушатель, а не отрезка, поэтому стадион получался бесконечно вытянутым и в него попадали «лишние» музыканты.
Я исправил проблему, но многие скоры все равно не сходились с сайтом организаторов. Да что же такое?! К счастью, в этот момент подвезли обновлённую спецификацию. Это традиция ICFPC — каждые сутки или чаще задача из нерешаемой превращается сначала в вообще нерешаемую, а потом в «они там совсем уже, что ли?». В нынешнем обновлении появились колонны и возможность «улучшать» игру музыканта, ставя его рядом с другими исполнителями на том же инструменте. Быстренько запилив поддержку этих фич в скоринг и выпустив таким образом пар, я вернулся к отладке.
Оказалось, что я допустил в скоринге колонн ту же ошибку, которую только что починил для пар музыкант–слушатель. После её исправления скоры стали получше — погрешность 1% относительно тех, что насчитал сайт организаторов — но всё ещё не сходились. После долгого вглядывания в код я наконец-то увидел, что:
С фиксами этих проблем некоторые наши скоры наконец совпали с сайтом организаторов. Но не все. ☹
Фокстран, Гсомикс и Форневер тем временем запилили новый солвер. Идея его проста: строим на сцене сетку, для каждого инструмента вычисляем скор в каждом узле сетки, а затем пытаемся расставить музыкантов так, чтобы максимизировать суммарный скор. Да, здесь не учтены ни колонны, ни влияние других музыкантов, но этого все равно хватило, чтобы сразу превзойти все мои «рандомные» решения.
За окном уже спустились сумерки, а я за весь день всего лишь пофиксил пару багов в скоринге. Нужно было срочно заняться чем-то более плодотворным. Так как мысли продолжали крутиться вокруг расчёта оценок, я естественным образом пришёл к тому, что надо сделать какой-то итеративный алгоритм поиска, а для этого нужно сделать итеративным сам алгоритм скоринга.
Остаток вечера ушёл на то, чтобы разбить формулу скора на составляющие и написать скелет итеративного расчёта. Можно было бы чуток быстрее, но в этом году мы с подачи Форневера писали на F#, поэтому заметная часть времени ушла на гугление синтаксиса. Глубоко в ночи я закоммитил скелет алгоритма и ушёл спать.
Понимая, что дела движутся слишком медленно, я поставил себе максимально простую цель: реализовать все тудушки в итеративном скоринге и запилить поверх него эволюционный алгоритм. Но что-то не задалось. Отчасти по неопытности, а отчасти из-за незнания F# я довольно долго пилил сначала геттеры-сеттеры для составляющих скора, а потом собственно вычисления. В итоге первая рабочая версия появилась только к четырём вечера, и… результат не сошёлся с тем скорингом, что у нас уже был!
Ладно (•̀⤙•́ ) Закатал рукава, пофиксил ошибку копи-пасты, пофиксил индексирование в массивах, пофиксил проверки валидности решения, добавил юнит-тест с задачей из спеки, исправил ещё одну ошибку в «стадионе» (он игнорировал препятствия, если линия музыкант–слушатель была вертикальной). Юнит-тест прошёл, но по сравнению с имевшимся скорингом мой алгоритм работал ужасно медленно.
Тем временем в командном чате пишут, что у нас закончились бесплатные минуты GitHub Actions.
Для оптимизации итеративного скоринга, конечно, пригодился бы профилировщик, но я разрабатываю без IDE, поэтому оптимизировал «на глаз». Итеративный скоринг с самого начала строился вокруг персистентных массивов, которые копируются при каждом изменении, так что стал смотреть на них. Первым делом поменял сеттеры, чтобы они не меняли массив, если элемент уже имеет нужное значение — это дало ускорение в несколько раз.
Других явных проблем я не видел, поэтому взялся за микрооптимизации, а именно расположение данных в памяти. Классы-составляющие хранили матрицы, например, матрицу расстояний музыкант–слушатель. Естественно, в памяти это представлялось одномерным массивом, а индексы пересчитывались по нехитрой формулке. Я ожидал получить заметный прирост производительности, расположив данные в более удобном для программы порядке, но как ни старался, разницы на глаз не заметил.
Пока возился с индексами, наступило прозрение: для изменения любого элемента матрицы мне приходится копировать её целиком! Переведя код на вектора Илиффа, я получил десятикратный прирост производительности и наконец достиг паритета производительности с нашим «неитеративным» скорингом.
Правда, результаты по-прежнему не сходились ни с имевшимся скорингом, ни с сайтом организаторов.
На часах было 11 вечера, а из-за работы это был последний день, когда я могу играть. Пока я занимался итеративным скорингом, мысль о локальном поиске трансформировалась сначала в эволюционный алгоритм, а затем в имитацию отжига. Времени его реализовать не оставалось, поэтому я попытался объяснить смысл итеративного скоринга Форневеру в надежде, что в понедельник он сам сможет что-то запилить. Фокстран тоже заинтересовался, но так ничего и не реализовал.
Заодно кратко обсудили последнее обновление задачи, в котором музыкантам добавили громкость. Она варьировалась от 0 до 10, на неё умножался скор каждого музыканта. Гсомикс не видел в громкости никакого толку, и все наши решения задавали десятку всем музыкантам. Мне с трудом верилось в бесполезность этого обновления, поэтому я взял какой-то из наших «улучшающих» солверов, использующий метод Нелдера — Мида, и поправил его, чтобы оптимизировалась громкость. К сожалению, это не дало улучшений ни по одной из опробованных задач, поэтому я в расстроенных чувствах почапал спать.
Уже стоя под душем, я вдруг допёр, что на самом деле у громкости есть польза: с её помощью можно заглушить музыкантов с негативным скором! И, конечно же, это легче всего сделать с помощью итеративного скоринга, потому что:
Поэтому я вернулся за клавиатуру и быстренько запилил новый «улучшающий» солвер под названием suosi — «shape up or ship out». Он брал готовое решение, выставлял всем музыкантам единичную громкость, считал скор, а затем менял громкости в зависимости от скора каждого музыканта — кто-то получал 0, а остальные 10. Этот солвер смог-таки улучшить некоторые решения, но на смешные сотни тысяч единиц; общий скор решения к тому моменту мог превышать миллиард.
Сдав работу коллегам и попросив Форневера погонять suosi на остальных, более крупных задачах, я всё же ушёл спать.
На момент заморозки скорборда мы были 51-ми из 155-и (или 161, если считать тех, кто не решил ни единой задачи). Не самый блестящий наш результат, но и не худший; так, средненький. Окончательные результаты будут объявлены в сентябре во время конференции ICFP.
Задача понравилась. Я не сразу загорелся энтузиазмом, но потом втянулся, и в воскресенье было сложно засыпа́ть — голова кишела мыслями о том, что ещё можно было бы предпринять.
F# мне понравился маржинально больше, чем Scala. Да, с ним тоже приходится разбираться по ходу дела; да, я не знаю дотнетовских апишек; да, моя производительность далека от той, которую я достиг бы на «своём» языке. Тем не менее, язык вполне юзабельный, можно применять (раз в два года :)
В шаблон проекта обязательно надо добавлять не только юнит-тесты, но также проперти-тесты и, возможно, бенчмарки. Уже в процессе написания этого отчёта я понял, что отличия между итеративным и «неитеративным» скорингом проще было бы отлаживать, напиши я проперти-тест на их эквивалентность.
В этом году Фокстран, Гсомикс и Форневер хорошо скооперировались, Портнов отвалился после первого дня, а мы с Аконом работали в основном в одиночку. Сложно сказать, хорошо это или плохо. Я, например, получил море фана за те два дня, что пилил итеративный солвер. Мне греет душу, что написанные мной солверы держали нас в лидерборде весь первый день. В общем, нам удалось поймать какой-то локальный оптимум, где нашлось место и кооперации, и индивидуализму.
За сим откланиваюсь. Если есть желание — поглядите на наш код на GitHub, а если желания нет — почитайте отчёт Форневера с более подробной хроникой работы всей команды. И до встречи в лидерборде ICFPC 2024!
]]>Some other boards provide a virtual COM port: you connect them to the computer
and use screen
, minicom
or even echo
to communicate with USART1
. Not so
with STM32F411E, because its ST-LINK debug probe is only V21, which does
not support a virtual COM port2. This is a hardware limitation; you can’t
fix it by upgrading ST-LINK firmware or re-installing the drivers.
The solution is to get an external USB-to-UART dongle and connect it to the board’s pins. That’s when you run into the second problem…
PA9
and PA10
don’t workThe first UART peripheral, USART1
, can be connected to two sets of MCU pins:
(PA9
, PA10
) and (PB6
, PB7
). Unfortunately, the Discovery board re-uses
the first set for the USB peripheral. If you try to use UART with PA9
and
PA10
, you’ll see the green LED at the bottom of the board light up — but no
signals on UART.
That’s why you should use the second set of pins, or one of the other two USART
peripherals (USART2
or USART6
).
see UM1842, User Manual, Discovery kit with STM32F411VE MCU, in ST’s documentation section↩︎
see TN1235, Technical Note, Overview of ST-LINK derivatives, in ST’s documentation section↩︎
Вопреки традиции, отпуск мне взять не удалось, поэтому к команде я присоединился только вечером пятницы, спустя четыре с половиной часа после начала соревнования. Задание (зеркало) вызывало лёгкое ощущение дежавю: создавая прямоугольные трафареты и закрашивая сквозь них полотно, мы должны были как можно быстрее и точнее воспроизвести заданную картинку. Самих картинок-задач под конец соревнования набралось аж 40 штук, причём они варьировались от обманчиво-тривиальных изображений Тетриса до вполне реальных картин вроде «Крика» Эдварда Мунка. В общем, классика ICFPC: задание, которое легко объяснить, но сложно выполнить.
Решение нужно было записать при помощи специального языка из пяти команд: разрезать полотно на кусочки («блоки») по горизонтали, вертикали или на четыре части, поменять два кусочка местами, склеить два кусочка или закрасить кусочек определённым цветом. За каждое действие мы платили цену, причём за действия над мелкими кусочками гораздо больше, чем за действия над крупными. Кроме того, учитывалась степень похожести результата на заданную картинку; она вычислялась как сумма отклонений цветов каждого пикселя.
В этом году мы писали на Haskell, так что пытаться понять наш код совершенно бесполезно ☺ Давайте я просто расскажу, как мы три дня пытались хоть что-то решить.
Когда я после работы завалился в командный чатик, portnov и ForNeVeR уже придумали тривиальную стратегию: измельчить полотно на однопиксельные кусочки и закрасить их необходимыми цветами. Дорого, зато «степень похожести» идеальная, т.е. нулевая. В это же время sergevp, у которого не было возможности играть все три дня, вывалил мне в приват полноценный план работ, тоже включавший эту идею.
К сожалению, получившиеся решения нельзя было отправить, потому что они не влезали в установленный организаторами двухмегабайтный лимит. Поэтому первое, что я сделал — это залил для всех задач пустое решение, состоявшее из одного только комментария «# nothing». Так как турнирная таблица сортировалась сначала по убыванию количества решённых задач, а затем по возрастанию стоимости решений, то мы сразу попали на восьмое место. Чудно!
Дальше я занялся оценщиком решений — вернее, интерпретатором, потому что для вычисления оценки нужно знать площадь задействованных в команде блоков. Тут меня ждала засада.
Условие задачи было сформулировано так, будто бы у блоков (кусочков полотна) есть иерархия: они делятся на «простые», которые залиты одним цветом, и «сложные», состоящие из нескольких простых. Кроме того, у каждого блока есть идентификатор, например «0», и при разрезании блока из него образуются блоки с идентификаторами «0.0» и «0.1». Мы, естественно, смоделировали это деревом. Теперь же я сидел и думал, как реализовать команду склеивания блоков: если разрезать полотно по горизонтали, затем каждую половинку разрезать по вертикали, а потом попытаться склеить четвертинки, принадлежащие разным половинкам, то придётся обновлять всю иерархию, начиная с корня!
Вообще-то деревья — это моя любимая структура данных, но такие широкомасштабные
манипуляции даже для меня были чересчур. Поэтому я решил попробовать другое
представление: хранить отображение из идентификатора блока в его положение
и размеры (Map BlockId Shape
), а также отображение из идентификатора блока во
множество идентификаторов блоков, которые он содержит (Map BlockId (Set BlockId)
). Успешно реализовав поверх этого все виды разрезов, я принялся за
команду объединения — и обнаружил, что она опять не получается! В этот раз
мешало то, что у простых блоков, находящихся внутри сложного, нет
идентификаторов — они теряются, когда блоки объединяются. Таким образом, второе
отображение вообще не имело смысла, т.к. я ничего не мог положить во множества.
Тут мне в голову полезли мысли о том, чтобы создать матрицу, в ячейках которой хранить идентификатор соответствующего пикселю блока. Правда, искать границы блоков в этом случае пришлось бы с помощью заливки, для оптимизации которой пришлось бы опять создавать отображение из идентификатора в положение и размеры…
Портнов тем временем сделал разрезалку полотна на четыре части и заливку каждого квадранта его средним цветом, но это почему-то давало оценки хуже, чем у моего «пустого» решения. Видимо, операции заливки обходились настолько дорого, что их не удавалось компенсировать улучшением «похожести».
Спать я ушёл в подавленном настроении. Бывало, конечно, чтобы мы не могли придумать или реализовать ни единой рабочей стратегии, но чтобы не удавалось даже написать структуры данных — это было впервые.
Мысли про матрицу идентификаторов не давали уснуть, и в полвторого ночи меня наконец осенило — достаточно разделить сущности! Нужно хранить отдельно — текущее состояние полотна (т.е. картинку) и отдельно — данные обо всех существующих блоках. Всё! Отсюда, кстати, и метафора про трафареты в начале этого поста: программа либо меняет существующие трафареты, разрезая и объединяя их, либо меняет полотно, раскрашивая его сквозь какой-то из трафаретов. К трём часам ночи интерпретатор был готов, и я, отчитавшись в чате, отправился спать.
Пока я спал, Портнов реализовал вычисление «похожести», а ещё написал скрипты
для заливки решений — теперь это можно было сделать одним вызовом, а не в шесть
кликов в браузере. После (позднего) завтрака я занялся допиливанием
интерпретатора до полноценного оценщика, чтобы он не только рисовал финальную
картинку, но и вычислял стоимость решения. К полвторого код был готов, но
результаты почему-то не сходились с вычислениями на сайте организаторов.
В итоге оказалось, что разность цветов у нас хранится в однобайтовых
переменных, которые иногда антипереполняются, а результат
квадратного корня мы храним во Float
, которому иногда не хватает точности.
Классика. Перевёл всё на Double
— и результаты наконец сошлись. Потом ещё
обнаружилось, что на длинных решениях оценщик сжирает всю память, но это
оказалось (вполне предсказуемой) проблемой с ленивостью, и deepseq
быстро
привёл всё в норму.
Тем временем организаторы выкатили обновлённую спецификацию. Это, кстати, фишка ICFPC — задача в целом не меняется, но время от времени выходят обновления, привносящие усложнения и сюрпризы. В этом, первом, обновлении организаторы добавили задачи с заранее раскрашенными полотнами и уже нарезанными блоками. Теперь нужно было не просто нарисовать что-то с нуля, а дорисовать или перерисовать то, что уже есть. Ощущение дежавю немного усилилось — ровно такое же обновление было в 2018-м году. Первой идеей было свести задачу к предыдущей: объединить все блоки обратно в один большой, а затем решать задачу уже существующими солверами. Портнов занялся парсером нового формата задач, а Форневер трудился над алгоритмом вырезания заданного прямоугольника из полотна.
Тут в чатик нагрянул Akon32 и, быстро сориентировавшись, взялся оптимизировать вычислялку среднего цвета в заданной области. У Портнова был солвер, пытающийся подобрать точку разрезания полотна так, чтобы заливка получившихся кусочков их средними цветами давала бы наилучший результат; этот солвер дико тормозил из-за неэффективности вычисления среднего. Akon32 намеревался помочь делу, используя интегральное представление изображения, которое должно было дать расчёт суммы пикселей за константное время.
В интерпретаторе тоже было что оптимизировать, чем я и занялся. Похоже, источником тормозов была команда, заливавшая область определённым цветом: полотно хранилось в виде иммутабельной картинки, и для заливки мне приходилось делать её копию. Я хотел перейти на мутируемое изображение, но запутался в монадах и не понял, как это сделать. Оно и к лучшему: благодаря иммутабельности мы на следующий день легко напишем обёртку, позволяющую откатывать результаты команд — и солверы получат возможность перебирать варианты действий и останавливаться на лучшем.
Портнов тем временем сделал солвер, заливавший все исходные блоки новых задач их средним цветом. И, конечно же, в условиях контеста не обошлось без шуток и прибауток:
<portnov> отправил решения на 26-й, 28-й, 29-й задачи, которые получились лучше чем “# nothing”
<Minoru> надеюсь, с комментарием «# better than nothing»? :)
<portnov> Minoru: that’s why we call it beta.
<portnov> ’cause it’s betta than nothin
А потом мы застряли. Akon32 знал, какой алгоритм применить к вычислению среднего, но очень долго писал его на Haskell. Портнов пытался ускорить уже существующий алгоритм с помощью библиотеки repa, но безрезультатно. Форневер продолжал заниматься алгоритмом вырезания прямоугольника, и тоже без прогресса. Я же, как уже сказано выше, погряз в трясине монад. Чатик окутало уныние, и мы даже немного поспорили, на каком языке писать в следующий раз.
Чтобы ощутить хоть какой-то прогресс, я плюнул на мутабельные изображения и занялся скриптом, который запускал бы все солверы на всех задачах и записывал лучшие решения в наш репозиторий. Форневер наконец-то заставил свой код компилироваться, словил исключение и теперь ждал, пока проект пересоберётся более старым компилятором — оказалось, что в GHC 9.0.2 сломано профилирование, без которого не работают стектрейсы. А без стектрейсов, вобщем-то, Хаскель дебажится только внимательным чтением кода.
Уже после полуночи в чат подтянулся pink_snow. Я спихнул на него доработку своего скрипта, чтобы тот умел обрабатывать более новые задачи, а сам ещё раз перечитал формулу стоимости решения и принялся рассматривать исходные картинки. Прошлогодний опыт показал, что мне полезно решить хотя бы одну задачку руками, прежде чем писать автоматизированные солверы.
Напомню, стоимость операции обратно пропорциональна размеру самого большого блока, который она использует. Мне стало интересно, как выгоднее всего нарезать полотно на столбцы. Можно резать пополам и потом рекурсивно нарезать половинки, а можно отрезать по одному столбцу за раз. Первый подход очень быстрый, но из-за того, что под конец он работает с очень маленькими блоками шириной в несколько пикселей, его стоимость оказывается просто астрономической. Постепенное нарезание на столбцы хоть и требует экспоненциально больше команд, но зато мы постоянно работаем с самым большим из доступных блоков и, соответственно, минимизируем общую стоимость программы. Контринтуитивно, но с арифметикой не поспоришь!
В итоге получилось что-то вроде биллборда, составляющего изображение из
вертикальных полос. К двум часам ночи Alt.Solver.Billboard
был готов, и даже
улучшил наши решения по паре задач. Довольный первым существенным прогрессом,
я ушёл спать.
За ночь pink_snow написал на Python программу, генерирующую решение первой задачи (на картинке выше), а также ускорил вычисление среднего цвета. Это, как и ожидалось, существенно помогло cолверу, искавшему оптимальную точку разреза, и мы получили несколько улучшенных решений. Портнов, проснувшись, занялся новыми задачами, в которых изначально уже присутствовали какие-то блоки: объединив их обратно в один большой, можно было свести эти задачи к предыдущим и применить существующие солверы.
Позавтракав, я занялся улучшениями «биллборда», которые придумал ещё вчера. Например, очевидно, что идущие подряд столбцы одного цвета можно рисовать все скопом, одним действием. А если «загрубить» цвета, то повторяющихся столбцов станет больше, и программа получится короче. Реализация этих нехитрых оптимизаций помогла существенно улучшить целый ряд решений.
В процессе я придумал ещё более крутое улучшение. Напомню, «биллборд» работает рекурсивно, постоянно отрезая от текущей области левый столбец и уходя в правую. Так как рабочая область постоянно уменьшается, то стоимость каждого следующего шага растёт. Со стоимостью закрашивания ничего поделать нельзя: я вынужден красить как можно более мелкие области, чтобы увеличить степень «похожести». А вот стоимость разрезов вполне можно сделать постоянной, если после каждого разреза склеивать полотно обратно!
Алгоритм теперь выглядел так:
Согласно моим расчётам, это должно было уменьшить стоимость программы в 1,75 раз.
Пока я занимался реализацией этой идеи, Портнов закончил с алгоритмом склеивания исходных блоков и принялся комбинировать разные солверы. Это дало хорошие результаты (какой сюрприз!), и он принялся писать некое общее API для упрощения такого комбинирования.
Тем временем я доделал новый алгоритм «биллборда» и обнаружил, что он не улучшает ни одного из существующих решений. Он не был плохим, он был просто… другим: всё то, что удалось сэкономить благодаря мержам, алгоритм тратил на создание большего количества столбцов. У меня была надежда, что алгоритм «выстрелит» на более новых задачах, поэтому я принялся писать своё собственное склеивание начальных блоков; то, что написал Портнов, мне не подходило, т.к. там не было гарантий полного склеивания.
Тут организаторы снова обновили задачу. Отныне предварительно созданные блоки могли быть заполнены не просто цветом, а какими-то картинками. У нас уже не было сил с этим разбираться, поэтому мы просто забили. Ещё организаторы добавили в турнирную таблицу информацию о лучшем решении каждой из задач. Форневер, отчаявшись написать свой алгоритм вырезания прямоугольника, проанализировал циферки и выяснил, какие из задач мы решили сильно хуже, чем соперники. Результаты явно указывали на более новые задачи, так что у моей работы были все шансы как-то улучшить наше положение. Форневер тем временем взялся писать ручную решалку на C# (потому что этот язык он знает хорошо, а GUI на Haskell мы уже когда-то делали и это была боль).
К десяти вечера я доделал мерж начальных блоков. Алгоритм был простейшим, но я сразу же получил улучшения по ряду задач. Затем я добавил сортировку, чтобы алгоритм мержил пару, включавшую наибольший возможный блок — и снова получил ряд улучшений! Учитывая, что воскресенье было для меня последним днём соревнований (из-за работы), я был очень рад получить такой ощутимый прогресс.
Ближе к ночи Форневер попробовал запускать тривиальный «попиксельный» солвер не на исходной картинке, а на каком-то её приближении: он взял Paint.NET и вырезал из картинки с тетрисом часть фигурок. И это дало решение лучше, чем на исходной задаче! Правда, мы так и не поняли, почему, и Форневеру не удалось развить эту идею.
Запилив напоследок базовую поддержку задач с блоками-картинками (на которые мы изначально забили) и получив несколько улучшенных решений (относительно «пустых»), я довольный ушёл спать.
В понедельник я был занят работой, поэтому уже ничего не писал. Портнов и Форневер попробовали всякие мелкие улучшения к уже существующим солверам, но результатов это не принесло. Так и финишировали.
К моменту заморозки турнирной таблицы мы были 69-е из 93-х команд, решивших все 40 задач, и 150-ти команд, участвовавших в соревновании. В общем, средненько во всех смыслах слова. Update 2022.09.17: в финале мы 71-е из 151-го.
В этом году у нас было очень плохое взаимодействие: все разбрелись по углам и пилили каждый своё. А ещё, перечитывая лог командного чатика, я постоянно натыкался на весьма перспективные идеи, которые во время контеста были проигнорированы. Например, Форневер в какой-то момент предлагал выбрасывать из программ финальные команды и смотреть, не улучшается ли от этого решение. Звучит как дополнительная работа, но если реализовать это непосредственно в интерпретаторе, то оптимизация будет практически бесплатной и автоматически применится ко всем солверам. Похоже, нам следует выделять время для периодического вдумчивого обмена идеями.
Та же мысль звучала и во время ретроспективы: после чтения спеки нам следует не просто написать в чатик впечатления, а собраться и составить список первоочередных задач, вплоть до уровня модулей и функций. Тогда больше шансов, что все будут работать в общем направлении. Звучит как формализм, но, возможно, капельки формализма нам как раз и не хватает.
А ещё в этом году мы поздно принялись за GUI и поэтому не знаем, помог бы он нам или нет.
В целом я доволен. Несмотря на то, что контест готовили в последний момент, он получился достаточно оригинальным и интересным. Так что, дорогие читатели, если уж вы добрались до этого абзаца — вам обязательно надо поучаствовать в ICFPC 2023! До него ещё год, так что можете скоротать время чтением моих прошлых отчётов ;) Если владеете английским, почитайте ещё и отчёт Форневера — у него своя перспектива.
]]>В этом году контест проходил с 9-го по 13-е июля. Я традиционно играл в составе Codingteam, которую также представляли Akon32, ForNeVeR, pink-snow, portnov и sergevp. Последний с нами ещё не выступал, но он любит задачки и весь предыдущий год обсуждал со мной ката в CodeWars. Вообще приятно, что команда обрастает новыми людьми, которые затем превращаются в постоянных участников: больше идей, больше рук для их реализации, больше фана и выше места́ в рейтинге.
Код писали на Scala 2.13. Да, старье, но тройка только-только вышла и вряд ли готова, да и мы к ней не готовы тоже :) Моя шпаргалка для хаскелистов актуальна до сих пор. Репозиторий со всеми наработками можно найти на GitHub.
Дальше я буду рассказывать в основном про то, что делал сам. За обзором работы всей команды смотрите отчёт ForNeVeR-а.
Организаторы вдохновлялись японской передачей Brain Wall: игрок стоит на месте, за спиной у него бассейн, а спереди на него едет стена с отверстием причудливой формы. Чтобы не оказаться в воде, игрок должен как-нибудь извернуться и протиснуться в дыру. Проще показать:
Игрок — это граф на плоскости. Мы можем как угодно переставлять его вершины, но длины рёбер должны оставаться почти неизменными (задан процент максимального отклонения). Ну и, конечно же, кроме человечков и лямбд бывают задачи посложнее:
Таблички «663» и «0», которые подымают судьи — это оценки решения. Они измеряются в «дизлайках», поэтому чем меньше, тем лучше; ноль — вообще идеально. Рассчитывается просто: от каждой вершины отверстия вычисляется квадрат расстояния до ближайшей вершины фигуры; сумма этих квадратов и есть оценка решения. (Внимательный читатель будет вознаграждён). Все подробности условия можно прочесть здесь.
В целом это было очень похоже на задачу 2016-го года про оригами, только там мы разворачивали фигуру в прямоугольный лист, а здесь — в произвольную форму. Сходство поверхностно, читайте дальше :)
Пока Форневер разбирался с API для отправки решений, мы с Портновым генерировали идеи. В целом было понятно, что алгоритм будет итеративным: мы будем двигать вершины фигуры внутрь отверстия, потом исправлять длины рёбер и снова двигать вершины, и так далее аж пока не найдём решение. Для исправления длин нам виделось несколько вариантов: можно как-то искать подходящие положения вершин (координаты целочисленные, так что пространство поиска ограничено), а можно рассчитывать «силы», возникающие в рёбрах, и двигать ими вершины в «правильное» положение.
Я настолько увлёкся этой физической аналогией, что даже перечитал главу Ландсберга про статику и осознал, какие силы возникали бы в рёбрах треугольника, парящего в пространстве, если приложить силу к любой его вершине. Чуть позже Форневер и sergevp независимо реализуют более простой «force solver», который считает рёбра пружинами и учитывает только силу упругости, и мои открытия не пригодятся.
Тем временем с начала контеста прошло уже четыре часа, и я, бросив свои
размышления о физике, взялся переводить наши модели данных и парсер JSON на
длинную арифметику — организаторы как раз подтвердили, что координаты могут быть
сколь угодно большими. Памятуя о задаче про оригами, где координаты были не
просто большими, а дикими, мы с готовностью повелись на провокацию и стали
везде впиливать BigInt
и другие хитрости. Я предлагал просто масштабировать
большие задачи, а алгоритмы писать на Long
, но эта идея не нашла поддержки,
и я забил.
Закончив с арифметикой, я быстренько написал «оценщик» решений, использующий вышеописанную формулу, и занялся первым «решателем»: мой «rotation solver» методом градиентного спуска искал самый удачный поворот фигуры. Никаких серьёзных задач он решить не мог, но я надеялся, что его удастся использовать как базу для более крутых алгоритмов. Тем временем у меня наступила ночь, и я ушёл спать.
В субботу я появился в чате ровно в тот момент, когда обсуждение дошло до A*. Кто не понимает, в чём тут соль — марш читать все мои предыдущие отчёты :) Портнов обратил внимание, что треугольники можно только двигать и поворачивать — их нельзя ни сложить, ни скрутить, потому что от этого ломаются рёбра. Следовательно, если выделить из фигуры некий «остов», то искать его положение будет сильно проще. Вдохновившись этими идеями, я написал алгоритм поиска отдельных треугольников, а затем поправил написанный Портновым алгоритм Брезенхэма: он у нас работал только с целочисленными радиусами, а в задачах встречались величины вроде \(26 \sqrt{2}\).
Тут у меня начало шатать Интернет, а у sergevp и вовсе выключили свет, но мы продолжали бороться: sergevp решал задачи вручную, удерживая нас на 25-м месте, а я занялся поиском «остова». К Z-46 этот код был готов, и я занялся развитием «верификатора», чтобы можно было проверять, находится ли точка внутри отверстия (там уже был похожий код, просто не было метода, который можно было бы дёрнуть снаружи). Заодно написал ещё и генератор случайных точек, лежащих внутри отверстия — задел для будущих стохастических алгоритмов (которые так и не появились).
Тем временем Форневер написал-таки «физический движок» с рёбрами-пружинами и обнаружил, что он почему-то не сходится к стабильному состоянию даже после небольших начальных возмущений. Кроме того, «движку» не хватало сил, которые заставляли бы фигуру разместиться внутри отверстия. Чтобы это исправить, я впилил простенький костыль, тянущий все «наружные» вершины к центру отверстия. Из-за неправильного расчёта этих сил возник прикольный баг: в одной из задач, где фигурой был журавлик оригами, силы заставляли его перевернуться головой вниз и улетать вниз и вправо, на юго-восток, в тёплые края. Починилось расчётом силы относительно текущего положения фигуры, а не исходного.
Настроение команды к этому моменту несколько упало: прошло уже полтора дня, а все наши решения до сих пор делались руками. У нас уже были какие-то общие идеи и базовый код, но не было видения, как из этого собрать полноценный «солвер».
В Z-40, пока я учил наш визуализатор загружать решения из файла, в чат вернулся sergevp и рассказал, что он успел понапридумывать в оффлайне. Среди прочего упомянул и неудачные идеи, например:
автопоиск нулевых решений от вершин дырки по целым координатам — перебор экспоненциален (на сложных задачах нереально), и требует очень хитрых оптимизаций (типа гамильтонов путь в графе), за контест я его точно не напишу, забил.
Тут меня совсем стал рубить сон, и я ушёл спать.
Проснулся с чёткой мыслью: sergevp забраковал идею совершенно зря, потому что есть замечательные генетические алгоритмы, которые живо найдут ему нулевое решение. Это ведь так просто: нужно просто каждой вершине фигуры сопоставить вершину отверстия (да-да), тогда расстояния будут нулевыми по построению, и оценка тоже будет нулевой! Это, конечно, уже комбинаторная задача, а не экспоненциальная, но генетика всё осилит!
Реализация выглядела так: координаты, в которых находится вершина фигуры — это
«ген», а «особь» — это набор «генов», то есть решение задачи. Чтобы
сгенерировать случайную особь, берутся случайные вершины отверстия (с
повторами). При мутациях 10% вершин заменяются на случайные, а при скрещивании
создаётся новая особь, в которой 90% генов взяты из одного предка, а остальные
из другого. Ну, а дальше всё стандартно: оцениваем каждую особь, складываем их
в TreeSet
и оставляем только 10 тысяч лучших. Потом проходимся по этому
«поколению», случайным образом мутируя и скрещивая особей, и начинаем новый
виток отбора.
Первым камнем преткновения стали локальные минимумы: алгоритм собирал все рёбра где-нибудь в углу, игнорируя их длины, и упорно не желал «разворачивать» фигуру и тянуться к вершинам отверстия. В попытке это побороть я добавил «перезапуски»: если текущее наилучшее решение не менялось в течение трёх тысяч итераций, я заменял 100 лучших особей новыми и продолжал эволюцию. Смысл был в том, чтобы дать шанс более слабым особям эволюционировать и найти решение получше. Это работало неплохо, но алгоритм все равно не сходился.
Затем я додумался глянуть на промежуточные решения в визуализаторе и обнаружил, что алгоритм преспокойно создаёт рёбра за пределами отверстия. Чтобы это предотвратить, мне нужно было «наказывать» особей с такими рёбрами. К сожалению, наш «валидатор» не умел сообщать, какое именно ребро оказалось за границей, поэтому я позаимствовал соответствующий код у sergevp. На портирование ушло совсем немного времени, и к Z-22 я наконец-то смог заставить генетику не выходить за границы отверстия, пригрозив ей дикими штрафами — четвёртой степенью длины ребра-нарушителя. Это помогло, но сходимость не улучшилась.
Спустя ещё пару часов я стал подозревать, что почти-идентичные решения заполняют всё «поколение» и мешают эволюции. Для борьбы с этим я добавил дедупликацию: для каждой возможной оценки хранилась только одна особь. Это существенно замедлило работу, но, вроде, немного помогло со сходимостью.
Впрочем, алгоритм всё ещё продолжал собирать точки в каком-то одном углу отверстия, и я ввёл «налог на однообразие»: поделил оценку особи на квадрат уникальных координат, которые она использует. От этого у солвера совсем сорвало крышу, он опять начал выбираться за пределы отверстия, и я окончательно разочаровался в этом подходе.
Наблюдая за промежуточными решениями генетики, я всё больше утверждался в мысли, что поиск можно было бы направлять, если учитывать длину рёбер. Я даже проанализировал имеющиеся задачи и выяснил, что у отверстия максимум 108 вершин, а у фигур — 224 вершины и 350 рёбер. Итого между вершинами отверстия можно сформировать чуть менее шести тысяч рёбер, из которых часть окажется за пределами отверстия и будет отбракована, а из остальных мы отберём те, длины которых соответствуют рёбрам фигуры. (Ага.) Пространство поиска можно сократить ещё сильнее, если учесть, что каждая вершина фигуры имеет рёбра строго определённой длины: например, если из неё выходят рёбра длиной 3 и 5 единиц, то её нельзя расположить в вершине отверстия, из которой выходят только рёбра длиной 1 и 3 единицы.
Я кратко обсудил эту идею с sergevp и, не получив убойных контр-аргументов, принялся за дело. Нужно понимать, что на часах у меня было уже полдесятого вечера, я кодил 11 часов кряду, а в голове вертелась фраза «constraint optimization» и воспоминания о нескольких постах майнтейнера Catch2. Изначально я думал, что поиском будет заниматься A*, но пока я занимался отсеиванием рёбер, идея про A* мутировала в совершенно шальную мысль: преобразовать всю задачу в boolean satisfiability problem! После этого её можно было бы скормить любому из существующих SAT-солверов (которые оптимизировались под эту задачу годами) и быстро получить решение.
Boolean satisfiability problem, или SAT, формулируется просто: есть булевы (двоичные) переменные и несколько выражений с их участием; нужно найти такое значение переменных, что все выражения истинны.
Представьте, что у фигуры \(F\) вершин, а у отверстия — \(H\). Пусть булева переменная \(f_ih_j\) будет истинной, если \(i\)-я вершина фигуры должна быть размещена в \(j\)-й вершине отверстия. Теперь можно сформулировать правила, описывающие «нулевое» решение задачи:
каждая вершина фигуры соответствует ровно одной вершине отверстия, то есть среди переменных \(f_ih_1, f_ih_2, f_ih_3, \ldots, f_ih_H\) истинной должна быть ровно одна. Звучит просто, а вот на языке булевой алгебры выглядит страшновато:
\[\begin{array}{crrcrcrcccrl} & ( & f_ih_1 & \land & \lnot f_ih_2 & \land & \lnot f_ih_3 & \land & \ldots & \land & \lnot f_ih_H & ) \\ \lor & ( & \lnot f_ih_1 & \land & f_ih_2 & \land & \lnot f_ih_3 & \land & \ldots & \land & \lnot f_ih_H & ) \\ \lor & ( & \lnot f_ih_1 & \land & \lnot f_ih_2 & \land & f_ih_3 & \land & \ldots & \land & \lnot f_ih_H & ) \\ \vdots & & \vdots & & \vdots & & \vdots & & \ddots & & \vdots & \\ \lor & ( & \lnot f_ih_1 & \land & \lnot f_ih_2 & \land & \lnot f_ih_3 & \land & \ldots & \land & f_ih_H & ) \end{array}\]
И так для каждой из \(F\) вершин фигуры. Хорошо, что эти штуки будет генерировать компьютер!
вершина фигуры может быть помещена только в ту вершину отверстия, из которой исходят рёбра нужной длины. Например, если вершина \(f_3\) может быть помещена только в вершины \(h_4\), \(h_7\) и \(h_9\) (потому что у других нет всех нужных рёбер), должно выполняться следующее условие:
\[f_3 \land (h_4 \lor h_7 \lor h_9)\]
если между двумя вершинами фигуры существует ребро, то эти вершины нужно размещать в соседних вершинах отверстия. Например, если между вершинами \(f_1\) и \(f_3\) есть ребро, и при этом вершина \(f_1\) может быть размещена в вершинах \(h_2\) и \(h_4\), а \(f_3\) — в \(h_8\) и \(h_9\), и к тому же подходящие рёбра образуются только парами \((h_2, h_8)\) и \((h_4, h_9)\), то при размещении \(f_1\) в \(h_2\) нужно обязательно разместить \(f_3\) в \(h_8\), а при размещении \(f_1\) в \(h_4\) — обязательно разместить \(f_3\) в \(h_9\):
\[(f_1h_2 \land f_3h_8) \lor (f_1h_4 \land f_3h_9)\]
если между двумя вершинами фигуры существует ребро, то эти вершины не могут быть помещены в одну и ту же вершину отверстия. Это совершенно очевидное правило пришло мне в голову гораздо позже, когда я начал смотреть на результаты первых трёх и увидел, что солвер ради решения готов сломать всю геометрию. Тут пришлось даже вывести формулку, похожую на импликацию, но как бы наоборот: \(\lnot a \lor \lnot b\) означает, что \(a\) и \(b\) не могут быть истинными одновременно. Теперь, если между \(f_1\) и \(f_4\) есть ребро, то для каждой из \(H\) вершин отверстия нужно сгенерировать условие:
\[\lnot f_1h_j \lor \lnot f_4h_j\]
Выглядит несложно, правда? На часах Z-16, мы занимаем 26-е место рейтинга (из 158-и команд), меня клонит в сон — превосходные условия для кодинга. Погнали!
Между мной и идеальными решениями всех задач стояла всего одна преграда: я никогда раньше не пользовался SAT-солверами. К счастью, в тех же постах майнтейнера Catch2 был упомянут Minisat, чья документация быстро прояснила ситуацию:
КНФ — это такая запись булевого выражения, где отрицания стоят только рядом с переменными, переменные объединяются только с помощью логического ИЛИ, а между объединениями стоят только логические И. Например, \((f_1h_1 \lor \lnot f_2h_9) \land f_3h_5\). Чтобы из вышеприведённых формул получить КНФ, нужно в цикле применять два закона и одну теорему, найти которые можно в Википедии. Освежив память, я взялся писать «упрощалку» выражений.
Сперва у меня произошёл фальстарт: я был настолько занят размышлениями о КНФ, что заточил под него AST булевых выражений. Конечно, это замечательно, что результат получается по построению, но на входе у меня всё же не КНФ. Переделав как надо, к Z-13 я получил (пока что не реализованную) возможность закодировать вышеприведённые формулы и выдать их в требуемой форме.
Формат DIMACS оказался простым текстом, в котором сперва нужно указать
количество переменных и «клоз» (clause), а потом перечислить клозы одну за
другой. Клозы — это те части КНФ, которые объединяются через И. На это ушёл ещё
часок, основная часть которого была потрачена на осознание того, что
StringBuffer
для задачи не подходит и вместо него нужен Array[String]
.
Где-то к Z-9, то есть середине ночи, я наконец-то закодировал первое правило, преобразовал его в КНФ, вывел DIMACS, руками скопировал его в Minisat и получил решение самой простой задачи: повернув треугольник на 90°, уместить его в такое же треугольное отверстие. На более крупных задачах моя «упрощалка» выражений просто загибалось. Прочитав Википедию чуть внимательнее, я узнал, что некоторые выражения при переходе к КНФ растут экспоненциально. Чтобы это побороть, я нагуглил алгоритм получше, но тут же отложил — сперва нужно было дописать остальные куски кода.
А оставалось не так уж много: ещё три правила и автоматический запуск Minisat с разбором результата. Впрочем, правила требовали вычисления длин рёбер и отсеивания вершин, так что вся эта работа была завершена только к Z-6, то есть утру понедельника.
Тем временем командный чат ожил, и я даже попытался уговорить Форневера сделать мне быстрый преобразователь в КНФ, но он глянул на остальные задачи и предпочёл заняться чем-нибудь более перспективным. Всё правильно сделал :)
Спустя ещё часок мой солвер научился решать две простейших задачи, и я взялся за очередной «баг»: на всех остальных задачах солвер говорил, что какие-то из ребёр фигуры невозможно построить между вершинами отверстия.
Внимательный читатель, наверное, уже охрип орать на монитор; потерпи, осталось всего три десятка слов. В Z-3:11 я наконец догадался открыть в визуализаторе одно из «нулевых» решений, которые ребята сделали руками, и обнаружил, что некоторые вершины фигуры не совпадают с вершинами отверстия! Дальше просто цитирую чат:
<ForNeVeR>
Не все точки решения должны содержаться в узлах отверстия.
<Minoru>
для нуля дизлайков? Но почему?
<ForNeVeR>
Там обратное требование
В каждой точке дыры нужно иметь одну из точек фигуры
У фигуры больше точек, чем у дыры, поэтому остальные точки могут делать что им захочется (в пределах ограничений).
Рейтинг смотрит на ближайшую точку фигуры к каждой точке дыры.
<Minoru>
*схватился за голову*
то есть
я два дня занимаюсь полной ерундой
и вы это терпите?
<ForNeVeR>
Мы не поняли, чем ты занимаешься :(
А вернее, я не объяснил толком, чем я занимаюсь, поэтому меня не успели остановить и разубедить. Эх!
Забавно, что эта ошибка была допущена именно мной. Ведь это же я писал «оценщик», я должен был лучше всех знать, как считается оценка! И тем не менее: код я написал правильно, а принцип запомнил неправильно; построил на нём две заведомо нерабочие идеи и успешно спустил два дня в трубу.
Выпив чаю и собравшись с мыслями, последние три часа контеста я решал задачи вручную.
Личные:
думать наперёд полезно, но у меня получается не очень хорошо. Вместо чтения Ландсберга нужно было закодить «очевидную» идею с рёбрами-пружинами и посмотреть, как она работает;
первым делом надо писать визуализатор и «щупать» задачи руками. Писать «солвер», не решив ни единой задачи вручную — это хороший способ получить максимум фана и минимум результата;
ну и ещё пара, которые я не буду писать в Интернете, но над которыми уже думаю.
А про команду написать нечего. Я в этом году слишком мало в команде участвовал, чтоб о ней выводы делать :)
В lightning division (первые 24 часа соревнования) мы 26-е из 137-и, в финале — 30-е из 160-и. Это лучший наш результат за всё время и я, вообще-то, удивлён. Портнов на протяжении всего контеста рассказывал про умных дядь из сильных команд, которые наверняка уже три дня молотят задачи с помощью чудо-алгоритмов на супер-мейнфреймах, а оказалось, что команда из 6-1 человек, решающая задачи почти что вручную, способна я этими «умными дядями» тягаться. Чудеса!
Если вы сюда дочитали, то, во-первых — спасибо! Во-вторых, ребята из команды TBD (вы могли видеть их вверху рейтинга на прошлых ICFPC) хотят организовать в первом квартале следующего года тренировку по ICFPC и дать задачку с какого-то из прошлых контестов. Приглашают всех в свой Discord. Увидимся ^_^
]]>Around the same time, I began exploring the world of Linux. You already see where this is going, right? Of course, I joined a Linux-related channel on Freenode. Actually, it was more like a gathering place for a ragtag crew, but hey, it had Linux in the topic and my Linux-related questions got answered, so it’s a Linux channel in my book.
I was a bit of a menace, pestering everyone else to point out my errors, but one of the guys there, pnbeast, did me one better: he engaged me in long, wandering conversations about anything and everything. We hit it off: I was curious, and he was an interesting person and a great interlocutor. I’m not sure what he got out of those chats, other than an occasional chuckle, but I got the jackpot: a habit of actually using English. pnbeast bridged the gap between the classroom and the real world for me, and once I got going, I just never stopped.
Two years later, I finished school with a B in English. Not bad for someone who was struggling to get passing marks until then, eh? Today, easily half of my communication happens in English.
There was also this other guy, Raging_Hog. (I didn’t appreciate the nickname until much, much later.) I don’t think we chatted all that much, but he too had a profound impact on me. I was writing scripts for my IRC client and sharing them via pastebins. Probably annoyed by my spam, Raging_Hog told me about Git and GitHub, so I could post a single link and quietly update it later.
Anyone who’s using Newsboat today is slightly indebted to Raging_Hog.
Perhaps I would’ve gotten serious about English some other way. Maybe I’d hear about GitHub a few years later, at the university. It’s possible that without Freenode, I’d end up finding some friends locally. Who knows. The facts are: Freenode did exist, and all those people were on the network, and I met them, and they affected me, and I went on to accomplish things.
Thanks, pnbeast. Thanks, Raging_Hog. Thanks, Sulis and Punko and everybody else. And thank you, Freenode.
(There’s an ongoing drama around Freenode; I don’t have a good summary to link to. The upshot is, I’m no longer on there, so if you spot Minoru on Freenode, that’s an impostor. Check the About page for where else you can find me.)
]]>setxkbmap -print
only shows the US layoutThis command is supposed to dump your entire keymap, including layouts and options, but for me, it only displayed the basic US layout:
$ setxkbmap -print
xkb_keymap {
xkb_keycodes { include "evdev+aliases(qwerty)" };
xkb_types { include "complete" };
xkb_compat { include "complete" };
xkb_symbols { include "pc+us+inet(evdev)" };
xkb_geometry { include "pc(pc105)" };
};
I expected to see my “ru” layout mentioned in xkb_symbols
, as well as the
option to toggle layouts with Alt+Space. To fix this, I had to explicitly pass
in all my layouts and options, like so:
$ setxkbmap -layout us,ru -option grp:alt_space_toggle -print
xkb_keymap {
xkb_keycodes { include "evdev+aliases(qwerty)" };
xkb_types { include "complete" };
xkb_compat { include "complete" };
xkb_symbols { include "pc+us+ru:2+inet(evdev)+group(alt_space_toggle)" };
xkb_geometry { include "pc(pc105)" };
};
Notice how xkb_symbols
now correctly lists all my settings.
xkbcomp <file> $DISPLAY
doesn’t affect anythingIf you put the result of setxkbmap -print
into a file, edit it, and run
xkbcomp <file> $DISPLAY
, the edits should be applied to your keyboard.
However, under Wayland, xkbcomp
seemingly doesn’t do anything (and prints some
errors at that!)
Actually, it does do something: it changes the settings of XWayland, an X11
server that Wayland runs for backwards compatibility with Xorg. You can verify
this by running xterm
: as an X11 app, it’ll use XWayland, and thus the
settings you introduced with xkbcomp
.
How to apply a keymap to both Wayland and XWayland though? I found two ways.
This only works for the xkb_symbols
section; if you want to edit anything
else, see further down.
Take your edited xkb_symbols
and put it in a file under
~/.config/xkb/symbols/ (you might have to create those directories first).
Give the file a plain name with no extension. If in doubt, check
xkeyboard-config(7) manpage to ensure there’s no
clashes with existing layouts. Remember, the file should only contain the
xkb_symbols
section:
xkb_symbols {
include "pc+us+ru(ruu):2+inet(evdev)+group(alt_space_toggle)"
};
Now specify that file as your layout. In Sway WM, that means tweaking your ~/.sway/config as follows (“runomi” is my file’s name):
input type:keyboard {
xkb_layout runomi
}
As you can see, there is no need to add xkb_options
to the config — the
options are taken care of by the layout file. I guess you could also use this
layout in Xorg now, but I didn’t test that.
If you’d like to edit not just xkb_symbols
, but other sections too, you got to
replace the whole keymap. I don’t know how to do it in an arbitrary environment,
but here’s a recipe for Sway WM.
First, dump your current keymap into a file using setxkbmap
as described
above. Let’s call it ~/.Xkeymap.
Then, edit your ~/.sway/config like so:
input type:keyboard {
xkb_file .Xkeymap
}
That’s it: your entire keymap is now defined by that single file, and you can tweak it to your heart’s content. Enjoy!
]]>Or so I thought. As I doubled down on Anki reviews and committed all the words to memory, there was this nagging feeling… Until I realized a few days ago that there are certain similarities, certain rules by which irregular verbs are formed. They can be grouped into smaller, neater tables where everything is simple!
I wanted to write a blog post about that grouping, but it turns out someone already did it. So I’m sharing this in hope that more English learners will discover this technique, and it will cut down on the amount of rote they have to do (with Anki, of course!)
]]>I’m fully aware that there are a thousand projects like this one, and I realize that mine is the worst of them all. It doesn’t have a GUI, its output is specific to my needs, and it crashes on broken JPEGs. In terms of usefulness to the world, it was a waste of my time.
Yet, it was the best thing I did in the last few months. These 200 lines of code helped me cross out a handful of items off my to-try list. I learned about perceptual hashes and BK-trees. I finally got my hands dirty with some famous Rust crates: walkdir, anyhow, and rayon. And I had fun the entire time.
That’s how I learned to program, actually. I built a lot of junk: a password generator, an IRC bot, some scripts for my chat client, a little database to manage my DVDs… These days, it’s different: I work on a handful of big-ish projects, and usually go for depth, not breadth. And so my to-try list keeps growing, making me feel like I’m missing out.
Building inconsequential stuff is the fastest way to shrink that list.
]]>If you’re a FLOSS maintainer hosting your projects on GitHub, Cirrus CI can offer you three killer features.
Don’t snigger! Even if you don’t care about FreeBSD as a target platform, you can still take advantage of its affinity with macOS. Both operating systems are descendants of BSD, and some build failures affect the whole family. If you don’t have a Mac lying around, you can’t legally run OS X in a virtual machine, and so FreeBSD becomes a very compelling option. Not to mention that its source is open, and it has up-to-date documentation.
All your jobs can simultaneously use up to 16 CPUs for Linux, 12 for macOS, 8 for FreeBSD, and 8 for Windows. You are free to slice them however you want (except on macOS). For example, you can give a linter job a single core, while the compilation jobs get four each. Furthermore, the limits are per-user, so you won’t get starved of CI time no matter how many pull requests you get!
The only meaningful competition here is GitHub Actions: they provide an unlimited number of dual-core VMs. But if you have just a handful of heavy-weight jobs, you’re still better off with Cirrus.
You can probably get a competitive proposition from CircleCI and Travis, but they bill by a minute, so the dynamics will change every time you change your pipeline. Either way, you probably don’t want to wake up to an email notification saying that you’ve run out of your compute credits for the month.
You pay for concurrency by accepting some flakiness. Cirrus uses AWS Spot instances to make such high limits viable, and Amazon can take those machines back at any time. Cirrus papers over this by automatically restarting affected jobs, but GitHub would still display them as “failed” until the restarted ones succeed. From my experience, about once a week some job won’t be restarted, or won’t start at all.
You specify a path to a Dockerfile; Cirrus builds and caches the image, then creates a container and runs all your tasks inside of it.
Contrast this with what other CI providers give you. At best, you are allowed to specify a Docker image to use. If no image fits your needs perfectly, you’ll have to build, publish, and maintain your own. At worst, your CI provider has a VM image with some popular stuff pre-installed, and you have to waste CI time installing the rest—every time your job runs.
This feature can break reproducibility. You can’t download a Docker image from Cirrus cache; you have to build one locally. As a result, your container might be slightly different from the one in CI, and you won’t reproduce the failure. This hasn’t bitten me yet, but I think it’s just a matter of time.
With Travis changing their billing just a few months ago, it’s an obvious question to ask: how long will the Cirrus-FLOSS paradise last? @cirrus_labs@twitter.com says they’re an “NYC-based startup”, which to me indicates that their future is less clear than that of GitHub (owned by Microsoft) or Travis (owned by Idera). Maybe this post will help Cirrus get a few more paying customers, and thus delay the exit a bit :)
If/when the time comes, I don’t think that migrating off Cirrus will be any more complicated than migrating off any other CI provider. The dockerfile feature means you’ll have your build environments in Docker already, which is widely supported (if not as conveniently as in Cirrus). The pipeline config you won’t keep anyway, as no two CI providers use the same format. If Cirrus limits the resources, you could keep just the FreeBSD jobs on there, as other platforms are well-represented with other providers.
Other than that, my biggest gripe with Cirrus CI is lack of support for any forges other than GitHub. When I migrate to a different one, it’d be sad to leave all this wealth of features behind. But until then, I think Cirrus is going to serve well.
]]>