Миниотчёт команды nbu
Команда nbu в этом году выступала в составе искренне вашего. Планировалось более многочисленное выступление, но все, кроме меня, либо сочли задачу невыносимо скучной (can't blame them), либо не потянули.
Решение написано на Си (heavy lifting, 809 lines, 651 loc) и ruby (webapi glue, 333 lines, 253 loc). Репу можно посмотреть тут.
Задачу выдали в 2 ночи по местному времени. До 4-х написал десять строк скрипта для дёргания webapi, и решил руками 20 проблем (самых коротких). Подумал, что завтра брошу это дело, и лёг спать.
С утра сформулировал, как енумерейтить все валидные синтаксические деревья, закодил это дело (gen-all.c, bv_gen.c). Потом быстренько реализовал eval для этого их языка (bv_eval.c). Потом из всего этого соорудил солвер, который в интерактивном режиме читает со stdin пары аргумент-значение, а на выход в ответ печатает программы, им удовлетворяющие (gen-eval.c). Потом к этому написал обвязку на ruby, которая ходит к webapi -- train.rb, который получает с сервера и решает одну тренировочную проблему, и run.rb, который в цикле бежит по всем myproblems (выбирая те, что выглядят попроще) и их решает. Таким образом, к дедлайну lightning-а я сделал 419 очков. Подумал, что завтра брошу это дело, и лёг спать.
С утра внезапно обнаружил, что сервер считает валидными решения с длиной, отличающейся от спецификации, и не использующие всех операторов из спецификации. Если бы я знал это раньше, наверное, был бы шанс выиграть lightning. Пооптимизировал всякое в решателе. К вечеру дали спеки на бонусные проблемы, вытащил примеров, почитал. Подумал, что завтра брошу это дело, в связи с этим запустил солвер решать все небонусные проблемы независимо от сложности, и лёг спать.
Первую половину дня даже, кажется, думал, что бросил. Потом заметил постепенно такой факт. Бонусные задачи имеют специальную форму -- f(x) = (lambda (x) (if0 (and e1 1) e2 e3)). Подбирать надо только e1, e2 и e3, для бонусных задач длина e1, e2, e3 примерно одинаковая и составляет 5-7. Легко видеть, что, для каждого x, f(x) либо равно e2, либо e3, и этот выбор определяется младшим битом e1. То есть можно сгенерить все e длиной 5-7, это копейки, и потом среди них (1) искать пары (e2, e3), такие, что для каждого из примеров хотя бы одна выдаёт правильное значение, и (2) искать к такой паре e1, которая младшим битом результата выбирает из (e2, e3) правильную для каждого примера.
До этого места в контесте вообще не было ни одного нетривиального момента; тут тоже не бог весть что, но хоть какой-то фокус. Реализовал это дело (gen-bonus.c и train-bonus.rb / run-bonus.rb), решил почти все 200 коротких бонусных проблем за пару, кажется, часов (запорол три или четыре из-за unrelated bugs). Попробовал натравить этот же код на длинные бонусные, но нет, слабО ему. Попробовал увеличить длину перебора -- захлёбывается по памяти и по CPU. Подумал, что вот тут-то я и брошу это дело, и пошёл гулять.
В пути заметил, что если генерацию синтаксических деревьев сделать вокруг immutable data sctructures with shared tails, то потребление памяти упадёт на порядок, если не на два. Кроме того, заметил, что для поиска пар (e2, e3) можно использовать что-то вроде хеширования вместо полного перебора, и будет на порядок или два быстрее; то же самое относится к поиску e1 для пары. Вернулся, реализовал это дело (bv_shared.c, gen-shared.c). Выяснилось, что да, это гораздо быстрее и больше длины перебора влезает, хотя для уверенного решения длинных бонусов и недостаточно. Но какой-то процент решает (четверть?). В общем, запустил солвер, и к моменту окончания контеста имел 1458 очков. Подумал, что вот теперь-то я точно с этим закончил, и лёг спать.
С утра обнаружил себя пишущим этот отчёт. Ну, вот теперь-то я уж точно с этим закончу.