Олимпиада по программированию на языке Python
Олимпиада по программированию мобильного робота. Задачей является ориентация робота в городе. У робота есть карта города и цель, куда ему нужно добраться. Отличительная черта в том, что робот заранее не знает, где он находится, у него есть только карта и точка финиша на карте. А также для участия не нужно приобретения никакой электроники и механики. Для того чтобы принять участие, необходим только компьютер и желание.
Прообразом для данной олимпиады послужил беспилотный автомобиль Google. Более того олимпиада проходит на языке Python.
Робот попадает в случайную точку и получает данные с виртуальных датчиков, затем делает ход. Чем больше ходов, тем больше данных, чтобы найти себя по карте города. Тот робот, кто за меньшее число ходов доберётся до точки цели, тот и победил.
Python - это язык программирования общего назначения, распространяемый с открытыми исходными текстами (Open source). Он оптимизирован для создания качественного программного обеспечения, высокой производительности труда разработчиков, переносимости программ и интеграции компонентов. Язык Python используется сотнями тысяч разработчиков по всему миру в таких областях, как создание веб-сценариев, системное программирование, создание пользовательских интерфейсов, настройка программных продуктов под пользователя, численное программирование и в других. Как считают многие, один из самых используемых языков программирования в мире.
Условия участия:
- Команда должна быть от высшего учебного учреждения
- Участие бесплатное
- Необходимо зарегистрироваться, послав заполненную заявку на адрес RobofestSSAU@yandex.ru
- Просьба в теме письма указывать «Олимпиада» и «Заявка», чтобы ваши заявки оперативно обрабатывались. Также по прошествию пары дней просим вас убедится в том, что ваша команда появилась на этой странице. А также перепроверить данные о команде, правильность ФИО участников и название учебного учреждения.
Сроки:
- Промежуточный этап пройдет 25 октября, где будут проведены предварительные испытания программ-роботов. До этого срока необходимо выслать свою программу-робота, на адрес RobofestSSAU@yandex.ru в теме письма указать «Олимпиада»
- Финальный очный тур состоится 14 ноября на II Областном турнире мобильных роботов.
Свои вопросы Вы можете присылать на e-mail: RobofestSSAU@yandex.ru с пометкой "Олимпиада".
С чего начать?
Итак, вы решили участвовать. Мы уже рады за вас, потому что это действительно увлекательно разбираться в таких актуальных и сложных задачах.
Во-первых, что же такое Python и с чем его едят?
Основы Python в кратком изложении:
1) Основы Python в кратком изложении
2) Основы Python — кратко. Строки.
3) Основы Python — кратко. Часть 3. Списки, кортежи, файлы.
4) Основы Python — кратко. Часть 4. Генераторы списков
5) Основы Python — кратко. Часть 5. Определение функций, основы.
6) Основы Python — кратко. Часть 6. Расширенное определение функций.
А также этот ресурс, для тех кто не боится английского.
Далее скачиваем соответствующий дистрибутив для Windows и устанавливаем его. Мы использовали в своей олимпиаде Python 3.3.2. Те участники, которые имеют Linux в качестве своей операционной системы, скорее всего смогут сами разобраться и с тем как его установить на Linux и с самим Python.
В меню Пуск/Все программы появится папка с Python 3.3 как на следующей картинке:
Далее запускаем выделенный на картинке IDLE (Python GUI), появится следующее окно:
Проверим работоспособность:
Measurement - это переменная типа словарь, это означает, что к каждому элементу можно обратиться по названию ячейки.
В данном случае мы получили измерение Measurement, со стороны правого датчика дорога, сверху, снизу и слева - красный дом.
Задание для олимпиады
Рассмотрим задание олимпиады на примере её решения.
Скачиваем у нас этот пример. Распаковываем и открываем Judge.py следующим образом (Edit with IDLE):
Открылся IDLE, по сути текстовый блокнот с подсветкой:
Чтобы запустить пример, выберите пункт меню Run/Run Module или нажмите F5:
В этот раз робот-программа справился за 141 шаг:
Ваше решение содержится только в файле RobotSolution.py. JudgeInit.py и Judge.py необходимы для проверки вашего кода. Если он пройдет проверку Judge.py, то запуститься и у нас.
В чем же заключается задача робота?
Мир, в котором робот ищет финиш, выглядит так:
Но робот его видит по-своему:
Перед каждым ходом робот получает информацию со своих четырех датчиков, которые расположены с четырех сторон робота. Давайте условимся следующим образом: если смотреть на мир сверху (как на картинке), то робот имеет датчики, которые считывают мир сверху, слева, снизу и справа. Теперь мы одинаково понимаем слова "сверху", "снизу", "слева" и "справа".
Ваша задача будет состоять в том, чтобы, имея карту мира, прийти к финишу за как можно меньшее количество шагов. Причем учтите, что сам мир и начальная позиция робота будут отличаться от данного примера на оценочном этапе и финальном туре. Поэтому просим вас стремиться к универсальности алгоритма.
Механизм передачи информации на датчики робота ('up', 'left', 'down', 'right', 'red', 'white', 'road', 'finish'), так же как и исполнительные команды ('up', 'left', 'down', 'right', 'red') не будут меняться ни в коем случае.
И еще одно. Код вашего решения содержится только в файле RobotSolution.py. JudgeInit.py и Judge.py необходимы для проверки вашего кода. Если он пройдет проверку Judge.py, то запуститься и у нас.
В дальнейшем, просим вас присылать только RobotSolution.py на почту RobofestSSAU@yandex.ru с пометкой «Олимпиада» и названием команды.
Так как же все-таки сделать моего робота?
Хорошо, давайте разберем этот вопрос поподробней.
Скачиваем наш пример.
Ваше решение содержится только в файле RobotSolution.py. В дальнейшем присылайте только этот файл. Judge.py и JudgeInit.py - необходимы для отладки вашего кода. Если запустится без ошибок у вас, то и у нас тоже все будет без проблем.
Чтобы разобраться как система проверки работает открываем Judge.py с помощью редактора IDLE. И запускаем нашу программу (F5), тем самым запуская процесс проверки алгоритма робота.
В том примере, что вы скачали алгоритм нахождения финиша случайный.
Проверка алгоритма робота со стороны Судьи (Judge.py):
Сначала инициализация судьи и мира, в котором робот будет ориентироваться:
#Judje side, Goal import JudgeInit GetMeasurement=JudgeInit.GetMeasurement SendMovement=JudgeInit.SendMovement World=JudgeInit.World
Затем импортируются только две функции из вашего решения RobotSolution.py: RobotMove и RobotSense.
#Robot side, Solution import RobotSolution RobotMove = RobotSolution.RobotMove RobotSense = RobotSolution.RobotSense
И начинается проверка вашего алгоритма с подсчетом ходов:
#Judje side, Check the Solution i=0 while not JudgeInit.IsFinished: RobotSense(GetMeasurement()) RobotMove() i+=1 if i>=1000: JudgeInit.IsFinished=True print('Solution exceeded 1000 times of steps') print ('Count of steps:', i)
Обратите внимание, что каждую итерацию цикла с вашему алгоритму выдают новые измерения с датчиков - RobotSense(GetMeasurement()), выполняется ваша команда - RobotMove().
Опрос вашего алгоритма заканчивается тогда, когда робот достиг финиша или, если сказать по-другому, клетки 'finish'.
Переписываем решение (RobotSolution.py):
Содержимое RobotSolution.py:
#Robot side, Solution from JudgeInit import SendMovement from JudgeInit import World Step='' LastMeasurement = ['','','',''] from random import randint def RobotMove(): global Step randvar=randint(0,3) #print ('random=',randvar) if randvar==0: Step='left' elif randvar==1: Step='right' elif randvar==2: Step='up' else: Step='down' print (SendMovement(Step))# You can use RobotMove() without print, like this #SendMovement(Step) def RobotSense(Measurement): global World global LastMeasurement global Step #print (World) LastMeasurement=Measurement #Paste here your code of robot #print ('Robot measures:',LastMeasurement) #print ('Robot measures from up sensor:',LastMeasurement['up']) #print ('Robot measures from left sensor:',LastMeasurement['left']) #print ('Robot measures from right sensor:',LastMeasurement['right']) #print ('Robot measures from down sensor:',LastMeasurement['down']) pass
Сейчас робот даже не анализирует полученные с датчиков данные, а лишь случайно выбирает сторону в какую идти. Причем, не важно, дорога там или дом.
Давайте исправим это.
#Robot side, Solution from JudgeInit import SendMovement from JudgeInit import World Step='' LastMeasurement = ['','','',''] from random import randint def RobotMove(): global Step print (SendMovement(Step))# You can use RobotMove() without print, like this #SendMovement(Step) def RobotSense(Measurement): global World global LastMeasurement global Step #print (World) LastMeasurement=Measurement WhereTo=[] for Direction in LastMeasurement: if LastMeasurement[Direction]=='road' or LastMeasurement[Direction]=='finish': WhereTo.append(Direction) # Now, in List 'WhereTo' we have all directions where to we can go randvar=randint(0,len(WhereTo)-1) if randvar==0: Step=WhereTo[0] elif randvar==1: Step=WhereTo[1] elif randvar==2: Step=WhereTo[2] else: Step=WhereTo[3] pass
Затем необходимо проверить наше новое решение с помощью Judge.py:
Данный алгоритм уже на порядок быстрее предыдущего.
Также обратите внимание, что вам доступна вся карта мира:
... from JudgeInit import World ... def RobotSense(Measurement): global World global LastMeasurement global Step #print (World) # Пользуйтесь доступной картой для нахождения своего местоположения ...
Второй пример доступен по этой ссылке.
Пользуйтесь доступной для вас картой мира для нахождения своего местоположения по данным с датчиков. В этом и заключается "изюминка" данной олимпиады.
И лишь после успешной проверки, получившийся RobotSolution.py отправляем на адрес RobofestSSAU@yandex.ru с пометкой «Олимпиада» и названием команды.
И еще одно: не пытайтесь импортировать переменную RobotPosition в RobotSolution.py, т.к. переменная с текущим положением робота все равно будет называться по-другому.
Удачи вам!