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

Rescue Operation — JavaScript Challenge

Микола Сеник

rescueСьогодні ти не програміст — ти в першу чергу рятівник. Люди потрапили у крижану пастку — їм потрібна твоя допомога. Від того, як ефективно ти зможеш розв’язати задачу, залежить людське життя.

Переможцю приз — 1000 грн.

Роботи надсилайте до 31 січня 2016.

Умова задачі

Зима. Величезне озеро покрите кригою. Багато рибалок розбрелися по всій поверхні і нічого не підозрюють. Раптово стає тепліше і крига починає танути. Треба рятувати людей.

Добрі новини:

  • рятувальна служба має достатньо вертольотів, щоб забрати усіх рибалок
  • кожен рибалка має мобільний телефон, тому GPS координати кожного відомі
  • ми можемо відправити кожному SMS з координатами вертольоту
  • всі вертольоти справні і мають однакову кількість посадкових місць

Погані новини:

  • лід тане швидко
  • до озера далеко
  • вертольоти зможуть зробити лише один політ

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

Технічні умови

Вхідні данні — об’єкт наступної структури:

{
  seats: M,
  people:[
    {x: X1, y: Y1},
    {x: X2, y: Y2},
    … ,
    {x: Xn, y: Yn}
  ]
}

де

  • seats — кількість місць у вертольоті
  • people — масив об’єктів з координатами кожної людини

Наприклад, для 3-х рибалок за координатами 50:70, 12:11, 73:45 та вертольоту на 5-ть посадкових місць — вхідні дані будуть такими:

{seats:5, people:[{x:50, y:70}, {x:12, y:11}, {x:73, y:45}]}

Результатом роботи програми має бути масив такої структури:

[
  {x: X1, y: Y1, people: [index0, index1, … , indexN-1]},
  {x: X2, y: Y2, people: [index0, index1, … , indexN-1]},
  … ,
  {x: Xm, y: Ym, people: [index0, index1, … , indexN-1]}
]

Кожен елемент масиву — це дані про один рятувальний вертоліт:

  • x та y — координати, де вертоліт забирає людей
  • people — масив з індексами тих людей, що летітимуть цим вертольотом

Відповідь може бути такою:

[{x:35, y: 40, people:[0, 1, 2]}]

Всі числа у вхідних та вихідних даних (координати, кількість місць) мають бути цілими та позитивними. Вважаємо озеро квадратним 10000 х 10000.

Особливості задачі

Уявімо, що в нас лише один вертоліт та троє рибалок. Їх координати ви можете побачити на малюнку:

rescue_sample

Найбільшою відстанню вважається шлях, який пройде рибалка з координатами (140; 140) до вертольоту (500; 550). Тобто:

distance

Якщо вертольотів кілька, то вам треба розподілити їх між рибалками. Подивіться на 2 наступні малюнки. Кількість рибалок та вертольотів однакова, але перший результат значно краще ніж другий.

Оптимальне рішення

optimal_route

Неоптимальне рішення

not_optimal_route

Пунктирною лінією позначений найдовший шлях. Саме це значення і буде визначати якість вашого алгоритму.

Правила участі у конкурсі

До участі у конкурсі кожен учасник може надіслати лише одну роботу. Вона має бути написана мовою JavaScript. Оформлена у вигляді анонімної функції такого виду:

function(input) {
  // your logic
  return output;
}

Свої роботи надсилайте на електрону пошту:
msenyk@corevalue.net

Граничний термій прийому робіт — 31 січня 2016 року.

Переможець отримає 1000 грн.

Як буде визначений переможець

Алгоритм має пройти через послідовність тестів (різних вхідних даних). Тест вважається задовільним, якщо виконані наступні умови:

  • всі люди врятовані
  • ніхто не потрапив одночасно на 2 і більше вертольоти
  • кількість вертольотів оптимальна — дорівнює кількості людей поділеної на кількість місць у вертольоті. Наприклад, для 100 чоловік при кількості посадкових місць 5 — вертольотів має бути 20. Дробові відповіді слід округлити до наступного цілого числа. Наприклад, для 101 чоловіка — відповідь буде 21 вертоліт.
  • координати вертольотів цілі позитивні числа. Якщо за вашим алгоритмом оптимальним пунктом призначення є {x:45.344, y: 76.9} ви маєте повернути округлений результат — {x:45, y:77}.
  • алгоритм закінчив роботу менше ніж за 10 секунд

Результат тесту — це найбільша відстань, яку людина пройшла від початкової точки до вертольоту. Ця відстань буде округлена до 3 знаків після коми.
Іншими словами будемо вважати, що всі вертольоти долітають до своїх пунктів призначення одночасно. Тому ми беремо до уваги лише відстань, яку потрібно пройти рибалкам пішки.

Результати всіх тестів буде зведено у таблицю:

results_table

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

  • за кращій результат у тесті — 10 балів
  • якщо декілька учасників отримали однаковий результат, то кількість балів зменшується пропорційно кількості. Наприклад, для двох кращій результатів не 10 балів, а 9 кожному.
  • якщо тест не пройдено — 0 балів

Допоміжні інструменти

Перш ніж надсилати свої роботи скористуйтесь будь ласка тестовим майданчиком:
https://jsfiddle.net/MykolaSenyk/ksc247a5/8/

Вам доступні 5 функції:

  • buildInputData(seats, peopleCount) — побудувати тестові дані
  • buildOutputData(inputData) — приклад відповіді по тестовим даним
  • checkResult(inputData, outputData) — перевіряє чи співвідносяться вхідні та вихідні дані. Обов’язково перевіряйте відповідь вашого алгоритму цією функцією.
  • calculateResult(inputData, outputData) — повертає максимальну відстань
  • drawRoutes(inputData, outputData) — візуалізація маршрутів, рибалок та вертольотів

Питання та відповіді

1) Зачем? Координаты всегда числа не целые

На квадратному озері використовується спрощена система координат. Один його кут має координати (0, 0) протилежний (10000, 10000). Навігаційна система має точність 1 метр.

2) it should be as Math.ceil(count of people / seats). ie around to the biggest part

Відповідність вертольотів (H) та рибалок (P). Кількість вертольотів завжди ціле число. Щоб його отримати, достатньо поділити кількість рибалок на число посадкових місць (M) і округлити результат до більшого цілого числа. Наприклад, P = 10, M = 3, H = 10/3 = 3.333 → 4.

3) Слишком много допущений в задаче. Толи без них задача будет слишком сложной… но если дано 3 человека между которыми по 10 км и один вертолёт на 5 человек то конечно вертолёт будет летать к людям, а не люди идти по ~5,8км

Так, задача навмисно спрощена. Не треба враховувати відстань від озера до бази МНС, швидкість польоту вертольота, швидкість пересування рибалок по кризі, час посадки однієї людини у вертоліт тощо.

4) Или если есть 3 групы людей между которыми по 10км, в которых 2, 3, и 4 человека соответственно. и вертолёты на 3 человека, то оптимально использовать 4 вертолёта если их число всёравно не ограничено :)

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

5) Чи може вертоліт “сідати” прямо на рибалку?

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

6) Існує обмеження у максимальній кількості рибалок?

Будемо вважати, що рибалок не більше 1000.

 

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

29.12.2015

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

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