unsigned long int128 (jerom) wrote,
unsigned long int128
jerom

Category:

icfpc 2009 lightning round

Отчёт про игру в icfpc-2009: реальные score 1006.1338, виртуальные LR: 2580.

Хохман (Гоман) - это http://en.wikipedia.org/wiki/Hohmann_transfer_orbit
Моя VM + рисовалка в 3003 задаче: http://paste.org.ru/?gf5crk

Виртуальные по задачам 4001-4004 я опишу позже, у меня ещё есть 16 часов.

Команды у меня не было, хотелось просто попробовать.

Я планировал ровно в 22:00:16 приступить к задачам, но времени не было, начал разбираться где-то в 0:01, можно сказать, в субботу.

Неработающая машина у меня была готова быстро, но только в 2:50 я узнал, что в спеке поменяли описание imm. В результате, в 3 ночи получил летающий нормально по кругу спутник (вся VM на этот момент была 80 строк).

Начал разбираться с координатами, двигателем, попутно ускорил vm в 100 раз (не отыгрывая последние 16000 NOOP :-)

Успокоился с оптимизацией машины я слишком рано. Если бы сразу написал не интерпретатор, а компилятор в перл (позже я сделал это за 10 минут), то скорость выросла бы в 10 раз, примерно до 15000 секунд за секунду на 3003 задаче. А если компилятор в C, да заinlinить в perl (XS), то это миллион секунд в секунду.


Задачи 1001-1004

Программировал чистого Хохмана, при это только горизонтального или вертикального (выжидал нулевой скорости вертикальной или горизонтальной и пыщал).

К 4 утра промахивался на 1000 км, к 4:30 - держался 1000 секунд в километре, но не по инерции.

К 4:55 получил первые ненулевые очки локально, начал делать сабмиттилку и делал её почти час параллельно с решением 1002-1004. В 5:54 получил очки первые 4 задачи (прошло чуть меньше 8 часов с начала соревнования): score: 260.42263.

Задачи 2001-2004

Примерно 30 минут просто тормозил, глядя на 2001 задачу. К этому моменту я знал, что мои координаты перевёрнуты, но уже ничего не исправлял.

Потом понял, что надо уметь делать Хохмана с любого угла и просто ждать нужное время (на 1й симуляции смотрим, на сколько обогнали, на второй включаем двигатели с задержкой).

В 7:30 у меня была зачтена 2001 задача, но потом я долго возился с остальными. В результате в 9:10 попал на второе место в scoreboard с 1006.1338.

В этот момент я удалился от icfpc и вернулся к нему только через 2 суток.

Задачи 3001-3004

К ним я приступил в 21:00 в понедельник, шансов на сабмит уже не было, но решить хотелось.

icfpc 3001 bug
«icfpc 3001 bug»

Разбираться с произвольными манёврами мне не хотелось, Хохман это наше всё. Начал я с определения параметров орбит. Самым простым способом: гоняем симуляцию подольше, ищем минимумы и максимумы орбит и углы поворота. После чего долго не мог попасть в нужную орбиту, написал визуализатор (прошло 3 часа), догадался ввести круговую орбиту промежуточного ожидания. Кроме того в первую же секунду делал свою орбиту круговой (хотя потом оказалось, что она и так всегда круговая).

После чего написал функцию из серии: "по всем k от 1..20 и n 1..20 ищем орбиту med от my до target с шагом 1 метр такую, чтоб k*target_half_time - n*med_time - time_to_med - time_from_med - rotation_time == 0", где rotation_time - время доворота до оси эллипса.

icfpc-2009 task 3001
icfpc 3002
icfpc 3004



Результат для 3001, 3002, 3004 нашёлся легко: 371.516 + 347.132 + 372.635. Полный манёвр был таким:

  1. сделать свою орбиту окружностью сразу
  2. выждать доворота на ось эллипса
  3. hohmann transfer на орбиту med
  4. коррекция до окружности на med
  5. выждать на med нужно количество полувитков
  6. hohmann transfer на одну из орбит target (t_min)
  7. двойная коррекция на t_min: 1 до окружности и сразу вторая до эллипса (всё по хохману)
  8. догон на струе, если надо



А вот с 3003 мне не хотелось ждать конца симуляции, там оборот target около 10 суток. Поэтому руками просто вписал: сразу прыг и через некоторое время догоняем на реактивной струе. Резальтат: 364.377 (за 27014 секунд). Формулы догонялки примитивна: на каждом втором шаге inp_x = dv_x + dx/mult, где mult - какая-то константа типа 10000.

icfpc 3003

Получается, если бы я работал всю субботу, то за LR мог бы получить score 2461.794. А догадавшись выжечь всё топливо в 1001-1004 (несколькими сильными импульсами это легко) и все 2580.




Посмотрим, каковы будут результаты LR. Задачи 4001-4004 я собирался решать на основании 3001, тем же Хохманом с промежуточными орбитами ожидания. И ещё попробую это сделать, потратив не более 16 часов.

icfpc 4004

Задачи 4001-4003 более-менее ясны, а вот в 4004 спутник крутится не в том направлении. Картинки 4001-4003 без решения: http://fotki.yandex.ru/users/jerom/album/70551?p=0






Tags: icfpc
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 8 comments