dastapov: (Default)
[personal profile] dastapov
Вот они, родимые.

Мы - на позорном 131 месте. Где-то за 20 минут до финиша, когда мои товарищи по команде вырубались после бессонной ночи, возник вопрос - какой же солвер сдавать в качестве финального?

У нас их было два - один реализовывал А* поверх А*, как описано вот тут, не умел бэктрекинга, шел только вперед и выводил части программы по мере достижения очередной лямбды.

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

На мелких картах второй тред успевал перебрать все (или почти все) и выбраться из практически любой ловушки. На больших же картах он рисковал со временем пожрать всю память и быть убитым OutOfMemory Killer-ом (который живет в ядре linux). Если бы это произошло, то мы бы на такой карте не набрали ничего. Осознание этой засады пришло слишком поздно, и сделать какой-то монитор/ограничитель мы уже не успевали.

Забоявшись out of memory, я убедил полусонных Женю и Ваню, что сдавать надо первый вариант. В результате мы вылетели в первом раунде.

Второй вариант набрал бы как минимум 7200 очков (я запускал его на оценочных картах с лимитом в 30 секунд, а за 150, думаю, он мог бы набрать и больше) и мы были бы где-то в районе 50-60 месте. Ну, как известно, если бы да кабы ... :) Мораль придумайте сами.

Посмотрим, что будет в следующем году.

(no subject)

Date: 2012-08-01 10:04 pm (UTC)
From: [identity profile] http://users.livejournal.com/_san/
У нас тоже было 3 алгоритма, но не жручие. И каждый алгоритм как только найдет очередной best, так сразу и рисовал результат вместе со score.
Я их шелл скриптом все валил >> в один файл, запустив каждый алгоритм с амперсандом (3 жава процесса).
Потом пишется трап, в нём sort -rn | awk | head -1
Считаю, это лучший кусок кода, написанный в этом ICFPC. Позорное 45 место.

(no subject)

Date: 2012-08-01 11:49 pm (UTC)
From: [identity profile] juan-gandhi.livejournal.com
Во как классно.

(no subject)

Date: 2012-08-02 07:26 am (UTC)
From: [identity profile] http://users.livejournal.com/_adept_/
"Умная мысля приходит опосля"

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

(no subject)

Date: 2012-08-02 01:10 am (UTC)
From: [identity profile] nivanych.livejournal.com
Исходники уж ладно, но где посмотреть, какие языки кто пользовал?

(no subject)

Date: 2012-08-02 06:17 am (UTC)
From: [identity profile] alexott.livejournal.com
jsn писал на языке Ц (http://jsn.livejournal.com/83836.html) - там есть ссылка на исходники

(no subject)

Date: 2012-08-02 03:49 am (UTC)
From: [identity profile] max630.livejournal.com
а как бы соотнести названия с кодом? jabber.ru, я так полагаю, aleksey, а остальные?

(no subject)

Date: 2012-08-02 07:22 am (UTC)
From: [identity profile] janatem.livejournal.com
Так надо было вторую команду зарегистрировать и посылать вторую версию от ее имени.

(no subject)

Date: 2012-08-02 07:28 am (UTC)
From: [identity profile] http://users.livejournal.com/_adept_/
Блин :)

Все гениальное просто ...

(no subject)

Date: 2012-08-02 07:42 am (UTC)
From: [identity profile] janatem.livejournal.com
;) Я вообще думал, что «важно имя, с которым мы выступали много лет», поэтому такой вариант не годится.

(no subject)

Date: 2012-08-02 08:02 am (UTC)
From: [identity profile] http://users.livejournal.com/_adept_/
Имя как раз каждый год новое, это не принципиально

(no subject)

Date: 2012-08-02 07:28 am (UTC)
From: [identity profile] http://users.livejournal.com/_navi_/
Я всё же считаю, что в нашем случае многопоточность и слишком долгая разработка солвера с ней (в том формате, в котором мы это делали) — это большая ошибка, которую стоило исправлять как можно скорее (я вроде пытался это выразить в процессе, но наверно недостаточно хорошо). Должен был быть один поток (так как гонялось всё всё равно на одном виртуальном процессоре), который бы умел переключаться между различными подходами в зависимости от ситуации. Ну и наличие настоящего бэктрэкинга бы переместило нас сильно вверх.

(no subject)

Date: 2012-08-02 05:55 pm (UTC)
From: [identity profile] pbl.livejournal.com
Организаторы порядочно отмочили, конечно. Все карты первого тура мелкие и смехопозорные. Моя безмозглая железяка, в которой кроме тупого лукахэда просто больше ничего нет, пришла на позорном двадцать пятом месте, хотя на картах тридцать на тридцать она уже просто умирать начинает из-за неэффективного апдейта игрового поля.

(no subject)

Date: 2012-08-02 09:01 pm (UTC)
From: [identity profile] psi-storm.livejournal.com
ну дык идея как раз и была в том что тупопереборные решения должны проходить первый раунд

(no subject)

Date: 2012-08-10 08:00 am (UTC)
From: [identity profile] -darkus-.livejournal.com
Да уж. Жаль.

Profile

dastapov: (Default)
Dmitry Astapov

April 2017

M T W T F S S
     12
3 45 6789
10111213141516
17181920212223
24252627282930

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags