![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
dastapovВот они, родимые.
Мы - на позорном 131 месте. Где-то за 20 минут до финиша, когда мои товарищи по команде вырубались после бессонной ночи, возник вопрос - какой же солвер сдавать в качестве финального?
У нас их было два - один реализовывал А* поверх А*, как описано вот тут, не умел бэктрекинга, шел только вперед и выводил части программы по мере достижения очередной лямбды.
Второй солвер запускал два треда, и в одном крутил первый солвер, подсчитывая набранные очки после каждого выданного куска программы и запоминая лучший полученный результаты. Во втором треде крутился тупой-тупой А* над игровыми состояниями, целевой функцией которого было найти программу с оценкой лучше текущей имеющейся, а эвристикой - сумма расстояний до лямбд.
На мелких картах второй тред успевал перебрать все (или почти все) и выбраться из практически любой ловушки. На больших же картах он рисковал со временем пожрать всю память и быть убитым OutOfMemory Killer-ом (который живет в ядре linux). Если бы это произошло, то мы бы на такой карте не набрали ничего. Осознание этой засады пришло слишком поздно, и сделать какой-то монитор/ограничитель мы уже не успевали.
Забоявшись out of memory, я убедил полусонных Женю и Ваню, что сдавать надо первый вариант. В результате мы вылетели в первом раунде.
Второй вариант набрал бы как минимум 7200 очков (я запускал его на оценочных картах с лимитом в 30 секунд, а за 150, думаю, он мог бы набрать и больше) и мы были бы где-то в районе 50-60 месте. Ну, как известно, если бы да кабы ... :) Мораль придумайте сами.
Посмотрим, что будет в следующем году.
Мы - на позорном 131 месте. Где-то за 20 минут до финиша, когда мои товарищи по команде вырубались после бессонной ночи, возник вопрос - какой же солвер сдавать в качестве финального?
У нас их было два - один реализовывал А* поверх А*, как описано вот тут, не умел бэктрекинга, шел только вперед и выводил части программы по мере достижения очередной лямбды.
Второй солвер запускал два треда, и в одном крутил первый солвер, подсчитывая набранные очки после каждого выданного куска программы и запоминая лучший полученный результаты. Во втором треде крутился тупой-тупой А* над игровыми состояниями, целевой функцией которого было найти программу с оценкой лучше текущей имеющейся, а эвристикой - сумма расстояний до лямбд.
На мелких картах второй тред успевал перебрать все (или почти все) и выбраться из практически любой ловушки. На больших же картах он рисковал со временем пожрать всю память и быть убитым OutOfMemory Killer-ом (который живет в ядре linux). Если бы это произошло, то мы бы на такой карте не набрали ничего. Осознание этой засады пришло слишком поздно, и сделать какой-то монитор/ограничитель мы уже не успевали.
Забоявшись out of memory, я убедил полусонных Женю и Ваню, что сдавать надо первый вариант. В результате мы вылетели в первом раунде.
Второй вариант набрал бы как минимум 7200 очков (я запускал его на оценочных картах с лимитом в 30 секунд, а за 150, думаю, он мог бы набрать и больше) и мы были бы где-то в районе 50-60 месте. Ну, как известно, если бы да кабы ... :) Мораль придумайте сами.
Посмотрим, что будет в следующем году.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
(no subject)
Date: 2012-08-01 10:04 pm (UTC)Я их шелл скриптом все валил >> в один файл, запустив каждый алгоритм с амперсандом (3 жава процесса).
Потом пишется трап, в нём sort -rn | awk | head -1
Считаю, это лучший кусок кода, написанный в этом ICFPC. Позорное 45 место.
(no subject)
Date: 2012-08-01 11:49 pm (UTC)(no subject)
Date: 2012-08-02 07:26 am (UTC)Мысль о том, что можно было запускать два солвера из шелловского скрипта пришла ко мне где-то спустя час после окончания ICFPC :)
(no subject)
Date: 2012-08-02 01:10 am (UTC)(no subject)
Date: 2012-08-02 06:17 am (UTC)(no subject)
Date: 2012-08-02 03:49 am (UTC)(no subject)
Date: 2012-08-02 07:22 am (UTC)(no subject)
Date: 2012-08-02 07:28 am (UTC)Все гениальное просто ...
(no subject)
Date: 2012-08-02 07:42 am (UTC)(no subject)
Date: 2012-08-02 08:02 am (UTC)(no subject)
Date: 2012-08-02 07:28 am (UTC)(no subject)
Date: 2012-08-02 05:55 pm (UTC)(no subject)
Date: 2012-08-02 09:01 pm (UTC)(no subject)
Date: 2012-08-10 08:00 am (UTC)