<< Вернуться на главную

ЧУДО ТРАКТОР

Конкурс программистов сезона 2019-2020 закончен.

И опять на очный этап пришло только 5 человек (причем трое - первокурсники и участники прошлогодних конкурсов). Пришлось провести турнир для номинации "школьники" и номинации "студенты" :-)

Условия конкурса и страничку заочного этапа можно скачать тут.

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

На очный этап было предложено 3-и участка. Первый условно назван "монолит" (единое поле с отдельными отростками). Второй участок имел "регулярную структуру" (по сути шахматная доска) ну а третий участок был представлен "Нерегулярной структурой" (специально сконструированной генератором случайных чисел).
Очные задания выглядели вот так:

Задача чисто теоретически поддающаяся полной оптимизации. Однако дополнительное условие, на ограничение времени работы программы (5 минут) делало невозможной полную оптимизацию. Для того чтобы вспахать максимум полей и уложиться в отведенное время, необходимо было снабдить свою программу кучей "эвристик". Все это усложняло и без того сложную задачу.

В общем все как в жизни, как оптимизировать вроде понятно но это невозможно :-).

Таким образом, участникам нужно было за 3-а часа приготовить решение для всех вариантов. Победитель определялся по максимальному суммарному количеству вспаханных участков.

Если вы хотите попробовать свои силы, то скачиваете проект заочного этапа (в соотватствии с удобным для вас языком программирования). Распаковываете и пробуете!
Версия для LAZARUSа.
Версия для С++BUILDER 9.

Для пробы работы с версиями очного этапа нужно скачать соответствующую версию картинки (можно прямо с этой странички, переименовать картинку в "1.bmp" и заменить ее в вашем проекте.

ВНИМАНИЕ! Для проекта на C++ BUILDER картинка помещается в папку "DEBUG" (впрочем, те кто работает на нем и так должны это знать).

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

здесь можно посмотреть, как проходил конкурс

Памятные сувениры	Конкурс	рабочий момент	"Прямоугольный" алгоритм
Конкурс	Экран победителя	1-е место среди первокурсников	1-е место 10-11кл

Результаты финальной битвы:

Фамилия и имя	1-е задание	2-е задание	3-е задание	Итог	Место
Пимонов Даниил	2967	2782	2506	8255	1-е место (1-й курс ТУСУР)
Лазеев Сергей	2955	2592	1380	6927	1-е место (10-11 кл.)
Агафонов Ярослав	2825	1418	2072	6315	2-е место (1-й курс СФУ ИИФиРЭ)
Керемецкий Артем	2063	1414	1413	4890	2-е место (10-11 кл.)
Климов Иван	1647	2805	206	4658	3-е место (1-й курс ТУСУР)

Анализ.

Очень порадовало обилие алгоритмов. Практически каждый участник работал со своими алгоритмами очень непохожими друг на друга. Выл тут и рекурсивный алгоритм подобный заливке картинки, и алгоритм подьема на гору, и векторный анализ и даже нейросеть! По результатам видно, что одни алгоритмы оказались оптимальнее для одних картинок а другие для других.

1) Нейросеть обучалась все три часа подряд и в итоге смогла вспахать аж 20 участков :-). На наш вгляд применение нейросети было неудачным (а сама нейросеть похоже получилась без сходимости обучения). Если уж применять такие алгоритмы, то скорее надо было использовать комбинированный способ управления (частично нейросеть - частично минимальное расстояние). Но правда автор алгоритма не стал на нее расчитывать и пока она там училась (непонятно чему :-) он реализовал рекурсивный алгоритм, который всех победил во втором задании
2)Очень интересно выглядел алгоритм, в котором просто выбиралась прямоугольная область и трактор как челнок катался на ней вправо влево. НА первый взгляд алгоритм простейший (ну разве что столбы мешают). Однако как оказалось он вполне может конкурировать с самыми сложнейшими алгоритмами (особенно в самой сложной "случайной" карте). А главное по сравнению с остальными этот алгоритм работал мгновенно!
3)Остальные алгоритмы в основном состояли из ветки нахождения ближайшей клетки пригодной для пахоты и далее заливки ближайших доступных клеток (с разными эвристиками). У всех эвристики были разные. И поэтому в ходе конкурса рисовались такие красивые картнки... Кроме того не всем полностью удалось задуманное и поэтому результаты разные.

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

Всем участникам, зарегистрировавшимся на заочном этапе были вручены памятные сувениры (напечатанные на 3д принтере трактора ДТ75) и соответствующие грамоты. Победителям вручены малюсенькие подарки (что поделать, спонсоры так и не горят желанием посодействовать)

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

Так как все участники оказались знакомы между собой, турнир был закончен рубиловом в квак-3 :-). В результате как всегда победила дружба!

Благодарим всех участников конкурса, которые пожертвовали последним днем каникул, не испугались мороза и злых конкурентов :-).
Большое спасибо ребята! Администрация конкурса желает Вам всяческих успехов в новом году (и в жизни).

Вопрос-ответ.