Спортивное программирование *

С момента возникновения программирования было написано множество приложений и библиотек, реализованы сотни алгоритмов, родилось и сменилось не одно поколение программистов. Достаточно внушительную долю специалистов в этой области за свою богатую историю подготовил Университет ИТМО.

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

Спасибо всем участникам нашего последнего конкурса по программированию! Публикуем окончательные, исправленные результаты конкурса.

Мы получили 408 решений от 237 различных участников (в конкурсе участвует только одно, последнее из решений от каждого участника, и мы публикуем именно последние варианты). Кроме того, 14 решений было отправлено нам либо после окончания срока приёма работ, либо сотрудниками Hola, и мы рассмотрели их вне конкурса.

64 решения, или 16% от общего числа, были отправлены в течение последних суток до окончания срока. Из них 15 были отправлены в течение последнего часа, а самое последнее «проскочило» за 34 секунды до дедлайна.

Тесты на корректность прошли 92 программы, что составляет 39% от числа протестированных. Кроме того, корректными признаны 10 из внеконкурсных решений.

Самое короткое решение уместилось ровно в 666 байт, а самое длинное растянулось на 90274 байт.

Один из участников был дисквалифицирован за попытку обмануть тестовую систему. Забавно, что его результат всё равно уступил честным результатам победителей конкурса. Ещё один участник прислал решение с говорящим названием volkswagen.js: оно работает медленно, но корректно при малом размере входных данных, и быстро выдаёт фальшивые результаты при большом размере.

Поздравляем победителей:

Спасибо участникам конкурса по программированию за долготерпение. Я пишу этот пост, чтобы признать и исправить серьёзную ошибку, которую мы допустили при подведении итогов.

Мы получили множество замечаний о методике тестирования решений. Ниже наши ответы на эти замечания.

Тесты на корректность неполны

Спасибо двоим участникам конкурса, приславшим дополнения к нашему набору тестов на корректность. Благодаря этим дополнениям нам удалось выявить несколько решений, выдающих неправильные результаты в редких случаях.

Тесты на производительность дают искажённые результаты из-за особенностей методики тестирования

В ноябре прошлого (уже) года, Hola объявила конкурс по программированию почтовых фильтров на js, и недавно опубликовала его результаты.

Я разделил второе место с Ильей Макаровым, и сейчас я расскажу…

Как это было

Объявление: Мы решили пересмотреть итоги конкурса из-за серьёзных недостатков, обнаруженных в тестовой системе. Подробности в новом посте и окончательные результаты.

Спасибо всем участникам нашего последнего конкурса по программированию!

Мы получили 408 решений от 237 различных участников (в конкурсе участвует только одно, последнее из решений от каждого участника, и мы публикуем именно последние варианты). Кроме того, 7 решений было отправлено нам либо после окончания срока приёма работ, либо сотрудниками Hola, и мы рассмотрели их вне конкурса.

Хочу поделиться опытом работы с задачей известного конкурса по машинному обучению от Kaggle. Этот конкурс позиционируется как конкурс для начинающих, а у меня как раз не было почти никакого практического опыта в этой области. Я немного знал теорию, но с реальными данными дела почти не имел и с питоном плотно не работал. В итоге, потратив пару предновогодних вечеров, набрал 0.80383 (первая четверть рейтинга).

От переводчика: CodinGame – это международная игровая онлайн платформа для программистов, где решение задачи сопровождается визуализацией в стиле видео-игр, а IDE поддерживает 23 языка программирования. Игры проходят с периодичностью один раз в месяц, а решение можно отправить в одну из компаний-спонсоров в качестве резюме на соискании должности. Организации предлагающие позиции зачастую обладают мировым именем, вроде Adobe, UBIsoft, eBay или Nintendo.

На этой неделе стала доступна новая версия IDE. Предыдущая версия уже умела многое: работал автокомплит, подсветка кода и мультикурсор … но теперь среда разработки стала ещё лучше и удобнее. Мы постарались собрать как можно больше отзывов и сделать её более дружелюбной к пользователю, если у вас не было ещё шанса в этом убедиться, вот вам несколько причин для этого:

Сначала этот текст был написан в виде комментария к теме победителя данного конкурса. Но в итоге объем текста стал таким большим, что было решено выделить его в отдельную тему. Так что предполагается, что читатель в курсе о конкурсе и прочёл тему победителя. Также можете почитать историю 30-го места.

Сразу дам ссылку на репозиторий с исходным кодом — помимо непосредственно исходников там же есть вся история коммитов. Например, интересным может показаться время, в которое был совершён коммит с комментарием «спать пора».

В целом, сложилось такое ощущение, что у большинства лидеров были примерно одинаковые основные идеи для итоговой стратегии:

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

Так что в данной теме я расскажу чуть подробнее о том, как эти идеи были реализованы в моём случае.

Хочу рассказать о своем участии и победе в ежегодном соревновании по программированию ИИ «Russian AI Cup 2015» от Mail.Ru Group. Посмотреть подробные правила соревнования и записи игры желающие могут на сайте соревнования russianaicup.ru.



В этом году соревнование было организовано на совершенно новом уровне. Изменения произошли как в масштабности игрового мира, в котором действует ИИ, так и на сайте соревнования. Благодаря трехмерной визуализации, игры смотрелись гораздо увлекательнее. По зрелищности, на мой взгляд, соревнование значительно превзошло прошлогодний хоккей, и «солдатиков» 2013 года.

Участнику предлагалось написать ИИ для управления автомобилем в гонках на выживание. Как и в прошлом году, задача была «с физикой». Но на это раз исходники «физического движка» были открыты. Еще, в отличие от прошлого года, на этот раз все случайные явления в игровом мире были наглядны — случайная карта, случайно расставленные бонусы. Сразу было видно — когда удача на твоей стороне, а когда она от тебя отвернулась. В прошлогоднем хоккее, даже наблюдая за игрой значительно отличающихся по силе противников, было трудно понять произошел выигрыш благодаря случаю или мастерству. Думаю, это положительно сказалось на зрелищности соревнования.

Краткое описание правил

Цель — проехать 2 круга по замкнутой трассе быстрее всех. Точнее надо набрать больше всех очков, но приехать первым — это основной способ заработать очки. Еще очки дают за сбор бонусов по дороге и нанесение урона противникам. Трасса, как конструктор, собирается из квадратных «тайлов», это прямолинейные участки трассы, углы (поворот трассы на 90 градусов), или перекрестки (Т образные и обычные). Нужно ехать по ключевым точкам («тайлам») трассы в определенном порядке – иногда приходится делать петли, иногда вообще ехать назад. Еще у машинок есть возможность разливать за собой лужи мазута, стрелять друг в друга специальными снарядами (шины и шайбы), и использовать особый ускоритель «нитро». Заряды для всех этих приспособлений ограничены, и пополняются подбиранием случайно разбросанных по карте бонусов.

Расскажу, как устроен мой ИИ, и благодаря чему (как я думаю) удалось победить.

Мое хобби, помимо программирования — разработка модификаций под игру S.T.A.L.K.E.R. Работаем мы в команде, где, как и принято, каждый отвечает за что-то свое. Я, помимо того, что вхожу в круг разработчиков, еще и осуществляю разработку ПО для команды. Под катом читайте, как мы автоматизировали распаковку игровых архивов, с какими проблемами столкнулись и как их решили.

Введение

В этом году в Russian AI Cup надо было запрограммировать бота для управления машинкой (а в финале даже двумя!), и я решил впервые поучаствовать, так как тема показалась близкой и родной: фанат гонок, периодически езжу катать в картинг (хоть и без выдающихся результатов), вечера часто провожу, катаясь по виртуальным Гавайям в Test Drive Unlimited или Nurburgring в GTR Evolution.

Высокого места я в итоге не занял (30 место в финале, песочницу закончил на 48 месте), но небольшое время между вторым раундом и финалом был в топ-10 песочницы. Также, судя по форуму соревнования, набор костылей решений как у меня больше никто не использовал, так что если желаете узнать подробностей — добро пожаловать под кат. Наиболее интересная часть в посте, пожалуй, про поиск оптимальной траектории.

Удивлен, что ссылки на Advent of Code до сих пор не видно на Хабре.



Если вкратце, то это рождественский календарь, где каждый день открывается по небольшой задачке на программирование. Сегодня пятница, и уже открыто 18 штук — отличный повод размять мозги, или потренироваться в написании программ на новом языке, до изучения которого никак не доходили руки.

После того, как вроде бы неплохой результат, полученный в предыдущей части, оказался лишь «локальным максимумом», я на некоторое время забросил задачку. Напомню условие:

«The decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number». Или, по-русски: «Десятичное число 585 в двоичной системе счисления выглядит как 1001001001. Оно является палиндромом в обеих системах счисления. Найдите n-й подобный палиндром».

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

В конце концов, алгоритм оказался не таким уж и сложным, зато, на мой взгляд, очень красивым.

Code Game Challenge – захватывающий формат соревнований, который вызывает у студентов большой интерес. В рамках IV Всероссийской молодёжной школы по робототехнике, встраиваемым системам и компьютерному зрению (http://roboschool.org), которая прошла в ноябре в Волгограде, мы хотели преподнести участникам что-то новое. Так родилась идея RoboCGC – совместить роботов и CGC. Подробности под катом.

13 декабря завершился финал четвёртого ежегодного чемпионата по программированию искусственного интеллекта Russian AI Cup. В этот раз своё мастерство продемонстрировали свыше 1 600 программистов, создававшие искусственный интеллект для управления автомобилем в гонках на выживание.

По условиям чемпионата можно было использовать один из языков: C++, Java, C#, Python, Ruby или Pascal. После серии напряжённых состязаний в финал выбились 50 сильнейших. И по результатам последней «гонки» золотой приз завоевал Александр «santa324» Санталов из Москвы. В качестве награды он получил MacBook Pro. «Серебро» и «бронза» достались Антону «Angor» Гордиенко из Москвы и Юрию «SDil» Семёнову из Санкт-Петербурга, они были награждены ультрабуками MacBook Air. Не остались без призов и конкурсанты, занявшие с четвёртого по шестое места, им были вручены планшеты iPad Air 2. Поздравляем Дениса «ud1» Уткина, Сергея «SKolotienko» Колотиенко и Сергея «Karkun» Иванова! Однако остальным участникам ещё рано расслабляться, а нам рано подводить окончательные итоги чемпионата. Предстоит ещё неделя состязаний в Песочнице, и по их итогам лучшие 6 участников получат поощрительные призы от партнёров мероприятия.

Не так давно прочитал на хабре статью grey_wolfs «Вперед, на поиски палиндромов» о решении и оптимизации любопытной конкурсной задачки с весьма лаконичной формулировкой:

«The decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number». Или, по-русски: «Десятичное число 585 в двоичной системе счисления выглядит как 1001001001. Оно является палиндромом в обеих системах счисления. Найдите n-й подобный палиндром».

Мы рады сообщить о начале очередного международного чемпионата по программированию искусственного интеллекта — Russian AI Cup. В этот раз чемпионат получил название CodeRacing. Храбрецам, которые отважатся принять участие, предстоит программировать искусственный интеллект для управления гоночным автомобилем. Но он должен будет не просто исполнять роль водителя, но и одновременно расстреливать соперников. В «игровом» мире предусмотрено четыре типа юнитов: кодемобили, снаряды, бонусы и лужи мазута. Самые «грязные» приёмы на трассе будут только поощряться: можно толкать чужие машины, повреждать их и ломать.

UPDATE: Опубликованы итоги конкурса.

Компания Hola снова объявляет конкурс по программированию на JS с солидным призовым фондом:

1. Первое место: 1500 USD
2. Второе место: 1000 USD
3. Третье место: 500 USD
4. Возможно, мы решим отметить чьё-то чрезвычайно оригинальное решение специальным призом в 350 USD.
5. Если Вы отправите кому-то ссылку на этот конкурс, поставив наш адрес в CC, и этот человек займёт призовое место, Вы получите такую же сумму, как и он.

Мы ищем талантливых программистов, поэтому авторы интересных решений будут приглашены на собеседования.

Правила

Некоторые из тех, кто помнит наши предыдущие конкурсы, были недовольны тем, что условия задач были сформулированы нечётко, и от участника требовалось «угадать», что мы имели в виду. На этот раз условие сформулировано предельно однозначно, а в распоряжении участников — эталонная реализация решения. Победит тот, чей код будет самым быстрым при условии прохождения тестов на корректность.

Условия конкурса на английском языке размещены на нашем сайте. Ниже — перевод на русский язык.

Соревнование Back to the Code закончилось и мы получили огромное удовольствие от просмотра различных повторов игр и изучения стратегий в каждой. Мы увидели достаточное количество хороших идей и мы надеемся вы насладились игрой в той же степени, что и мы.

Recar и Olaf69 оба разработали отличную стратегию, которая позволила им добраться до вершины турнирной таблицы и они согласились ею поделиться, таким образом вы можете открыть для себя секретные ингредиенты их секретно-ингредиентного супа.

Не так давно на Хабре была статья про codebattle от hexlet.io. Ну и затянуло же нас с друзьями, это как наркотик! Вроде пытаешься на работу отвлечься, а руки прям сами тянутся зайти на сайт, и все мысли — об оптимизации решений.

И вот однажды попалась мне задачка, звучала она так: «The decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number». А если по-русски, то так: «десятичное число 585 в двоичном виде выглядит как 1001001001. Оно является палиндромом в обеих системах счисления. Найдите n-ый подобный палиндром». Она совсем не сложная и решена была быстро.

function is_palindrome($num) {
   return $num == strrev($num);
}
function solution($num) {
   $count = $i = 0;
   while($count<$num) {
      $i++;
      // Проверяем по порядку все числа, являются ли они палиндром в десятичном и двоичном виде
      if (is_palindrome($i) && is_palindrome(decbin($i))){
         $count++;
      }
   }
   return $i;
}

Но вот незадача. Примерно в то время на сайт напал хабраэффект, и тесты ни в какую не хотели проходить, отваливались по timeout. В местном чате началось обсуждение по оптимизации решения, но никто дельного совета так и не дал. Потом сайт отпустило, все тесты прошли, но желание оптимизировать осталось…