Проблема
В мае жители городов русских начинают ездить на природу и устраивать весенний шашлык, культурно выпивать и радоваться теплой погоде. После окончания праздника очень сложно разобраться, кто сколько чего купил и кто кому сколько должен. В данном посте я запишу идею телеграм бота, который решит эту проблему раз и навсегда.
var totalExpenses = clients.reduce(function(total, client) { return total + client.expenses; }, 0);
// 2, -998, 704, 292
// Федор внес меньше всех - 300. Ему придется заплатить чуть больше, чем всем остальным
Результат:
Алгоритм готов. 😎 В следующем посте будут описаны интерфейсы. А еще позже - реализация и релиз. Продолжение во втором посте.
Концепт
Телеграм бот
Почему решение будет оформено в виде телергам бота? Задача простая и выполнять ее нужно не так часто. Выпускать приложение или создавать сайт не имеет смысла. А вот бот отлично подойдет:
- не надо скачивать/устанавливать;
- не надо искать в интернете, можно пролистать списог диалогов в мессенджере;
- результат работы алгоритма - текстовое сообщение, его легко скопировать и отправить друзьям в разные мессенджеры;
- простой и удобный ввод данных.
Постановка задачи
Если люди, которые вместе отдыхают. Каждый в отдельности покупает продукты, напитки и товары для общего пользования. Все в равной степени пользуются общими покупками и в равной степени несут расходы за покупки. Необходимо произвести взаиморассчет.
Алгоритм
Исходные данные
На вход алгоритм получает массив объектов. Каждый объект - это имя и затраченные финансы. Пример:
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
// 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
}
];
Результат: