/fluffy-eureka

Third tasks for Yandex SHRI

Primary LanguageJavaScriptMIT LicenseMIT

Задание на JS - Реализовать алгоритм

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

На вход подаются данные о тарифах, электроприборах и их максимальной потребляемой мощности.

Тарифы — это периоды в сутках, для которых задана отдельная стоимость киловатт-часа.

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

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

При значении mode:

  • day период с 07:00 до 21:00.
  • night период с 21:00 до 07:00 следующего дня.
  • undefined период отсутствует, прибор может работать в любой промежуток времени.

Примеры входных и выходных данных находятся в ./test/data.

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

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

Мы будем оценивать реализацию функциональности по следующим критериям:

  • Правильность алгоритма на разнообразных входных данных.
  • Оформление кода.
  • Производительность.
  • Наличие и качество тестов.

Выполнение задания

1. Настройка окружения

Оформление кода

Для реализации единого оформления кода установил дополнительно пакеты:

для реализации автоматизированного приведения к единому стилю с помощью запуска Prettier в precommit hook.

Тесты

Для тестов решил использовать Jest, так как он является zero configuration, легок в использовании и имеет достаточный функционал без подключения дополнительных библиотек.

Структура

Все функции хранятся в файле index.js, основная функция называется getScheduleDevices.

Тесты хранятся в папке ./test и имеют следующую структуру:

  test/
  |__ data/
  |   |
  |   |__ input.json              // входные данные для основной функции
  |   |__ output.json             // выходные данные для основной функции
  |    ...
  |
  |__ someFunction/
  |   |__ data/
  |   |     |__ input.json        // входные данные для вспомогательной функции
  |   |     |__ output.json       // выходные данные для вспомогательной  функции
  |   |
  |   |__ someFunction.test.js    // файл с Jest тестом для вспомогательной функции
   ...
  |__ getScheduleDevices.test.js  // файл с Jest тестом для основной функции

Установка:

  npm install

Для того чтобы запустить тесты:

  npm test

Посмотреть покрытие кода тестами:

  npm run-script test-coverage

Авто запуск тестов при разработке:

  npm run-script dev

2. Комментарии по алгоритму

Алгоритм действий:

  1. Преобразуем диапазоны тарифов в массив, где каждому индексу соответствует конкретный час работы, и сдвигаем его так чтобы начало утреннего периода было в 0-м индексе. Сдвиг делается для удобства работы с диапазонами.
  2. Получаем массив сумм тарифов, sumRate[i] = sumRate[i-1] + rate[i], для удобства расчета тарифа в диапазоне. То есть, чтобы найти сумму тарифов на определенном отрезке понадобится: rangeRate = sumRate[range.finish] - sumRate[range.start];
  3. Сразу расставляем устройства которые работают круглосуточно и которые работают только в определенном периоде имея продолжительность равную длительности этого периода.
  4. Находим все возможные положения оставшихся устройств на временной шкале с их суммарным тарифом и хешируем их:
  • Положения ищутся исходя из продолжительности работы.
  • Если положения для определенной продолжительности работы были рассчитаны - второй раз расчёт не запускается.
  • К тому же если продолжительность работы больше 12 часов положения для устройсв можно не рассчитывать, если уже положения найдены для длительности равной 24 - duration. Так как оптимальное положение для продолжительности в 23 часа можно найти просто взяв самый  неоптимальный период для продолжительности в 1 час, и инвертировать период. (time1h.from = time23h.to; time1h.to = time23h.from;). Данный прием позволит не делать лишних вычислений, а так же более точно подбирать оптимальные значения для больших диапазонов не добавляя дополнительной логики работы с временными периодами.
  1. Сортируем оставшиеся устройства исходя из мощности, чтобы более выгодно разместить самые энергозатратные устройства.
  2. Расставляем устройства в расписание:
    1. Выбираем нужные позиции из Хеша(созданного в п. 4) позиций, учитывая мод и продолжительность.
    2. Сортируем возможные позиции по величине суммарного тарифа, от меньшего к большему, чтобы саме оптимальные положения оказались в начале массива.
    3. Берем первый элемент массива (самый оптимальный вариант положения) и проверяем хватает ли мощности для данного устройства в каждом часе на выбранном периоде.
      1. Если хватает - устанавливаем устройство в расписание.
      2. Если не хватает - переходим к следующему варианту.
    4. Если не возможно установить устройство - запускаем функцию которая ищет варианты перестановки устройств местами.
      1. Находим часы в которые не укладывается устройство
      2. Находим устройства которые можно подвинуть, исходя из высвобождаемой мощности
      3. Сортируем устройства которые хотим переставить по возрастанию мощности
      4. Проверяем можно ли переставить устройства, путем удаления из расписания и массива доступной мощности, устройства которое хотим сдвинуть, и запуская функцию расставления устройств, с приоритетом на установку устройства которое не удалось установить ранее.
        1. если устройства можно переставить то функция сделает это и обновит календарь
        2. если нет - выкинет ошибку
  3. Формируем ответ из state, убирая смещение времени которое было сделано в п.1

3. Итог

  • Реализован алгоритм поиска оптимального расположения для устройств.

  • Реализована проверка типов всех входных данных в распределенные на несколько функций, чтобы дополнительно не создавать циклы только для валидации данных

  • Написаны тесты на все функции, которые используются в данном алгоритме.

  • Реализованы проверки:

    • Корректного задания периодов
    • Проверка корректности мода
    • Возможности установки всех устройств имеющих продолжительность в "полный" период. (undefined = 24h, day - 14h, night - 10h)
    • Возможности установки всех устройств с продолжительностью в "неполные" периоды.

  • Покрытие кода тестами:

    test coverage