sharpc (sharpc) wrote,
sharpc
sharpc

  • Music:

ICFPC-2008. Жизнь после сабмита.

Часть 2/2. Начало тут.

Первый день я посвятил поискам виртуальной машины, зарывшись в IDA. Бинарник сервера был скомпилирован то ли MLton, то ли SML/NJ, поэтому все выглядело непривычным. Были найдены три основные кандидата на паранойю:

1) зашитые строки /tmp/fileh66xwi.4.S, /tmp/filepBsTWf.3.S, /tmp/fileXajp7t.2.S, /tmp/filel5vY27.1.S (похоже это были ключи для ftok);

2) В двух местах бинарника KANAL обнаружил константу 0x9E3779B9 — это самое близкое к золотой середине среди int32 число (2^{32} \frac{\sqrt{5}-1}{2}). Оно используется во многих алгоритмах шифрования и хэширования (например, в TEA), но здесь, видимо, использовалось в garbage collector.

3) Еще была найдена строка "bogus command exceeds max length". Ознакомившись с http://en.wikipedia.org/wiki/Quantum_bogodynamics, я уж было обрадовался, что есть какие-то читы, но дальнейший безрезультатный поиск привел к мысли, что слово "bogus" употреблено в основном смысле.

Кроме того, кое-кто заметил на официальном канале #icfp-contest, что в бинарнике есть строка "June 1, 1996", а по его словам "this is a day when "Mars Attacks!" movie was ended filming...". Но поиски и в эту сторону результатов не принесли.

Тем более странно это было, учитывая, что организаторы в IRC сообщили, что контест готовился как минимум с января.

Поэтому я разочаровался в задании и подкинул сокомандникам (мы гордо поименовали себя The Little Collider Team) идею о том, как делать pathfinding. Для этого следует построить итеративную триангуляцию Делоне с вершинами в центрах препятствий, затем по ребрам триангуляции построить граф проходимости (вроде как подграф сопутствующей диаграммы Вороного), а на нем тупо искать быстрейший путь. Когда телеметрия присылает данные о новых препятствиях, достраивать триангуляцию. Сокомандники добавили в эту схему мультитредность и клиент с визуализацией на GLUT.

Итог контеста: 209 ревизий (всего 12 из них мои), 422 КБ кода, почти 398 КБ логов IRC... и ни одного сабмита на сервер :) Перед самым концом контеста все заглючило, засегфолтило, а в svn начался форменный бардак. Впрочем, мы не особо много потеряли :)

Искренне желаю, чтобы в следующем году ICFPC вновь порадовал нас интересными и нестандартными заданиями, подобно тому, как это было в 2006 и 2007 годах.
Tags: программирование
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 9 comments