Задание на JS для Школы Разработки Интерфейсов

Основная функция находится в корне, в файле index.js и уже экспортирована.
Как обычно:

npm i
npm run test

Table of contents

Формулировка задания
Использованные сторонние пакеты
Основной алгоритм
Алгоритм проверки на наличие тупиковых состояний
Верификация ввода
Тестирование
Подробное описание основных модулей

Формулировка задания

Цель задания — реализовать алгоритм работы «умного дома», который будет производить расчёт стоимости потребляемой электроэнергии в день и возвращать рекомендованное расписание использования электроприборов, оптимизируя денежные затраты.
На вход подаются данные о тарифах, электроприборах и их максимальной потребляемой мощности.
Тарифы — это периоды в сутках, для которых задана отдельная стоимость киловатт-часа.
Приборы — это набор подключенных к «умному дому» электроприборов, для которых известна потребляемая мощность, длительность цикла работы, а также время дня, когда они используется. Каждый прибор должен отработать один цикл в сутки. Максимально потребляемая мощность указывается в ватт-часах.
На выходе должно получиться суточное расписание включения электроприборов. Каждый прибор за сутки должен отработать один цикл, а суммарная стоимость потраченной электроэнергии должна быть минимальной.
При значении mode — day период с 07:00 до 21:00.
При значении mode — night период с 21:00 до 07:00 следующего дня.
При значении mode — undefined период отсутствует, прибор может работать в любой промежуток времени.
Примеры входных и выходных данных.

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

Сторонние пакеты

Jest

Тестовый фреймворк. Задействован с целью упростить процесс тестирования и не писать самостоятельно тестраннер с обработкой ошибок, выбрасываемых assert'ом при тестировании нативными средствами. Также возможность собирать coverage весьма удобна при отладке и отслеживании лишнего кода. Почему именно он? Потому что zero-configuration, удобный API и я с ним уже работал раньше.

fs-extra

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

Основной алгоритм

В упрощенном виде алгоритм можно свести к следующему:

1. Устройства сортируются по приоритету [1]
2. Каждому устройству вычисляется наиболее выгодная позиция [2]
3. Производится проверка на наличие тупикового состояния [3] при размещении устройства на этой позиции
4. Если проверка прошла успешно, то устройство размещается, если нет - то то же самое повторяется для следующей по выгодности позиции
5. Повторяем пока не будут размещены все устройства или пока для одного из устройств не закончатся возможные позиции для размещения

подробный алгоритм и разбор кода можно найти в последнем разделе

[1] Приоритет устройств

Вычисляется по следующим првилам

1. Устройство с mode ВСЕГДА приоритетнее устройства без mode
2. Устройство с большим показателем duration всегда приоритетнее устройства с меньшимм показателем duration (кроме случая из п.1)
3. При прочих равных устройство с большим показателем power приоритетнее устройства с меньшим показателем power

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

[2] Наиболие выгодная позиция

Такая позиция, на которой устройство будет размещаться преимущественно на часах с минимальным значением тарифа. Вычисляется следующим образом:

1. Берем один из часов, зная duration, находим сумму тарифа на каждом часу на протяжении duration, начиная с указанного часа
2. Часы с получившимся значениями сортируем по возрастанию (первый - наиболее выгодный, последний - наименее выгодный)

[3] Тупиковое состояние

Это такое состояние, при котором невозможно разместить в расписании все оставшиеся устройства так, чтобы каждое устройство отработало полный цикл.

Алгоритм проверки на наличие тупиковых состояний

Собственно, алгоритм проверки на наличие тупиковых состояний можно упростить до следующего:

1. Создаем копию расписания и дальше работаем с ней
2. Размещаем устройство на заданной позиции
3. Пытаемся максимально компактно разместить все остальные устройства
4. Возвращаем ответ получилось ли разместить устройства, если получилось, то указанное устройство будет размещено на указанной позиции, если нет, то размещение будет отклонено

разбор кода можно найти в последнем разделе

Как и в основном алгоритме, в первую очередь размещаются устройства зависимые от времени суток, но процесс более комплексный. В первую очередь выделяются устройства, зависимые от времени суток и разделяются на дневные и ночные. После этого обе эти группы сортируются по убыванию duration и каждая из них размещается в расписании по модифицированному алгоритму floor ceiling decreasing. Причем это делается так, чтоб между дневными и ночными устройствами оставалось как можно больше непрерывного свободного места. Модификация алгоритма заключается в том, что на каждой итерации производится мини-проверка на потенциальные тупики: мы находим независимое от времени суток устройство с самым большим показателем duration среди неразмещенных и проверяем будет ли возможность его разместить после этой итерации, если нет, то на этой итерации мы разместим его, а не устройство зависимое от времени суток. В остальном алгоритм работает как обычный floor ceiling decreasing, за исключением того, что он по сути выполняется в двух экземплярах -- для дневных и ночных устройств.
После того как мы разместили зависимые от времени устройства (либо у нас больше нет возможности создавать новые уровни), мы размещаем оставшиеся устройства с помощью модифицированного варианта алгоритма best fit decreasing: нет никаких уровней, устройства приоретизируются уже описанным способом, каждое устройство размещается туда, где оно сможет забрать наибольшую долю от оставшейся энергии.

Верификация ввода

Верификация ввода проводится на двух этапах.

1. Явная верификация ввода с помощью специально написанного модуля.
2. На этапе назначения каждому часу тарифа, согласно введеным данным. Если было проитерировано ровно 24 часа, значит у нас заданы все нужные тарифы, если нет, значит во вводе либо были не указаны тарифы для всех часов, либо у нас есть конфликтующие тарифы.

(рассмотрим начиная с последнего)

Верификация на этапе назначения тарифов

./models/schedule-model.js:22

/**
 * Назначает часам оставшуюся мощность и тариф, который на них действует
 * @param {Array} rates массив тарифов
 * @param {Number} maxPower максимальная мощность
*/
_assignRatesAndPower(rates, maxPower) {
    let ratesPlaced = 0; // считаем сколько раз был назначен тариф для часа
    rates.map(rate => { // для каждого тарифа итерируем часы и на каждый назначаем тариф
        const { from } = rate;
        const to = normalizeHours(rate.to - 1);
        this.iterateHours({from, to}, h => {
            h.rate = rate;
            h.remainingPower = maxPower;
            ratesPlaced++;
        });
    });
    // если мы назначили тарифов больше или меньше, чем у нас есть часов, значит ввод был неверный
    if (ratesPlaced!=24) throw Error('Incorrect input, should be exactly one rate per hour.');
}

Явная верификация

Для явной верификации была написана функция, выполняющая поверхностную (нерекурсивную) проверку на соответствие объекта объекту-дескриптору. Чтоб много не расписывать, вот пример работы взятый из тестов:

./verify-input/verify-object.spec.js:0

const verifyObject = require('./verify-object');
const { all, one } = verifyObject;

test('successful verification and wrong arguments', () => {
    
    const descriptor = {
        arrayField: Array,
        objectField: Object,
        numberField: Number,
        stringField: String,
        booleanField: Boolean,
        symbolField: Symbol,
        functionField: Function,
        NaNField: NaN,
        nullField: null,
        undefinedField: undefined,
        customCheckField: a => a >= 4,
        numberOrString1: one(Number, String),
        numberOrString2: one(Number, String),
        nonEmptyArray: all(Array, a => !!a.length)
    }

    const object = {
        arrayField: [1, 2, 3],
        objectField: {},
        numberField: 5,
        stringField: 'this is string',
        booleanField: true,
        symbolField: Symbol(),
        functionField: function func() {
            return 'i am function';
        },
        NaNField: NaN,
        nullField: null,
        customCheckField: 4,
        numberOrString1: 'two',
        numberOrString2: 2,
        nonEmptyArray: [1, 2, 3]
    }
    
    expect(verifyObject(object, descriptor)).toBe(true);
    expect(verifyObject(null, descriptor)).toBe(false);
});

Принцип работы

Дескриптор должен содержать поля, соответствующие полям ожидаемого объекта, но в каждом поле вместо самого значения указывается либо тип значения (на данный момент можно указывать Array, Object, Number, String, Boolean, Symbol, Function, NaN, null, undefined, причем Number не соответствует NaN, а null не соответствует Object), либо функция, которая должна быть использована для проверки. Методы All и One предназначены для объединения нескольких условий и работают как логические И и ИЛИ соответственно. Сам алгоритм весьма прост:

0 У нас есть несколько заготовленных функций для проверки.
1 Итерируем через поля дескриптора и проверяемого объекта.
2 Если значение в поле дескриптора является ключем, то проверяем значение в таком же поле объекта с помощью соответствующей ему функции, если нет, то значение в дескрипторе это функция, которую используем для проверки.

С исходным кодом верификатора можно ознакомиться в ./verify-input.
Соответственно, при несоответствии объекта дескриптору, программа будет выбрасывать ошибку (фрагмент): ./verify-input/index.js:15

let checkInput = verifyObject(input, {
        devices: Array,
        rates: Array,
        maxPower: Number
    });
    if (!checkInput) {
        throw Error('Incorrect input.')
    }

Тестирование

Тесты писались таким образом, чтобы была возможность проверить как можно большее вариантов различных выборок. Применялись как статичные данные, так и случайно сгенерированные. Все основные тесты можно посмотреть в ./index.spec.js и остальные тесты в файлах, оканчивающихся на .spec.js.

Статичные тесты

Тестирование с оригинальными данными, предоставленными в задании

./index.spec.js:10

test('original.json', () => {
        expect(createSchedule(require('./data/original.json')).consumedEnergy).toEqual({
            value: 38.939,
            devices: {
                '02DDD23A85DADDD71198305330CC386D': 5.398,
                '1E6276CC231716FE8EE8BC908486D41E': 5.398,
                'F972B82BA56A70CC579945773B6866FB': 5.1015,
                '7D9DC84AD110500D284B33C82FE6E85E': 1.5215,
                'C515D887EDBBE669B2FDAC62F571E9E9': 21.52
            }
        });
    });

Тестирование с крайними случаями (неверный ввод и отсутствие устройств)

./index.spec.js:23

test('no-devices.json', () => {
    // нет устройств, не должно быть никаких проблем, должно просто сформировать пустое расписание
    expect(createSchedule(require('./data/no-devices.json')).consumedEnergy).toEqual({
        value: 0,
        devices: { }
    });
});

const wrongRateInput = [
    'conflicting-rates.json',
    'not-enough-rates.json'
].map(filename => {
    const path = './data/' + filename;
    const input = require(path);
    // при конфликтующих тарифах или их недостатке должна быть одна и та же ошибка
    test(filename, () => {
        expect(() => createSchedule(input)).toThrowError('Incorrect input, should be exactly one rate per hour.');
    });
})

Тестирование со случайными данными

Для тестирования со случайными данными был создан отдельный модуль, который генерирует случайные, но корректные данные, причем таким образом, что при размещении всех устройств из сгенерированной выборки, на каждом часу не останется свободной энергии. То есть, всё тестирование производится "на пределе". К сожалению, не удалось сделать так, чтоб программа работала в 100% случаев, но в большинстве случаев (>80%) всё же все устройства будут размещены, на обычных выборках, схожих с оригинальной (где не так много устройств и они не занимают всё место в расписании), проблем не будет. Генератор случайных данных предусматривает возможность генерации выборок как без устройств, зависимых от времени (с такими практически никогда не бывает проблем), так и с определенной долей устройств, зависимых от него (большинство проблем именно на таких выборках). Ознакомиться с генератором данных можно в ./testing-utils/input-generator.
Само тестирование с комментариями:
./index.spec.js:63

describe('monkey testing', () => {
    // очищаем папку, в которой хранятся выборки, на которых выскочила ошибка
    fsExtra.emptyDirSync('./output/failed_tests'); 
    // генерируем 99 различных выборок
    const differentInputs = [
        // 33 выборки без устройств зависимых от времени суток
        generateInput(33, 4, 0),
        // 33 выборки, где половина устройств зависит от времени суток
        generateInput(33, 4, 0.5),
        // 33 выборки, где все устройства зависят от времени суток
        generateInput(33, 4, 1)
    ].map(inputs => {
        inputs.map(inputWrapper => {
            // разворачиваем обертку выборки для получения данных о ней
            const { name, input, modeP } = inputWrapper;
            // конвертируем данные в JSON для возможности последующей записи в файл
            const log = JSON.stringify(input, null, 2);
            test(name, () => { // присваиваем тесту имя выборки
                try {
                    const schedule = createSchedule(input);
                    // если не было ошибок, то в выводе должно быть столько же устройств, сколько было при вводе
                    expect(Object.keys(schedule.consumedEnergy.devices).length).toBe(input.devices.length);
                } catch(e) {
                    // если не удалось разместить устройства в выборке, то сохраним её
                    Promise.resolve()
                    .then(() => fsExtra.ensureDir(`./output/failed_tests/mp${modeP}`))
                    .then(() => fs.appendFile(`./output/failed_tests/mp${modeP}/${name}.json`, log, e => { if (e) { console.log(e.message) } }))
                    .catch(e => console.log(e.message));
                    // если и была ошибка, то она должна быть связана с невозможностью разместить устройства
                    expect(e.message).toBe('Impossible to place all devices.');
                }
            });
        });
    });
});

Подробное описание основных модулей

Модели
Основная логика

Модели

Device
Hour
DayModel
ScheduleModel

Device ./models/device-model.js

Класс устройства, содержит атрибуты и методы для манипулирования устройствами в расписании.

Конструктор

new Device(deviceData, environment);

• deviceData -- оригинальный объект устройства из входных данных
• environment -- ссылка на окружение, в котором будет располагаться инстанс класса (ScheduleBuilder или VirtualScheduleBuilder)

.id, .name, .power, .duration, .mode

Полностью повторяют данные из deviceData

.placed

Объект содержащий информацию о расположении устройства в расписании.

• .placed.is -- Boolean факт размещения устройства. true - размещено, false - не размещено
• .placed.start -- Number номер часа, в котором устройство начнет работать
• .placed.end -- Number номер последнего часа работы устройства (включительно, то есть, если устройство работает с 1 до 3, то тут будет 2)

.bestHours

Массив инстансов класса Hour, содержит все часы, в которые может быть размещено устройство, начиная с самого экономичного варианта, заканчивая самым неэкономичным

.cloned

boolean, указывает является ли это устройство копией.

.checkBasicSafety(hourNumber)

Проверяет возможность размещения устройства на указанном часу. В соответствии с duration проверяется нужное количество часов следующих за указанным часом, у каждого часа должен быть соответствующий mode и достаточное количество оставшейся энергии. Возвращает boolean.

.place(hourNumber)

Размещает устройство на заданном часу. В соответствии с duration, начиная от указанного часа, записывает в массив устройств каждого часа себя, а также убирает себя из массива неразмещенных устройств.

.remove([recentlyPlaced])

То же самое, что place, но в обратном порядке. Убирает устройство с часа на котором оно расположено. Добавляет его обратно в массив неразмещенных устройств. Если устройство размещено было только что (опциональный аргумент, по умолчанию true), то устройство добавит себя в начало массива неразмещенных устройств, если нет, то ещё и отсортирует его по новой.

.setHoursPriority()

Находит все часы, на которых можно разместить устройство. Сортирует их от наиболее выгодных к наименее выгодным. Сохраняет в атрибуте .bestHours.

.setHoursPriorityNoRates()

То же самое, что setHoursPriority, только вместо учитывания тарифов и сортировки часов по более выгодным, учитывает где устройство займет наибольшую долю от оставшейся энергии и в соответствии с этим сортирует. Сохраняет в атрибуте .bestHoursNoRates.

Hour ./models/hour-model.js

Модель часа, содержит атрибуты и методы для манипулирования часами в расписании. Для составления расписания требуется 24 инстанса класса Hour.

Конструктор

new Hour(number, mode, environment);

• number -- какой час в суточном цикле будет представлять создаваемый инстанс, устанавливает атрибут number
• mode -- к какому времени суток будет отнесен созданный час, устанавливает атрибут mode
• environment -- окружение, в котором будет этот инстанс располагаться (ScheduleBuilder или VirtualScheduleBuilder), устанавливает атрибут environment

get rate(), set rate()

Каждому часу можно устанавливать тариф, действующий на нем. Ссылка на объект тарифа хранится в в атрибуте ._hourRate. Сеттер устанавливает значение этого атрибута, геттер возвращает только атрибут value из него.

setEfficency(duration, value), getEfficency(device)

Каждому часу можно установить значение того, насколько экономично будет расположить устройство с определенным значением duration на нем. Меньше - лучше. setEfficency устанавливает атрибут efficency, getEfficency возвращает соответствующий устройству показатель.

getCombinedPower(duration)

Возвращает суммарную оставшуюся энергию начиная с этого часа и на протяжении duration.

DayModel ./models/day-model.js

Моделирует суточный цикл. Содержит в себе 24 инстанса класса Hour и методы для итерации через них.
Основная задача -- предоставить возможность непрерывно итерировать через часы, то есть, если мы хотим проитерировать от 22 часа до 1, у нас должна быть такая возможность, иначе не получится размещать устройства на стыке суток.

Конструктор

new DayModel(dayStart, nightStart)

• dayStart -- час, с которого начинается день
• nightStart -- час, с которого начинается ночь

.hours

Массив инстансов класса Hour, наш суточный цикл

_addHours()

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

* _iterateFromTo(from, to)

Функция-генератор, итерирует от заданного часа до заданного часа включительно. То есть, если указать в аргументах (23, 3), то будут выведены часы 23, 0, 1, 2, 3. Не предназначена для вызова извне.

• from -- номер часа с которого итерировать
• to -- номер часа до которого итерировать

* _iterateTimes(from, times)

Функция-генератор, аналогична предыдущей, только итерирует не до заданного часа, а указанное количество раз. То есть, если указать в аргументах (23, 3), будут выведены часы 23, 0, 1. Также не предназначена для вызова извне.

• from -- номер часа с которого итерировать
• times -- количество итераций

iterateHours({ from, [to|times]}, cb)

Синтаксический сахар, объединяет предыдущие два итератора и включает в себя проверки на правильность переданных аргументов, предназаначена для вызова извне. Принимает на вход час с которого итерировать и час до которого итерировать | количество итераций, а также коллбэк, который будет вызван на каждой итерации. Если коллбэк возвращает truthy значение, то итерация прекращается.
Пример использования:

dayModelInstance.iterateHours({ from: 23, to: 3 }, h => console.log(h.number)) // -> 23, 0, 1, 2, 3
dayModelInstance.iterateHours({ from: 23, times: 3 }, h => console.log(h.number)) // -> 23, 0, 1

ScheduleModel ./models/schedule-model.js

Наследуется от класса DayModel и содержит вспомогательную логику для манипулирования расписанием.

Конструктор

new ScheduleModel(inputs, dayStart, nightStart);

• inputs -- исходные данные, в соответствии с сигнатурой указанной в задании
• dayStart -- время начала дня
• nightStart -- время начала ночи

.maxPower

Максимальная мощность, заданная во входных данных.

.devices

Массив инстансов класса Device

_assignRatesAndPower(rates, maxPower)

Метод предназначен для вызова из дочерних классов. Назначает каждому часу соответствующий тариф и оставшуюся энергию. А также выбрасывает ошибку при конфликтующих или недостающих тарифах.

• rates -- массив тарифов
• maxPower -- максимальная энергия

addDevices(devices)

Заполняет атрибут .devices заданными устройствами, попутно конвертируя их в инстансы класса Device.

setHoursEfficency()

Устанавливает для каждого часа стоимость размещения на нем устройства с определенным показателем duration. (см. setEfficency/getEfficency в Hour).

renderResults()

Формирует и возвращает объект расписания, оформленный в соответствии с сигнатурой указанной в задании.

Модули с основной логикой

Тут всё будет сильно подробнее.
ScheduleBuilder
VirtualScheduleBuilder
Приоретизация устройств

ScheduleBuilder ./schedule-builder.js

Конструктор
.lastSafeBuild, .firstFailedBuild, .lastFailedBuild
placeDevices()
tryToPlaceDevice(device)
deadlockCheck(device,hourNumber)

Конструктор

new ScheduleBuilder(input, dayStart, nightStart);

• inputs -- входные данные в соответствии с сигнатурой, указанной в задании
• dayStart -- час в который начинается день
• nightStart -- час, в который начинается ночь При вызове конструктор в первую очередь проверяет правильность входных данных, затем вызывает методы _assignRatesAndPower, addDevices и setHoursEfficency, унаследованные от ScheduleModel. После этого создает массив неразмещенных устройств .notPlacedDevices. Таким образом, мы готовы к составлению расписания.

.lastSafeBuild, .firstFailedBuild, .lastFailedBuild

Инстансы VirtualScheduleBuilder.
lastSafeBuild -- последний инстанс VirtualScheduleBuilder, в котором удалось разместить все устройства
firstFailedBuild, lastFailedBuild -- первый и последние инстансы VirtualScheduleBuilder, в которых не получилось разместить все устройства, требуются только для отладки

placeDevices()

Основная логика для размещения устройств.
Подробный алгоритм:

1. Сортируем устройства по приоритету.
2. Итерируем через все устройства пока у нас есть неразмещенные:
   2.1) Пробуем разместить устройство.
   2.2) Если получилось, то переходим к следующему.
   2.2) Если не получилось, то проверяем получалось ли у нас разместить какое-то устройство на одной из прошлых итераций.
   2.2.1) Если получалось, то рендерим результаты из последнего успешного инстанса VirtualScheduleBuilder, где удалось разместить устройства.
   2.3) Проверяем пробовали ли мы альтернативную сортировку.
   2.3.1) Если ещё не пробовали, то применяем альтернативную сортировку и начинаем цикл заново.
   2.4) Проверяем попробовали ли мы уже начать с каждого устройства.
   2.4.1) Если пробовали, значит выбрасываем ошибку.
   2.4.1) Если не пробовали, значит переходим к следующему
3. Рендерим результаты и возвращаем их.

В коде:
./schedule-builder.js:30

/**
     * Размещает устройства и возвращает объект с сигнатурой, указанной в задании
     * @returns {Object}
     */
    placeDevices() {
        // Сортировка устройств по приоритету
        this.devices = this.devices.sort(sortDevices.byPriority); 
        // Копируем себе устройства, так как возможно их порядок придется изменить и мы не хотим мутировать основной массив
        let devices = this.devices.slice(0); 
        // Первая проверка на наличие тупиковых состояний, чтоб иметь дополнительный фоллбэк в lastSafeBuild
        this.deadlockCheck(); 
        
        let i = 0;
        let triedToStartFromEveryDevice = false;
        let triedPowerBias = false;
        // итерируем через все устройства пока у нас есть неразмещенные
        while(this.notPlacedDevices.length) {
            const device = devices[i];
            // пробуем разместить устройство
            let success = this.tryToPlaceDevice(device); 
            // если получилось, то продолжаем дальше итерировать через устройства
            if (success) {
                // мы могли начать размещать не с первого (будет ниже), поэтому i будет циклическим
                i = i + 1 == devices.length ? 
                0 : 
                i + 1 ;
                continue; 
            }
            // если не получилось разместить устройство, то проверяем получалось ли разместить что-то на прошлой итерации
            if (this.lastSafeBuild !== null) { 
                // если получалось, то рендерим данные из последнего успешного инстанса VirtualScheduleBuilder и завершаемся
                return this.lastSafeBuild.renderResults();
            }
            // если не было размещения на прошлой итерации, то проверяем пробовали ли мы отсортировать устройства альтернативным способом
            if (!triedPowerBias) {
                // если нет, то сортируем наши устройства альтернативным способом и начинаем с первого устройства
                // (добавление этого условия помогло избавиться от сильных проседаний производительности на определенных выборках)
                devices = devices.sort(sortDevices.byPriorityPowerBias);
                i = 0;
                triedPowerBias = true;
                continue;
            }
            // если мы уже пробовали альтернативную сортировку, то просто пробуем начать с каждого устройства
            if (!triedToStartFromEveryDevice) {
                i = i + 1 == devices.length ?
                ~(triedToStartFromEveryDevice = true) && 0 :
                i + 1 ;
                continue;
            }
            // если мы пробовали начать с каждого устройства и это не дало результатов, значит скорее всего устройства нельзя разместить, выбрасываем ошибку
            throw Error('Impossible to place all devices.');
        }
        // если ошибок не было и мы успешно прошли до конца цикла (не осталось неразмещенных устройств), значит выводим результаты
        return this.renderResults();
    }

tryToPlaceDevice(device)

Предпринять попытку размещения устройства.

• device -- объект-инстанс класса Device Алгоритм:

1. Если устройство уже размещено, то возвращаем true.
2. Приоретизируем часы для устройства.
3. Итерируем через возможные часы пока они не кончатся или пока не будут размещены устройства:
   3.1) Проверяем на наличие тупикового состояния при размещениии устройства на данном часу.
   3.2) Если присутствует тупиковое состояние, то переходим к следующему часу.
   3.2) Если тупикового состояния не появилось, значит размещаем устройства и возвращаем true.
4. Если мы так и не разместили устройство, проитерировав через все возможные часы, то возвращаем false.

В коде:
./schedule-builder.js:71

/**
 * Предпринимает попытку размещения устройства и возвращает факт успеха
 * @param {Object} device объект устройства
 * @returns {Boolean}
 */
tryToPlaceDevice(device) {
    // Если устройство уже размещено, то возвращаем true
    if (device.placed.is) { return true; }
    // Приоретизируем часы для устройства
    device.setHoursPriority();
    // Итерируем через возможные часы пока они не кончатся или пока не будут размещены устройства:
    while (device.bestHours.length && !device.placed.is) {
        // находим час
        const hour = device.bestHours.shift();
        // Проверяем на наличие тупикового состояния при размещениии устройства на данном часу
        const isSafe = this.deadlockCheck(device, hour.number);
        // Если присутствует тупиковое состояние, то переходим к следующему часу
        if (!isSafe) { continue; }
        // Если тупикового состояния не появилось, значит размещаем устройства и возвращаем true
        device.place(hour.number);
        return true;
    }
    // Если мы так и не разместили устройство, проитерировав через все возможные часы, то возвращаем false
    return false;
}

deadlockCheck(device, hourNumber)

Проверяет на наличие тупикового состояния в случае размещения устройства на данном часу.

• device -- объект-инстанс класса Device
• hourNumber -- номер часа, на котором собираемся произвести размещение
  Алгоритм:

1. Создаем новый инстанс VirtualScheduleBuilder, передав в его конструктор текущее окружение (this)
2. Пробуем разместить устройства внутри VirtualScheduleBuilder и узнаем о наличии или отсутствии тупикового состояния.
3. Сохраняем инстанс в lastSafeBuild/lastFailedBuild/firstFailedBuild в зависимости от результата
4. Возвращаем результат

В коде:
./schedule-builder:92

/**
 * Проверка на наличие тупиковых состояний путем создания виртуального расписания и размещения в нем устройств
 * @param {[Object]} device устройство, которое мы собираемся разместить
 * @param {[Number]} hourNumber час, на котором мы его собираемся разместить
 */
deadlockCheck(device, hourNumber) {
    // Создаем новый инстанс VirtualScheduleBuilder, передав в его конструктор текущее окружение (this)
    const virtualBuilder = new VirtualScheduleBuilder(this);
    // Пробуем разместить устройства внутри VirtualScheduleBuilder
    virtualBuilder.placeDevices(device, hourNumber);
    // Проверяем на наличие тупикового состояния
    const isSafe = virtualBuilder.deadlockState === false;
    // Если нет тупикового состояния
    if (isSafe) {
        // Сохраняем lastSafeBuild
        this.lastSafeBuild = virtualBuilder;
    // если есть
    } else {
        // Сохраняем lastFailedBuild и опционально firstFailedBuild
        this.firstFailedBuild = this.firstFailedBuild === null ? this.firstFailedBuild = virtualBuilder : this.firstFailedBuild;
        this.lastFailedBuild = virtualBuilder;
    }
    // Возвращаем результат
    return isSafe;
}

VirtualScheduleBuilder ./virtual-schedule-builder.js

Виртуальное расписание. Также содержит атрибуты и методы для размещения устройств, как и ScheduleBuilder. Отличие заключается в том, что методы тут направлены не на размещение устройств максимально дешевым способом, а на размещение их максимально компактным способом, так, чтоб удалось разместить как можно больше устройств.
Конструктор
placeDevices(device, hourNumber)
floorCeilDayNight()
createInitialLevel(mode)
createNextLevel({ floor, ceiling, devices })
placeOnFloor(device,floor)
placeOnCeiling(device,ceiling)
floorCeilSafetyMeasures(placedDevice,placedHourNumber)
bestFit()

Конструктор

new VirtualScheduleBuilder(parent);

• parent -- объект-инстанс ScheduleBuilder, из которого нам нужно скопировать данные Собственно, конструктор воссоздает то же состояение, которое в parent. При этом все часы заменяются на копии часов и все устройства заменяются на клоны устройств, дабы избежать мутации этих объектов внутри ScheduleBuilder.

placeDevices([device,hourNumber])

• device -- устройство, которое проверяем
• hourNumber -- номер часа, на которое основной составитель расписания хочет его поставить

Алгоритм:

1. Размещаем копию переданного в аргумент устройства на указанном часу
2. Размещаем устройства, зависимые от времени суток по модифицированному алгоритму Floor Ceiling Decreasing
3. Размещаем оставшиеся устройства с помощью безуровневой версии алгоритма Best Fit Decreasing
4. Проверяем удалось ли разместить устройства и выставляем соответствующее состояние атрибута deadlockState

В коде:
./virtual-schedule-builder.js:34

/**
 * Предпринимает попытку размещения устройств
 * @param {Object} device устройство, которое проверяем
 * @param {Number} hourNumber номер часа на котором мы его проверяем
 */
placeDevices(device, hourNumber) {
    if (device) {
        // находим клон размещаемого устройства
        device = this.devices.find(d => d.original === device); 
        // проверяем возможность размещения как таковую
        if (!device.checkBasicSafety(hourNumber)) { 
            this.deadlockState = true;
            return this.deadlockState;
        }
        // размещаем устройство
        device.place(hourNumber); 
    }
    // размещаем устройства, зависимые от времени суток по алгоритму floor-ceiling
    this.floorCeilDayNight(); 
    // размещаем оставшиеся устройства по немного измененному алгоритму best fit decreasing
    this.bestFit(); 
    // если все устройства размещены
    if (!this.notPlacedDevices.length) { 
        // сообщаем об отсутствии тупикового состояния
        this.deadlockState = false; 
        return this.deadlockState;
    }
    // если остались неразмещенные устройства, сообщаем о наличии тупикового состояния
    this.deadlockState = true; 
    return this.deadlockState;
}

floorCeilDayNight()

Размещает устройства, зависимые от времени суток, по модифицированному алгоритму Floor Ceiling Decreasing.
Следующий алгоритм выполняется одновременно для ночных и дневных устройств:

1. Создаем первоначальный уровень
2. Если у нас нет ни дневных, ни ночных устройств, то ничего не делаем
3. Пока есть возможность размещать у стройства или создавать новые уровни: 3.1) Итерируем через все неразмещенные устройства:
   3.1.1) Если устройство дневное, то пробуем сначала разместить на пол, а потом на потолок.
   3.1.2) Если устройство не удалось разместить, то возвращаем его в массив неразмещенных устройств
   3.2) Создаем следующий уровень
   В коде:
   ./virtual-schedule-builder.js:58

/**
 * Размещение устройств, зависимых от времени суток по алгоритму floor-ceiling
 */
floorCeilDayNight() {
    // создаем начальный уровень для дневных устройств
    let day = this.createInitialLevel('day'); 
    // создаем начальный уровень для начных устройств
    let night = this.createInitialLevel('night'); 
    // если нет устройств, зависимых от времени суток, то ничего не делаем
    if (!night.devices.length && !day.devices.length) { return; } 
    while(true) {
        [ day.devices, night.devices ] = day.devices.concat(night.devices).reduce((ac, device) => {
            // если у устройства дневной режим, то пробуем разместить сначала на пол, а потом на потолок
            device.mode == 'day' ?
            (this.placeOnFloor(device, day.floor) || this.placeOnCeiling(device, day.ceiling)) || ac[0].push(device) :
            // если у устройства ночной режим, то пробуем разместить сначала на потолок, а потом на пол
            device.mode == 'night' ? 
            (this.placeOnCeiling(device, night.ceiling) || this.placeOnFloor(device, night.floor)) || ac[1].push(device) : null;
            // заодно записываем кого нам не удалось разместить
            return ac; 
        }, [ [], [] ])
        
        // создаем следующий уровень для дневных устройств
        day = this.createNextLevel(day); 
        // создаем следующий уровень для дневных устройств
        night = this.createNextLevel(night); 
        // если всё разместили или больше ничего нельзя разместить, то прерываемся
        if (!day.devices.length && !night.devices.length) { break; }
    }
}

createInitialLevel(mode)

• mode -- для устройств какого режима создавать уровень (day/night)
  Создает начальный уровень для устройств, зависимых от времени суток, равный по продолжительности самому продолжительному устройству с соответствующим временем суток. Причем, если это ночной уровень, то его потолок (левая граница) будет располагаться прямо перед началом дня, а если дневной, то его пол (правая граница) будет располагаться в самом начале дня. Таким образом между дневными и ночными устройствами получается максимально большое непрерывное незанятое место.
  Возвращает новый объект уровня.

createNextLevel(level)

• level -- объект предыдущего уровня
  Создает новый уровень с продолжительностью, равной продолжительности самого продолжительного неразмещенного устройства с соответствующим mode из которого всё ещё есть возможность создать уровень, таким образом, что если это ночной уровень, то его потолок (правая граница) будет располагаться прямо перед полом (левой границей) предыдущего созданного уровня, а если это дневной уровень, то его пол будет располагаться сразу после потолка предыдущего уровня. Таким образом группа размещенных ночных устройств остается максимально прижатой к конечной границе периода ночи, а группа дневных устройств максимально прижатой к начальной границе периода начала дня, что позволяет оставить как можно больше непрерывного свободного места между дневными и ночными устройствами для размещения устройств независящих от времени суток.
  Возвращает новый объект уровня.

placeOnFloor(device, floor)

Размещает устройство на полу уровня

• device -- объект устройства
• floor -- номер часа, который считается за пол уровня
  Проверяет возможность размещения устройства на часу являющемся полом уровня. Если возможности размещения нет, то возвращает false, если есть, то размещает и возвращает true. Перед тем как вернуть true принимает дополнительные меры для избежания тупикового состояния.

placeOnCeiling(device, ceiling)

Размещает устройства на потолке уровня

• device -- объект устройства
• ceiling -- номер часа, который считается за потолок уровня
  Сначала вычисляет час на котором должно быть размещено устройство, чтобы его последний час работы попал на потолок уровня путем вычитания duration устройства из ceiling. После этого проверяет возможность размещения устройства и размещает его, если такая возможность есть и возвращает false если такой возможности нет. Перед тем как вернуть true принимает дополнительные меры для избежания тупикового состояния.

floorCeilSafetyMeasures(placedDevice, placedHourNumber)

Дополнительная проверка на наличие тупиковых состояний при размещении какого-либо из устройств на полу или потолке какого-либо из уровней.

• placedDevice -- только что размещенное устройство
• placedHourNumber -- час, на котором оно было размещено
  Алгоритм:

1. Находим устройство независимое от времени с самым большим показателем duration
2. Проверяем остались ли у нас ещё часы, где мы можем разместить это устройство
3. Если не осталось, то убираем из расписания устройство, которое только что разместили и размещаем вместо него устройство независимое от времени суток и возвращаем false
4. Если осталось, то оставляем как есть и возвращаем true

bestFit()

Размещает оставшиеся устройства по безуровневой версии алгоритма Best Fit Decreasing. Предполагается, что устройства уже приоретизированы.
Алгоритм:

1. Для каждого неразмещенного устройства:
   1.1) Вычисляем для него часы, на котором оно может быть размещено
   1.2) Размещаем на том часу, на котором это устройство будет потреблять наибольшую долю оставшейся энергии

Приоретизация устройств ./utils/sort-devices.js

Реализовано несколько вариантов приоретизации устройств. Все они задуманы как коллбэки для функции Array.prototype.sort.

Приоретизация по duration ./utils/sort-devices.js:10

В основном используется она.
Выполняются следующие правила:

1. Устройство с mode ВСЕГДА приоритетнее устройства без mode
2. Устройство с большей duration приоритетнее устройства с меньшей duration (за исключением п.1)
3. Устройство с большей power приоритетнее устройства в меньшей power (за исключением п.1, п.2)

Альтернативная приоретизация (по power) ./utils/sort-devices.js:29

Иногда частных случаях может использоваться вместо приоретизации по duration.
Следующие правила:

1. Устройство с mode ВСЕГДА приоритетнее устройства без mode
2. Устройство с большей power приоритетнее устройства с меньшей power (за исключением п.1)
3. Устройство с большей duration приоритетнее устройства в меньшей duration (за исключением п.1, п.2)

Приоритезация только по duration ./utils/sort-devices.js:44

Выполняются следующие правила:

1. Устройство с большей duration ВСЕГДА приоритетнее устройства с меньшей duration
2. Устройство с большей power приоритетнее устройства в меньшей power (за исключением п.1)