?

Log in

No account? Create an account
 

ICFP 2015 ((ктулху фтагн)) - swizard

About ICFP 2015 ((ктулху фтагн))

Previous Entry ICFP 2015 ((ктулху фтагн)) 11 авг, 2015 @ 03:56 Next Entry
Ну что, успешно упоролись свежим icfpc в этом году, спасибо всей команде за участие, было весело!
Репо солюшна вот здесь: https://bitbucket.org/skobochka/icfpc-2015/overview

По результатам всё традиционно: тонны кода, дичайший недосып, часы дебага наитупейших ошибок, сорванные в последние минуты дедлайны, страшнейшие факапы за мгновение до окончания раундов, и невероятные озарения спустя пятнадцать минут после. Собственно всё то, за что мы все этот конкурс так ценим :)

Как обычно, пару дней до соревнования все безуспешно пытались угадать к чему надо готовиться, но это каждый раз пропащее дело. В этот раз, согласно всем имеющимся в наличии намёкам, я предположил, что будет что-то из серии: "учёные, пытаясь предотвратить гибель пчёл в стране, что-то набедокурили со своими программами для квантового суперкомпьютера и пробудили древнее зло".

В итоге, историю я фактически угадал, но вспоминать криптографию и программировать квантовые компьютеры было не надо.

Собственно, задачу копипастить мне лень, надо читать введение от оргов (оно стоит того) и спеку (всё кратко и понятно).

А развёрнутая ретроспектива событий получилась какая-то такая (восстановлено по логам конфы):

Пятница.


  • За пять минут до старта контеста я ушёл к стоматологу, и задание пытался читать краем глаза уже из-под бор-машины :)

  • Вернулся через час, все участники пока осознавали правила. Но sectoid уже освоил самбишн решений.

  • Ещё через полчаса я решил развести бюрократию в виде плана действий в корне проекта. Чтоб типа всё как у взрослых: разные подзадачи, там, каждый выбирает себе что-то и закрепляет за собой. Изначальная идея была в том, что в команде уже 5 человек, поэтому нужна какая-то минимальная координация.

  • Но через некоторое время актуальность предыдущего пункта резко упала, потому что grepz снялся с конкурса по уважительным причинам, и нас осталось четверо.

  • Далее наступил какой-то ад: уже через полтора часа после начала контеста на доске почёта какие-то команды стали зарабатывать по 600000 очков и выше. Меня в этот момент начала мучать лёгкая паника.

  • turtle отправился делать генератор случайных чисел.

  • sectoid и jtootf оказались знатоками Лавкрафта, и моментально нашли фразу власти из 51 символа: Ph'nglui mglw'nafh Cthulhu R'lyeh wgah'nagl fhtagn! Лол, как выяснилось в последний день, вместо восклицательного знака нужно было ставить точку :)

  • 17:30 — мы с turtle всё ещё мучаем ГСЧ.

  • Доску почёта продолжает нещадно колбасить -- орги, как обычно, правят баги "по-живому". Кому-то снимают очки, у кого-то, наоборот, они рандомно зарабатываются сотнями тысяч.

  • 18:15 — sectoid принёс нам первые очки вручную сфабрикованным решением.

  • 18:45 — у нас всё ещё нет никакого кода, мы лениво прикидываем, кто чем бы хотел заняться.

  • 19:10 — всё ещё никакого кода, но jtootf нашёл какой-то симулятор гексо-тетриса на тикле, и решил на его основе сделать визуализатор.

  • 19:30 — появился первый код: sectoid написал сабмитилку, а я сделал базовый скелет проекта, структуры данных и загружалку входных данных.

  • План на лайтнинг я на тот момент видел так: надо строго сделать всю сопутствующую мелочёвку (карту, фигуры, координаты, движение / вращение, проверка валидности всех положений, спавн новых фигур), написать какой-нибудь колхозный брутфорс для нахождения места, куда надо уложить появляющуюся на поле фигуру, и реализовать базовый A* для построения скрипта команд с какой-нибудь простенькой эвристикой. Ну и какой-никакой транслятор команд.

  • Далее задачи распределилсь так: sectoid отправился реализовать движение и вращение фигур, а я всё остальное :) turtle допиливал ГСЧ, а jtootf взялся сделать визуализацию.

  • 20:10 — орги, наконец-то, справились со своей доской подсчёта, и она стала выглядеть по-человечьи, без многосоттысячных результатов у каких-то рандомных бомжей.

  • Решаем с sectoid'ом в трансляторе команд реализовать микрооптимизацию: если вдруг каким-то магическим образом собралась последовательность, соответствующая заклинанию, то заменять её на заклинание (мощная идея, правда?).

  • 21:00 — орги пригрозили, что любые команды в скрипте, которые воспоследуют после того, как игра будет закончена (на карте не останется валидных мувов), то решение аннулируется с нулём очков. Так вот, куда пропали все лидеры из рейтинга ;)

  • turtle отправился писать Makefile для проекта, а я к этому моменту изобразил какой-то нищебродский A*. Проблема была в том, что пока не было механики вращения и движения фигурок, поэтому его не на чем было отлаживать. Поэтому я пошёл писать какое-то крайне позорное, но быстрое решение для поиска места, куда следует класть порождённую фигуру. "Стратегия" такая: запихнуть фигуру максимально низко в стакан, прижать максимально сильно к левому краю, повернув таким образом, чтобы справа осталось максимум места. Лол, конечно, но нужно было иметь хоть какую-то реализацию, нежели не иметь никакой.

  • 21:00 — jtootf тем временем спрограммировал на тикле какой-то рендерер гексагонального поля, и поехал домой.

  • То же самое порывался сделать sectoid, но потом передумал, решив сначала добить фигурки. Хех, как он ошибался.

  • Выясняется, что координатная сетка на поле не для щенков. Чётные ряды сдвинуты в право относительно нечётных, поэтому оперировать координатами в терминах (row, column) невероятно мучительно. Сами фигуры задаются при этом относительно своей локальной системы координат.

  • Я сходу порождаю очередную бомжацкую идею: давайте перейдём от описания фигуры в терминах пивот + списка координат её ячеек к такому виду: сдвигаем пивот в (0,0), а все ячейки кодируем последовательностями команд движения, которые надо выполнить, чтобы попасть в них. К счастью, меня не поддержали.

  • 23:00 — у нас всё ещё пока нихрена нет. Sectoid таки поехал домой.

  • Судя по лидерборду, народ где-то нашёл уже готовые тетрисовские солверы и адаптировал их под задачу. Опять приступ паники :)

  • 00:00 — sectoid приехал домой, и мы дальше взмыленно обсуждаем, как правильно быть с координатами.

  • 00:30 — всё ещё обсуждаем.

  • 00:45 — всё ещё обсуждаем.

  • 00:48 — turtle внезапно обнаруживает, а я внезапно читаю материал по этой ссылке, на которую sectoid уже несколько раз ссылался. Оказывается же можно использовать кубические координаты. Мало того, sectoid их уже использовал для поворота, лол.

  • Короче, переходим на кубические координаты. Жизнь снова заиграла красками. А для доступа к полю преобразовываем их обратно.

  • Бла-бла-бла.

  • 01:40 — готовы движения и повороты фигур! Я бросаюсь доводить A* и выбор цели для фигуры, turtle программирует сгорание рядов при заполнении, sectoid пошёл делать транслятор скрипта движений.

  • 03:00 — у меня заработал поиск пути, который стало возможно транслировать. Приступил потихоньку к поиску позиции для фигуры.

  • 03:20 — sectoid берёт таск про спавн фигур (согласно заданию, их надо центрировать), turtle делает бинарь с поддержкой cmd args. У меня в этот момент очередная тупая проблема с тем, как сравнивать две фигуры на доске на эквивалентность (сортировать и сравнивать список ячеек долго, хочется быстро).

  • 03:49 — jtootf напрограммировал базовый визуализатор, но пока непонятно как кормить его данными.

  • 04:23 — я спрограммировал брутфорсный выбор позиции (на отъебись, конечно, но как-то он заработал).

  • 04:30 — у sectoid тем временем затык со спавном: фигура никак не хочет правильно центрироваться.

  • Чем позже становится, тем всё происходящее происходит всё медленнее и медленнее :) На какие-то элементарные вещи тратится непонятная куча времени.

  • 05:00 — первый код в game-loop.

  • 05:27 — на правах местного оракула, произношу пророчество:

    • swizard: подозреваю, что щас будет как-то так:

    • swizard: мы сделаем решение, засабмитим, и получим 0 очков

    • swizard: и далее надо долго дебажить что не так


  • 05:35 — делаю первый пуш кода game-loop.

  • Внезапно обнаружил, что не хватает сжигания рядов. Вроде turtle делал.

  • 05:45 — сжигание рядов есть, но не работает. Быстренько пишу консольный визуализатор, чтобы хотя б видеть что происходит.

  • 06:00 — сжигание рядов всё ещё не работает.

  • Тем временем, jtootf находит на картах подсказки-заклинания: R'lyeh и Yuggoth.

  • 06:12 — сжигание рядов всё ещё не работает. Да что ж такое-то.

  • 06:24 — пока turtle ремонтирует сжигалку, я не выдержал и написал параллельную версию, чтобы общий процесс разблокировался, и можно было что-то делать дальше.

  • 06:24 — оказывается, sectoid тоже психанул и написал свою версию сжигателя рядов :) Итого у нас три имплементации одного и того же.

  • 06:37 — ура, есть наконец решатель! Натравливаем его на все доступные таски.

  • 06:48 — разумеется, баги. Эксепшны, выходы за границы массива, и прочая срань. Ремонтировать баги в семь утра тоже тот ещё кайф :)

  • 06:59 — победили, есть 800 жалких очков на первой карте! На остальных, правда, нуль, ну да и чёрт с ним. Зато можно с чистой совестью идти спать.

  • 07:10 -- делаю крестьянскую визуализацию на базе репла и (break) чтобы воочию понаблюдать перед сном за падающими фигурками. Наблюдаю, и иду спать.

Суббота


  • 11:45 — подъём =) Пробуем взять лайтнинг.

  • 11:55 — начинаем сеанс багфиксинга. Надо понять за что нам везде ставят нуль баллов.

  • 12:00 — я начинаю лихорадочно делать покадровый вывод игры, чтобы его можно было скормить визуализатору имени jtootf.

  • 12:26 — запушил возможность записи и вывода фильма в процессе игры. Прошу sectoid'а конвертнуть вывод в какой-нибудь json, чтобы jtootf мог его подхватить. Сам сел фиксить производительность солвера.

  • 12:38 — ускорил решение в три раза, сел дебажить решение глазами через свой крестьянский визуализатор, который брейками :) Не вижу никакого криминала, игра идёт б/м корректно.

  • 12:53 — sectoid тем временем никак не может совладать с cl-json, чтобы получить корректный выхлоп. В итоге отказывается от таска =) Я забираю обратно.

  • 13:12 — что-то тоже обламываюсь сходу с cl-json, плюс ещё какая-то мелкая срань навалилась. А ведь основная проблема-то -- починить 0 очков на карте.

  • 13:32 — побеждаю cl-json и часть мелкой срани. Всё ещё непонятно, почему 0 очков.

  • 13:45 — выпиливаем из зависимостей lift =) Который год уже пытаемся писать какие-то юнит-тесты, и каждый раз облом. Не до них, код слишком быстро меняется и вообще устаревает.

  • 13:54 — втыкаю в визуализатор, в упор не понимаю, что системе не нравится в нашей игре. На вид всё замечательно.

  • 14:03 — пошагово сравниваем наше решение с видео с игрой, которое выложили орги. Порядок выпадающих фигур правильный, фиксирующие ходы (freezing moves) в порядке. Всё ещё непонятно, где засада.

  • 14:26 — turtle изучает игру дальше, я занимаюсь какой-то ерундой. Что-то ускоряю, где-то что-то переделываю.

  • 14:45 — отчаиваемся, сабмитим к лайтнингу решение, которое у нас уже есть. Которое с нулём очков.

  • 14:53 — выясняется, что на 6 задаче у нас аж три с половиной тыщи очков. Значит, на каких-то конфигурациях оно всё же работает :)

  • jtootf: "ну да, мы всё-таки на три места выше команды DNIWE ;)"

  • 14:58:27 — turtle находит этот долбанный баг! Косяк со спавном фигуры -- она появляется не в том месте, где это оговорено правилами. У нас целых полторы минуты на его исправление =)

  • 15:00 — лайтнинг успешно просран.

  • 15:05 — новый план: отремонтировать баг, начать стабильно получать очки, и идти досыпать.

  • 15:30 — sectoid ремонтирует свой код, а я, по-традиции, параллельно пишу свою версию его же.

  • 15:33 — sectoid починил код, я написал свою версию. Сравниваем -- ни тот ни тот не работает как следует =)

  • 15:44 — sectoid повторно починил свой код, а я, в свою очередь, починил свой. На первый вид оба работают, но оба не всегда.

  • 15:45 — turtle пошёл в баню.

  • 16:08 — я вроде отладил свой вариант спавна, сходу ошибок больше не нашёл. Осваиваю сабмит, чтобы сделать проверку.

  • 16:54 — наконец-то не ноль в лидерборде! Sectoid тем временем добил свою версию, и порывается тоже засабмитить, но я предлагаю сначала прогнать всё на всех картах и тупо сравнить ответы двух наших спавнилок.

  • 17:01 — проверка обломалась :)

  • 17:25 — разобрались, косяк на моей стороне =) В честной борьбе побеждает sectoid, его решение уходит в game-loop.

  • Всё, сабмиты пошли, расходимся по своим делам (моё дело -- вздремнуть пару часов).

  • 18:00 - 20:30 — перерыв на сон и ужин.

  • Тем временем, у нас уже три заклинания, помимо того, что дали в задании: Ia! Ia!, R'lyeh и Yuggoth.

  • 21:00 — начинаю вяло читать всякие ссылки про тетрис и искуственный интелект в нём.

  • Параллельно меня опять "осеняет" (прямо сезон откровений), что мы, в отличие от классического тетриса, знаем всю игру наперёд — какие и когда будут выпадать фигуры.

  • jtootf тем временем регулярно накидывает разные ссылки на разные материалы по теме.

  • sectoid неспеша пытается набрутфорсить больше заклинаний.

  • И только к 21:45 я начинаю заниматься чем-то полезным: перетряхивать свой A*, чтобы он научился пользоваться заклинаниями для переходов по графу.

  • jtootf с sectoid активно вспоминают лавкрафта в поисках новых заклинаний, а я отвлёкся на какую-то ерунду в плане фикса производительности.

  • Примерно в 22:30 часть народа разошлось спать, часть куда-то подевалось, я остался один. Разговаривал сам с собой в конфе =)

  • 01:39 — я спрограммировал поддержку заклинаний в A*. Попробовал засабмитить, но из-за какого-то бага на борде мне показало 0 слов силы, хотя очки засчитали.

  • В конфе появился jtootf, вовремя, а то я уже устал сам с собой разговаривать.

  • 01:45 — Тем временем мой солюшн стал потихоньку набирать очки. Команда в общем зачёте поднялась на 38-е место.

  • 01:56 — 33 место.

  • 03:00 — 24 место в турнирке!

  • 05:00 — 8-е место на нулевой карте, 19 место в общем зачёте.

  • 05:32 — 13-е место в общем зачёте.

  • 05:40 — я отваливаюсь спать на рекорде: 11-е место в общей турнирке.

Воскресенье


  • 13:20 — врываюсь в игру.

  • Потихоньку собираюсь с силами начать нормальный солвер. Параллельно прощупываю почву, не хочет ли кто-нибудь спрограммировать его вместо меня =)

  • 13:30 — sectoid там понаэкспериментировал с разными кандидатами в заклинания, в итоге одно добавилось, одно забраковалось (R'lyeh). Какое-то время я разъясняю ситуацию с багом на лидерборде, в итоге ръльех реабилитирован :)

  • turtle тем временем в процессе делает распараллеливание обсчёта разных seed-ов в game-loop, чтобы они играли независимо на разных ядрах.

  • В процессе у меня ломается сборка, и я начинаю активно ныть в конфу о необходимости ветвиться. Sectoid активно поддерживает, turtle активно сопротивляется :)

  • 14:00 — на борде нам, наконец, зачли все 4 заклинания. Починили багу походу.

  • 14:20 — turtle пушит параллельный game-loop.

  • 14:41 — я сходил позавтракать, возвращаюсь -- а солвер всё ещё никто не пишет =) Ладно, сел программировать, решил для начала закодить вот этот вариант.

  • 15:09 — понабежал sectoid с идеей, что можно собирать одно длинное заклинание из ходов нескольких фигур.

  • Чуток пообсуждали идею: в целом, мне, например, всё понравилось, но я просто совсем хз как это ровно закодить. Надо же, получается, как-то тащить контекст через ходы всех фигур, включая "freeze move" — ход, который лочит фигуру. Он, получается, тоже должен участвовать в общем деле.

  • 15:30 — я мучаю солвер, sectoid пишет тулзу для jtootf для упрощения поиска новых заклинаний.

  • 16:30 — я сделал estimator, который берёт поле и фигуру и оценивает позицию. Привинтил к визуализатору и запряг turtle оценить вменяемость скоринга.

  • Сам в это время сел делать брутфорсный поисковик позиций для нужд дебага. Суть токова: перебрать нахрен все клетки карты, и в каждую клетку попробовать запихнуть текущую фигуру. Если не получается, повращать её и опять попробовать запихнуть. Для всех мест, куда удалось запихнуть, собрать estimate score и запомнить позицию с максимумом. Короче, самый что ни на есть bleeding edge мировой науки, и вот это всё =)

  • 17:00 — turtle даёт добро на estimate.

  • 17:30 — мержу солвер в мастер и ухожу обедать. Sectoid тем временем сел писать расчёт официального скоринга.

  • 18:00 — пустили параллельный обсчёт и сабмит всех задач на борду с новым солвером.

  • turtle тем временем забрал солвер себе и пошёл экспериментировать с весами разных факторов.

  • 19:06 — досабмитились решения: 18 место в зачёте.

  • sectoid пошёл делать генетический алгоритм для автоматического подбора весов факторов.

  • 19:25 — jtootf вбрасывает в конфу линк на алгоритм "Iterative deepening A*", а я этого не заметил :( Блин тока щас по логам увидел, жесть. Это же верное направление.

  • 19:40 — начинаем с turtle классический вялотекущий срач по поводу гигиены разработки (не трогать грязными руками мастер, если собираешься всё ломать).

  • 20:05 — заканчиваем срач.

  • Я опять закопался в производительность.

  • 21:10 — sectoid добил ГА, подобрать нормальные коэффициенты не удалось :(

  • Я тем временем ради интереса выполнил поиск на гитхабе по ключевому слову "Yuggoth" и нашёл ненулевое количество открытых репо, в которых были файлы с заклинаниями =) Запустили проверку по всем тем, которых у нас не было, но облом -- это всё не заклинания.

  • 22:00 — ищем по инерции ещё заклинания.

  • до 23:00 занимаемся какой-то ерундой. Sectoid дописывает скоринг (не работает), я пробую чуток улучшить генерацию freeze move, чтобы оно, по-возможности, заканчивало заклинание, а не просто лочило фигуру. Заодно проверил, что будет, если эвристику расстояния до цели в A* развернуть обратно: стараться выбирать наиболее длинные маршруты (в надежде, что в маршруты влезет больше заклинаний). Ничего не вышло.

  • 23:00 — прошу turtle собраться, взять свои руками выставленные коэффициенты, свой новый фактор, и довести решение до рабочего состояния, чтобы можно было объективно сравнить с тем, что есть. Если будет явное улучшение — заменим.

  • 00:03 — устал чёто сильно, пошёл погулять.

  • 01:24 — вернулся, врываюсь обратно.

  • Пока гулял, подумал, что целесообразно нарыть в инете какой-нибудь словарик по вселенной лавкрафта, и тупо зарядит батчем на нулевую карту. Если 0 — весь батч выкидывается, если не ноль — ура, в этом батче есть заклинание.

  • Параллельно привычно слазил на гитхаб, посмотреть, как там дела у конкурентов (да, я подлый, знаю). Принёс в берлогу добычу: заклинание Yogsothoth :)

  • На этой оптимистичной ноте стартовала очередная итерация массовой рыбалки на предмет заклинаний.

  • 02:33 — sectoid разгадал подсказку оргов про "Conway. Cocke. Hopcroft. Backus.", итого +1 заклинание: John Bigboote.

  • 02:55 — вылавливаем ещё одно заклинание: tsathoggua

  • 03:07 — вылавливаем Planet 10

  • 03:10 — я пытаюсь найти подсказки в картах. На 24-ой карте обнаруживается закладка: выпадающие в процессе игры фигурки складываются в строку: icfp2015 :) Я уж думал, что это заклинание, но нет.

  • 03:17 — решаем заканчивать на сегодня: собираем все наши найденные заклинания, и запускаем два раза сабмит всех карт: один раз решателем из мастера, второй -- решателем с коэффициентами от turtle. Конечная идея заключается в том, чтобы выбрать лучший вариант.

  • 03:20 — не, не заканчиваем, рыбачим дальше =)

  • 04:06 — turtle, а затем и пришедший ему на помощь sectoid больно бьются об рандомное поведение dymanic variables в кл при использовании в бинаре и с тредами.

  • 04:30 — проблема решена. Но какая-то новая проблема у turtle с бинарём.

  • 04:40 — нет, проблема не решена =) Я пока от безысходности снова ухожу в профилирование.

  • 05:30 — наконец всё работает, turtle сабмитит оба варианта решений.

  • 05:44 — какие-то результаты для сравнения. Нуууу, так — где-то получше, где-то похуже, но в общем поровну примерно.

  • Короче, решаем, что мейнстримом теперь будут параметры turtle, и вмерживаем в мастер. Финальный сабмит, и идём спать. Я лично уже физически валюсь с ног.

  • 06:10 — ложусь физически в кровать и какое-то время сонно размышляю, что нам делать с 24-ой задачей — она слишком здоровая, наш солвер её никогда в жизни не обсчитает. В этот момент меня озаряет, и я чётко понимаю, что я осёл =) Ну конечно же, надо искать позиции тем же самым A*, которым я ищу маршруты, потому что это банальный BFS traversal, и ему можно тривиально ограничить глубину просмотра. А при обходе графа тупо оценивать каждую позицию текущим нашим estimate, и трекать лучший результат. В итоге, на больших картах алгоритм сможет всегда находить решения, пусть иногда и неоптимальные по эвристикам, но неплохие.

  • 06:30 — не выдерживаю, беру ноут и начинаю программировать прямо в кровати — вставать уже сил нет никаких. Параллельно произвожу мощный рефакторинг, и, в итоге, ближе к 10 утра (когда сел ноут) у меня есть решатель в бранче a-star-forever, который умеет быстро решать большие карты номер 14 и 24. На обычных он, правда, даёт результат хуже, чем текущий солвер в мастере, но я надеюсь после 12 дня его настроить.

  • 10:00 — засыпаю, наконец.

  • 12:00 — просыпаюсь, врываюсь в игру.

  • Вкрадце рассказываю о новом решателе, и мы садимся его настраивать.

  • 12:15 — расчехляем ГА имени sectoid, и пытаемся улучшить коэффициенты факторов.

  • 12:30 — у turtle падает инет, у меня тоже падает инет, разваливается конфа, начинается разнообразная возня с резервными каналами, etc. Как всегда, всё крайне вовремя :)

  • Дальше полноценных логов конфы нет, потому что часть общения переместилась то в обычный джаббер, то в скайп, и в итоге мы как-то собрались в скайповой конфе.

  • Ближе к 14:00 удалось подобрать неплохие коэффициенты для солвера a-star-forever

  • После 14:30 внезапно выяснилось, что у меня там какой-то баг, из-за чего использование заклинаний приводит к невалидному решению с нулём очков. Ремонтировать уже некогда, поэтому мы откатываемся на вариант в мастере.

  • И, под самый финал, на сладкое, я неожиданно совершаю косяк и случайно затираю сабмит 14-й задачи в рейтинге. Пересчитать мастером мы её уже не успеваем (результата надо ждать пару часов), поэтому в конце контеста наша команда резко проваливается на 57-ю позицию =)

Ну вот как-то так, в целом. Было занимательно, ещё раз всем огромное спасибо! Выводов на этот раз нет, какой в них смысл, всё равно им не следуем :)

Отчёт turtle можно почитать тут.
Оставить комментарий
[User Picture Icon]
From:pbl
Date:Август, 11, 2015 02:36 (UTC)
(Link)
Это Unagi-то бомжи? :-) Таки взяли первое в квалификации. И это если не вспоминать их вины в прошлых контестах.

> неожиданно совершаю косяк и случайно затираю сабмит 14-й задачи в рейтинге

GET по урлу для сабмишнов дает список всех решений с очками. Это офигенно для отсылки самых лучших решений из всей истории, даже если сами солверы необратимо профтыканы!

Отличный отчет, кстати.
[User Picture Icon]
From:Azamat Kalimoulline
Date:Август, 11, 2015 10:39 (UTC)
(Link)
Вначале там вообще давался скор на решение за весь список засабмиченных решений. Итого было многотыщ действительно у каких-то рандомных бомжей.
[User Picture Icon]
From:pbl
Date:Август, 11, 2015 10:47 (UTC)
(Link)
По-моему, первыми поэксплойтили это именно Unagi. И пока борду не ресетнули, они постоянно болтались там сверху.
[User Picture Icon]
From:Azamat Kalimoulline
Date:Август, 11, 2015 12:47 (UTC)
(Link)
Ну я помню, что там унагей и не было. Не скажу, что часто смотрел, но когда смотрел, были какие-то ноунеймы.
[User Picture Icon]
From:swizard
Date:Август, 11, 2015 15:15 (UTC)
(Link)
> GET по урлу для сабмишнов дает список всех решений с очками. Это офигенно для отсылки самых лучших решений из всей истории, даже если сами солверы необратимо профтыканы!

Вот проклятье, я про это не знал =) Тем более обидно, теперь.
[User Picture Icon]
From:pbl
Date:Август, 12, 2015 09:35 (UTC)
(Link)
А это нигде не было spelled out в их матерьялах. Подразумевалось, видимо, что все сами догадаются, у них такой REST же в сервисах. Это единственная большая польза, которую я получил от зависания на официальном ирц-канале. Под конец там еще развился целый черный рынок Фраз Могущества, но от этого я отшатнулся в омерзении.
[User Picture Icon]
From:swizard
Date:Август, 11, 2015 15:18 (UTC)
(Link)
Unagi, емнип, это чуть ли не команда из десяти каких-то знаменитых японских олимпиадников? Или я ошибаюсь?
[User Picture Icon]
From:pbl
Date:Август, 12, 2015 09:37 (UTC)
(Link)
Ну примерно так, да. Второе в прошлом году, первое в позапрошлом, второе в 2011 и т. д. Стая страшных малолетних японских монстров.
[User Picture Icon]
From:worm_ii
Date:Август, 11, 2015 09:00 (UTC)
(Link)
О, рiдна башкортостаншчына прославлена в веках!
Кстати, двое из этих трёх аццких батыров работают у нас. Третий, почему-то ещё нет.
[User Picture Icon]
From:Azamat Kalimoulline
Date:Август, 11, 2015 12:48 (UTC)
(Link)
А что за контора у вас?
[User Picture Icon]
From:swizard
Date:Август, 11, 2015 15:16 (UTC)
(Link)
Подозреваю, что яндекс :)
[User Picture Icon]
From:worm_ii
Date:Август, 11, 2015 17:06 (UTC)
(Link)
primegeo.ru
В Яндекс одного из них приглашали, он не пошёл.
Ждёт предложения от гугла :)
[User Picture Icon]
From:thedeemon
Date:Август, 11, 2015 17:17 (UTC)
(Link)
>Параллельно меня опять "осеняет" (прямо сезон откровений), что мы, в отличие от классического тетриса, знаем всю игру наперёд -- какие и когда будут выпадать фигуры.

Это как-то использовали в итоге? А то по описанию складывается впечатление, что так по одной фигуре и фигачите.
[User Picture Icon]
From:swizard
Date:Август, 11, 2015 17:40 (UTC)
(Link)
В сабмите нет :( А в a-star-forever я оставил разъём, чтобы можно было ходить по списку лучших стейтов для фигуры — от самого лучшего к следующему и тд. Дальше была мысль поподбирать из таких списков комбинации, максимизируя сумму скоров всех стейтов через DP, но это всё так и осталось в планах.
[User Picture Icon]
From:thedeemon
Date:Август, 11, 2015 17:22 (UTC)
(Link)
В удивительных местах у вас сложности были - центрирование фигур, как его можно сделать не так? :)

С ГСЧ тоже неожиданно. У меня обнаружился нужный ништяк в стандартной библиотеке языка, заработало сразу:
int[] generateUnitsOrder(ulong seed) {
  LinearCongruentialEngine!(ulong, 1103515245UL, 12345UL, 4294967296UL) lcrnd;
  lcrnd.seed(seed);
  auto rnd = chain(only(seed), lcrnd).map!(x => (x >> 16) & 0x7FFF);
  return rnd.take(sourceLength).map!(x => cast(int) (x % units.length) ).array;
}
[User Picture Icon]
From:swizard
Date:Август, 11, 2015 17:43 (UTC)
(Link)
С сдвигах чётных рядов запутались-таки =) И это ещё не самая тупая сложность, с которой мы столкнулись.

ГСЧ быстро сделали, на самом деле, просто, насколько я помню, turtle не сразу сообразил, что первое его значение — это сам seed.

[User Picture Icon]
From:Neil Faccly
Date:Август, 12, 2015 16:59 (UTC)
(Link)
> С сдвигах чётных рядов запутались-таки =)
А у меня повороты фигур всю кровь выпили. Так замучили, что сил никаких не осталось на самое интересное - игратель в тетрис, вместо него какая-то ебулда была, которая кое как играла, я сейчас даже не смогу написать в чем суть.
[User Picture Icon]
From:Azamat Kalimoulline
Date:Август, 11, 2015 20:10 (UTC)
(Link)
ГСЧ написали быстро, начали сверять - первое значение не совпадает. Пока да, сообразили, что это значение от самого сида, причём первые 16 бит только, пришлось чиркнуть пару писем оргам.
[User Picture Icon]
From:pbl
Date:Август, 12, 2015 09:40 (UTC)
(Link)
Я с центровкой тоже что-то потел. Я для всех операций внутре переводил координаты в axial (правда, не знал, что это так называется), по-моему, именно от этого у меня вышла какая-то фигня с центровкой поначалу.
[User Picture Icon]
From:pbl
Date:Август, 12, 2015 09:41 (UTC)
(Link)
А с RNG я напоролся с тем, что неправильно стейт по дереву поиска передавал, shallow copying и все такое. Пожалел, что не стал на Хаскеле писать, когда нашел.
(Оставить комментарий)
Top of Page Разработано LiveJournal.com