Информация
Отчет

JavaScript Challenge

Микола Сеник

Битва роботів — це нове випробування Ваших JavaScript здібностей. Необхідно розробити  алгоритм поведінки робота у лабіринті. Ваша мета — вивести робота з лабіринту за найменшу кількість кроків.

walle_small
На що схожий Ваш робот? Це доволі потужний пристій, він має:

  • вбудований інтерпретатор JavaScript
  • сенсори з можливістю розпізнавання зображень (відрізняє стіну від проходу)
  • шасі — може їхати вперед та повертати праворуч та ліворуч

Приз переможцю — Xiaomi Mi Band.

Увага, термін подачі робіт подовжено на 10 днів. Фінал буде 10 серпня!

Особливості робота

Робот може виконувати 4 прості операції:

  • крок вперед
  • поворот праворуч
  • поворот ліворуч
  • сканування периметру

На жаль, функція “очей” (сканування периметру) нашого роботу витрачає багато енергії. Тому перед тим як “розплющити очі” робот має зупинитися. Те саме стосується і поворотів. Повертати і рухатись одночасно робот не може. Іншими словами робот виконує лише одну команду за раз.
Поясню на прикладі. Подивіться на ланцюжок з 7 команд робота:
move (1), scan (2), left (3), move (4), scan (5), right (6), move (7)

Перекласти її можна так:

  1. крок вперед
  2. просканувати периметр
  3. повернути ліворуч
  4. крок вперед
  5. просканувати периметр
  6. повернути праворуч
  7. крок вперед

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

Особливості лабіринту

Лабіринт, з якого треба знайти вихід буде великим та складним. Нехай Вас не вводить в оману проста структура тестового лабіринту:

sample_mazeКонкурсний лабіринт скоріше буде схожим на наступний (матиме порожні простори, проходи що перетинаються, довгі коридори з великою кількістю бокових проходів тощо):

complicated_maze

Умови конкурсу

У конкурсі може взяти участь необмежена кількість учасників. Єдина умова — алгоритм поведінки робота має бути написаний на JavaScript.
Роботи необхідно надіслати електронною поштою на скриньку: msenyk@malkosua.com
Граничний термін подачі робіт 10 серпня 2015 року.

 

Форма подання робіт

Алгоритм має бути оформлений у вигляді анонімної функції, яка повертає об’єкт наступної структури:

{
  name: “Назва алгоритму, ваше ім’я чи псевдонім”,
  roboFunc: function(api)
}

де roboFunc — це функція, що реалізує основний алгоритм поведінки робота. У якості аргументу вона завжди отримує об’єкт доступу до API робота. Ця функція буде викликатися кожного разу, коли вам необхідно віддати команду роботу. Обрана команда має бути повернена через оператор return. Наприклад,

return api.CMD_MOVE;

Наступний виклик цієї функції поверне результат виконання команди у полі api.result. Для команд поворотів (api.CMD_LEFT та api.CMD_RIGHT) — результат завжди успішний (робот розвертається на місці):

{success: true}

Але для кроку вперед він може бути негативним, якщо попереду робота стіна (чи закриті двері):

{success: false}

Для команди сканування (api.CMD_SCAN) результати більш інформативні:

{success: true, before: “wall”, left: “space”, right: “exit”}

Сканування відбувається майже по всьому периметру, тому одночасно робот знає що знаходиться попереду нього, ліворуч та праворуч. Що знаходиться позаду робота він не бачить.
Можливі варіанти розпізнаної місцевості:

  • wall — стіна
  • space — прохід
  • exit — вихід з лабіринту
  • key — ключ

Останнім кроком робота має бути команда api.CMD_MOVE у напрямку виходу за умови, що робот знайшов ключ.

Найпростіший алгоритм може виглядати так:

function() {
    return {
        name: “Simple”,
        roboFunc: function(api) {
            if ( api.result.success ) {
                return api.CMD_MOVE;
            } else {
                return Math.random() > 0.5 ? api.CMD_LEFT : api.CMD_RIGHT;
            }
        }
    };
}

Звичайно він зможе вийти не з кожного лабіринту, але тестову модель він подужає за певну кількість кроків.

 

Опис API робота

Команди робота

Крок вперед

Ви повертаєте управління командою return api.CMD_MOVE. Якщо наступного разу api.result.success дорівнює true — переміщення на крок вперед відбулося успішно. У випадку коли api.result.success дорівнює false робот наштовхнувся на стіну (чи закритий вихід) і переміщення не відбулося.

Поворот праворуч

return api.CMD_RIGHT;

Поворот ліворуч

return api.CMD_LEFT;

Сканування периметру

return api.CMD_SCAN;

Результати сканування доступні у наступний виклик у полі api.results.

Загальні константи

api.PLACE_WALL — результат сканування стіни
api.PLACE_SPACE — результат сканування вільного проходу в лабіринті
api.PLACE_EXIT — результат сканування виходу
api.PLACE_KEY — результат сканування ключа
api.LEFT — напрямок сканування ліворуч
api.RIGHT — напрямок сканування праворуч
api.BEFORE — напрямок сканування безпосередньо перед роботом

 

Тестовий майданчик

Перевірити вашу реалізацію ви зможете тут:
http://jsfiddle.net/MykolaSenyk/up7sy3so/

Для того, щоб додати вашу реалізацію використайте наступний код:

// init your code here
algorithmHolder.putInstance(1, function () {
    // ваш код
}());

Першим аргументом функції algorithmHolder може бути ціле число від 1 до 3.

 

Визначення переможців

Після 1 серпня алгоритми учасників будуть перевірені на досить складному лабіринті. Переможе алгоритм, який виведе робота з лабіринту за найменшу кількість кроків. Якщо таких учасників виявиться декілька — можливе проведення другого раунду (інша структура лабіринту). Якщо і цей раунд не виявить переможця — то перевагу буде віддано найбільш швидкому алгоритму.
Результати будуть опубліковані на сайті спільноти.

 

Запитання та відповіді:

1) Чи є генератор лабіринтів? Чи лабіринт буде завжди один і той самий?

Лабіринт для конкурсу буде один, але достатньо великий, тому вгадати короткий шлях до виходу буде досить складно.

2) Чи достатньо наступити (наїхати) на клітинку з ключем, щоб вважалося що ключ у тебе?

Так.

3) Є обмеження на процесорний час?

Ні, але розраховуйте на 2-3 секунди на один хід максимум.

4) Для зменшення впливу випадковості, треба проходити декілька різних лабіринтів, а не один.

Дивись відповідь на запитання №1.

5) Початкова позиція в лабіринті однакова для всіх учасників?

Так.

6) Якщо просто проїхати по ключу без використання команди SCAN (тобто робот нічого не знає про ключ) чи означає це що ключ є у робота.

Так. Достатньо лише потрапити у клітинку з ключем.

7) Вихід з лабіринту завжди знаходиться по периметру чи може бути в будь-якій клітинці?

Теоретично може бути будь-де, навіть може існувати декілька виходів. Але тестовий лабіринт буде мати один вихід на периметрі.

8) Чи може один учасник надіслати декілька варіантів алгоритму?

Так, тільки будь ласка для кожного варіанту придумайте унікальну назву для поля name.

9) Що буде, коли алгоритм поверне назву неіснуючої команди, наприклад, return «Unknown»?

Система вважатиме це пропуском ходу (хід на місці). Не робіть так.

10) У який бік дивиться робот на початку проходження лабіринту?

Ця інформація недоступна роботу. Але всі роботи стартують в одній точці і дивляться в один бік.

11) Робот без попереднього сканування заїхав у клітинку з ключем. Може він якось про це дізнатися?

Ні. Але тепер він зможе вийти з лабіринту. Без ключа рух у напрямку виходу поверне негативний результат.

 

Якщо у Вас є запитання, пропозиції чи зауваження надсилайте їх мені електронною поштою: msenyk@malkosua.com

Успіхів Вам та натхнення!

01.07.2015

2 комментария на «JavaScript Challenge»

  1. Нужно ломать этот заговор молчания в комментариях :)
    Кто тут участвует помимо меня?

  2. Отправил свой вариант…

Добавить комментарий

Для отправки комментария вы должны авторизоваться.