Задание 3 - Задание на JS

Данная задача является задачей на комбинаторную оптимизацию. Исходя из условия задачи, получается, что задача NP-сложная, т.е. нет решения задачи (или я не знаю его) за полиноминальное время, поэтому для решения этой задачи я использовал метод ветвей и границ. Данный метод гарантированно позволяет найти самое оптимальное решение задачи, либо сообщит, что решений задачи нет, но работать он с реальными данными не будет (с тестовыми данными справляется на ура), т.к. решение задачи данным методом с более сложными условиями потребует слишком много вычислений.

В качестве ветвей, использовались различные времена запуска приборов, а в качестве границ можно использовать только суммарную мощность запущенных приборов в определенный час и допустимую суммарную мощность. Текущую стоимость работы в качестве границы использовать нельзя, т.к. нет гарантии, что ветвь с самой большой текущей стоимостью работы не окажется в конце самой дешевой. Я максимально посторался оптимизировать работу метода, насколько смог, но достичь производительности, которую можно использовать в боевых решениях этим методом у меня не получилось. Поэтому я добавил в решение второй метод "быстрый". Реальный дома и квартиры проектирются так, что даже если включить все приборы разом, то суммарная мощность приборов никогда не должна превышать допустимой мощности. Обычно допустимая мощность в несколько раз больше суммарной мощности всех приборов. Исходя из этого условия, можно попытаться решить задачу очень быстрым и простым способом, который не учитывает ограничение по суммарной мощности.

В результате у меня получилась библиотека power-optimizer, подключив которую, можно передав в нее в метод calculate объект с входными данными, получишь объект с результатом. Библиотека автоматически сначала попытается применить для решения задачи быстрый метод, а если его применить нельзя (дом спроектировал так, что включив все, в нем выбьет автоматы), то будет пытаться решить задачу методом ветвей и границ. Так же библиотека видет статистику по работе обоих методов. Для проверки работы библиотеки, я собрал маленькую CLI-утилиту, которая принимает файл с входными данными и сохраняет результат в выходные данные.

Запуск проекта

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

npm install
npm build
npm start

В результате в файле output.json сохранится решение задачи с тестовыми данными из задания.

Работа с тестовой утилитой

Для работы с тестовой утилитой нужно выполнить:

npm install
node dist/index.js

Утилита принимает следующие параметры:

• --input, -i - файл с входными данными (ОБЯЗАТЕЛЬНЫЙ);
• --output, -o - файл с выходными данными (ОБЯЗАТЕЛЬНЫЙ);
• --algorithm - алгоритм используемый для расчета: auto - выбор алгоритма автоматически (по-умолчанию), both - использование обоих алгоритмов, fast - использование только быстрого алгоритма, bnb - использование только алгоритма ветвей и границ;
• --print-statistics, -s - выводить статистику работы алгоритмов (по-умолчанию, включена).

Описание того, как сделан проект

Проект имеет следующие особенности:

1. проект полностью написан на TypeScript;
2. покрыт unit-тестами при помощи mocha и chai;
3. настроен автоматический анализ глубины покрытия тестами при помощи nyc;
4. настроен линтинг проекта при помощи tslint;
5. настроен автоматический запуск линтинга проекта перед коммитом за счет использования git-хуков при помощи prettier, tslint, husky и lint-staged;
6. из зависимостей у проекта только yargs для работы CLI-утилиты.