Thursday, May 10, 2018

Хорошо посидели бот (часть 1)

Проблема


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


Концепт


Телеграм бот


Почему решение будет оформено в виде телергам бота? Задача простая и выполнять ее нужно не так часто. Выпускать приложение или создавать сайт не имеет смысла. А вот бот отлично подойдет:
  • не надо скачивать/устанавливать;
  • не надо искать в интернете, можно пролистать списог диалогов в мессенджере;
  • результат работы алгоритма - текстовое сообщение, его легко скопировать и отправить друзьям в разные мессенджеры;
  • простой и удобный ввод данных.

Постановка задачи


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


Алгоритм


Исходные данные


На вход алгоритм получает массив объектов. Каждый объект - это имя и затраченные финансы. Пример:

var clients = [
    {
        name: "Вадим",
        expenses: 1000
    },
    {
        name: "Денис",
        expenses: 2000
    }, 
    {
        name: "Федор",
        expenses: 300
    }, 
    {
        name: "Юрий",
        expenses: 710
    }
];

Шаг 1


Находим общую сумму затраченных средств. Пример:

var totalExpenses = clients.reduce(function(total, client) { return total + client.expenses; }, 0);

// 1000 + 2000 + 300 + 710 = 4010

Шаг 2


Находим среднее арифметическое:

var arithmeticAverage = Math.floor(totalExpenses / clients.length);

// 4010 / 4 = 1002.5

Тут надо отметить, что не всегда среднее арифметическое это целое число. Поэтому среднее арифметическое округляем до меньшего.

// Math.floor(4010 / 4) = 1002

Шаг 3


Благодаря округлению у нас появилась дельта:

var delta = totalExpenses - arithmeticAverage * clients.length;

// 4010 - 1002 * 4 = 2

Дельта нам понадобится позже.

Шаг 4


Теперь найдем кто сколько недоплатил или переплатил.

var clients = clients.map(function(item) { 
    item.delta = arithmeticAverage - item.expenses;
    return item;
});

// 2, -998, 702, 292

Отрицательное значение означает, что человек переплатил; положительное - недоплатил.

Шаг 5


Если сложить все значения из шага 4, то значение не будет равным 0. Таким образом невозможно произвести взаимный расчет. Эта проблема возникла из-за округления в шаге 2. Чтобы произвести деребан, надо что-то делать с дельтой из шага 3.

Решение спорное, но логичное: дельту в округлении заплатит тот участник, кто первоначально потратил средств меньше всех:

var idx = 0;
var maxDelta = clients[idx].delta;
clients.forEach(function(client, index) {
    if (client.delta > maxDelta) {
        idx = index;
        maxDelta = client.delta;
    }
});

clients[idx].delta += delta;


// 2, -998, 704, 292
// Федор внес меньше всех - 300. Ему придется заплатить чуть больше, чем всем остальным

Важно! Возможна ситуация, когда несколько человек внесли минимум средств. В таком случае алгоритм работает "несправедливо" 🙂

Шаг 6


Пишем простой алгоритм, который распределяет платежи.

// метод проверяет, закончен ли взаиморасчет
var isFinished = function() {
    var finished = true;

    clients.forEach(function(client) {
        if (client.delta != 0)
            finished = false;
    });

    return finished;
}

// в цикле распределяем затраченные средства
while (!isFinished()) {
    var idx = 0;
    var minPositiveDelta = clients[idx].delta;

    clients.forEach(function(client, index) {
        if (client.delta > 0 && client.delta > minPositiveDelta) {
            idx = index;
            minPositiveDelta = client.delta;
        }
    });

    // отбираем того, у кого самый маленький долг
    var payer = clients[idx];

    // раскидываем долг тем, кто переплатил
    for (var i = 0; i < clients.length; i++) {
        var recipient = clients[i];

        if (recipient.delta < 0 && payer.delta > 0) {
            var payment = Math.min(Math.abs(recipient.delta), payer.delta);

            recipient.delta += payment;
            payer.delta -= payment;

            // логируем платеж
            console.log(payer.name + " -> " + recipient.name + "  $ " + payment);
        }
    }
}

// Федор -> Денис  $ 704
// Юрий -> Денис  $ 292
// Вадим -> Денис  $ 2


Еще пример


var clients = [
    {
        name: "Вадим",
        expenses: 1000
    },
    {
        name: "Денис",
        expenses: 2000
    }, 
    {
        name: "Федор",
        expenses: 300
    }, 
    {
        name: "Юрий",
        expenses: 710
    }, 
    {
        name: "Коля",
        expenses: 830
    }, 
    {
        name: "Наташа",
        expenses: 1120
    }, 
    {
        name: "Оля",
        expenses: 560
    }
];

Результат:



Итого


Алгоритм готов. 😎 В следующем посте будут описаны интерфейсы. А еще позже - реализация и релиз. Продолжение во втором посте.