У нас с друзьями долги копятся не за один вечер, а месяцами. Сходили поесть, кто‑то заплатил за всех, на месте скидываться неудобно: у кого‑то нет наличных, у кого‑то деньги на другой карте, кто‑то обещает перевести позже. Через неделю ресторан, платит другой. Потом кино, потом такси, потом опять кафе. Кто‑то ждёт зарплату, кто‑то просто забыл, кто‑то отдал часть и считает, что закрыл всё.
Через месяц выясняется, что посчитать это уже нельзя: никто не помнит сумм, переписка не помогает, а половина участников уверена, что они в расчёте. Обычно всё заканчивается тем, что кто‑то один машет рукой и молча остаётся в минусе.
Ключевое тут не арифметика, а то, что долги надо записывать по ходу дела и закрывать явно. Поэтому я написал бота с мини‑приложением в Телеграме. Под катом три вещи, ради которых стоит читать: как схлопывать долги в минимум переводов, как считать чеки моделью со зрением и не гадать о расходах, и почему в проекте до сих пор ноль зависимостей.
Задача: минимум переводов
Первое, что выясняется: большинство переводов лишние. Если Аня должна мне, а я должен Максу, то Аня может перевести сразу Максу, и один перевод исчезает.
Сначала считаем баланс каждого: сколько человек заплатил минус сколько он наел. Дальше остаются только итоговые числа, и кто именно за что платил, уже не важно.
// Баланс: заплатил минус своя доля. Сумма всех балансов всегда ноль. const balance = new Map(); for (const e of expenses) { balance.set(e.payerId, (balance.get(e.payerId) ?? 0) + e.amountKop); for (const s of e.shares) balance.set(s.memberId, (balance.get(s.memberId) ?? 0) - s.amountKop); }
Дальше жадный алгоритм: берём самого большого должника и самого большого кредитора, закрываем меньшую из двух сумм, повторяем.
const debtors = [...balance].filter(([, v]) => v < 0).sort((a, b) => a[1] - b[1]); const creditors = [...balance].filter(([, v]) => v > 0).sort((a, b) => b[1] - a[1]); const transfers = []; let i = 0, j = 0; while (i < debtors.length && j < creditors.length) { const amount = Math.min(-debtors[i][1], creditors[j][1]); transfers.push({ from: debtors[i][0], to: creditors[j][0], amountKop: amount }); debtors[i][1] += amount; creditors[j][1] -= amount; if (debtors[i][1] === 0) i += 1; if (creditors[j][1] === 0) j += 1; }
Переводов получается не больше, чем участников минус один: на каждом шаге хотя бы один человек закрывается полностью. На примере из шести человек и восьми трат четырнадцать переводов «каждый каждому» схлопываются в пять.
Честная оговорка: минимальное число переводов в общем случае это NP‑полная задача (она сводится к разбиению на подмножества с нулевой суммой). Жадный алгоритм даёт не оптимум, а верхнюю границу n-1. Но разница проявляется на компаниях, где балансы удачно складываются в группы, а в компании из шести человек это исчезающе редкий случай, зато результат объясним: «ты переводишь одному человеку, вот столько». Понятность здесь важнее пары лишних переводов.
Кстати, ровно так же работает клиринг в платёжных системах: считается нетто‑позиция каждого участника, а деньги двигаются только по итогам. Это мне подсказали в комментариях, и объяснение оказалось лучше моего.
Деньги в копейках, а не в числах с плавающей точкой
Скучно, но обязательно: все суммы целые, в копейках. Доли округляются вниз, а оставшиеся копейки достаются тем, у кого дробная часть была больше. Это метод наибольших остатков, тот же, по которому распределяют мандаты между партиями:
function splitEqually(amountKop, memberIds) { const base = Math.floor(amountKop / memberIds.length); const rest = amountKop - base * memberIds.length; return memberIds.map((id, index) => ({ memberId: id, amountKop: base + (index < rest ? 1 : 0) })); }
При равных долях остатки одинаковы, и копейки уходят первым по порядку. Интереснее случай с чеком: там доли пропорциональны позициям, дробные части разные, и копейка достаётся тому, кому не хватило больше всех. Скидка из чека раскидывается так же. Пользователь этого не видит, но без этого итог не сходится с чеком, и первое, что скажет любой человек: «у вас тут на рубль не бьётся, я не доверяю».
Чек по фото
Переписывать позиции руками никто не будет, поэтому чек фотографируется и распознаётся моделью со зрением. Просим строго структурированный ответ:
{ "items": [{ "title": "Пицца Маргарита", "amountKop": 54000 }], "sumKop": 493000, "totalKop": 493000 }
Отдельно просим сумму позиций и итог по чеку: если они разошлись, значит модель что‑то потеряла или выдумала, и приложение честно говорит, что итог не сошёлся, вместо того чтобы молча делить неправильные числа. Плюс любую строку можно поправить карандашом прямо в приложении.
Цифры приводить не буду: расход зависит от выбранной модели, от числа позиций в чеке и от того, насколько подробно модель отвечает, а прайсы меняются. Полезнее сам подход: учёт я веду строкой на каждый чек, с числом позиций и числом токенов. В счёте провайдера всё сложено в общий итог за сутки, и без своего журнала невозможно отличить рост от новых пользователей от роста из‑за того, что модель стала болтливее. Заодно сразу видно, если средний чек подорожал вдвое: значит, что‑то изменилось в ответах модели, а не в числе людей.
Две грабли, на которые я наступил.
Первая: глобальный агент Node 22. Запросы к модели начали падать ровно через 5 секунд с загадочной ошибкой. Оказалось, у глобального HTTPS‑агента в Node 22 появился таймаут по умолчанию, и для долгих запросов нужен свой:
const agent = new https.Agent({ keepAlive: true });
Вторая: модель иногда думает минутами. nginx отдавал 504, а человек смотрел на крутилку и уходил. Сделал предел в 22 секунды на попытку и две попытки, с показом номера попытки на экране. Лучше честное «пробую ещё раз», чем бесконечное ожидание.
Ноль зависимостей
В проекте 6 тысяч строк на Node 22 и ни одного пакета в dependencies. Не из принципа, а потому что всё нужное уже есть в платформе:
HTTP‑сервер и запросы:
node:http,node:httpsподпись мини‑приложения:
node:cryptoтесты:
node --test, сейчас их 179хранилище: JSON‑файл на компанию через
node:fsс атомарной записью во временный файл и переименованием
Отправка фотографии в Телеграм это единственное место, где пришлось написать руками чуть больше обычного: multipart‑тело собирается вручную из буферов. Это 40 строк, которые не ломаются при обновлении и которые я полностью понимаю. Вместо этого можно было принести пакет с двадцатью транзитивными зависимостями.
Побочный эффект приятный: деплой это scp папки и systemctl restart, а обновление Node не ломает вообще ничего.
Мини‑приложение: вход без пароля
Приложение внутри Телеграма получает строку initData, подписанную ключом, выведенным из токена бота. Проверка подписи на сервере это весь вход: ни регистрации, ни паролей, ни хранения чужих учёток.
const secret = crypto.createHmac('sha256', 'WebAppData').update(botToken).digest(); const check = crypto.createHmac('sha256', secret).update(dataCheckString).digest('hex');
Плюс проверка возраста подписи: старая почти всегда означает, что её выдернули из чужой ссылки. Это единственное место в проекте, где ошибка стоит по‑настоящему дорого, поэтому там нет ни одной поблажки в духе «временно отключим для отладки».
152-ФЗ, про который все забывают
Неожиданная часть работы. Как только вы обрабатываете имена и фотографии людей, вы оператор персональных данных, и это значит:
уведомление в Роскомнадзор до начала обработки
отдельное уведомление о трансграничной передаче, если фото чека уходит на зарубежный сервер модели
согласие на обработку отдельным действием, а не галочкой «согласен со всем сразу»
политика обработки, доступная по ссылке
Я подал оба уведомления, развёл согласия по двум разным действиям и написал политику. Это заняло примерно столько же времени, сколько распознавание чеков. Зато теперь бота не страшно показывать.
Что получилось
Мини‑приложение в Телеграме: траты, чек по фото с делением по позициям, расклад с минимумом переводов, подтверждение возвратов, отправка итога картинкой в общий чат. Бота можно добавить в чат компании и писать траты одной строкой, а можно вообще не добавлять и вести всё в приложении.
Бесплатно, без рекламы, переписку в чате бот не читает: видит только свои команды и нажатия своих кнопок.
Ссылка: t.me/chek_split_bot
Интересно, кстати, мнение про жадный алгоритм: стоит ли вообще искать оптимум для маленьких компаний, или понятность результата важнее? И как вы сами делите расходы в поездках?
