みなさんはWalicaというサービスをご存知でしょうか？
Walicaは、友人や仲間内などで遊んだ時に発生する貸し借りなどの立替を、最終的に誰が誰にいくら払えばいいのかという計算をサポートしてくれるサービスです。

意外に知られてないようですが、僕自身は何年も前からWalicaを愛用していて、今までもWalicaを知らないたくさんの友達にWalicaの存在を広めてきました。
とても便利です！ぜひ使ってみてください！

日常的によく使っているのですが、たまに 「Walicaの計算って本当に正しいの？」 と疑問に思う友達がいたりします。
たしかに、最終的な清算金額の計算がどうやって行われているかなどどこにも書かれていませんし、自分も何回か疑問に思ったことはあります。ですがその度に自分で計算してみても金額が一致するので、何も考えずにいまも使っています。

Walicaのコアバリューはこの清算アルゴリズムです。
どんなにたくさんの立替が行われても、最終的に送金回数が最も少なくなるような清算最適化アルゴリズムが考えられています。
（開発者の方曰く、まだまだ改善余地があるようです。）

今回は疑問に思っている友達や同じことを考えたことがある人に向けて、送金回数が最小回数になる清算アルゴリズムを考えて、実際にWalicaの計算アルゴリズムが正しいのかを検証してみたいと思います。

ちなみにWalicaの開発者の方のブログが公開されているので興味がある方は読んでみてください。

清算金額計算の流れ

清算金額の計算のざっくりとした流れは以下の通りです。

ユーザーが立替の明細を記録する
（誰が何代をいくら払ったか、その対象は誰か）
誰がいくら支払ったかを計算して、本来支払うべき金額との差額を計算する
清算時の送金額を計算する

今回考えるのは最後の「清算時の送金額を計算する」部分です。

清算最適化アルゴリズムを考える

清算を行う方法はいろいろありますが、今回はこちらのブログ記事を参考にアルゴリズムの実装を行ってみます。
最後にWalicaの実際のデータと比較してみたいと思います。

この記事に書かれているように、最適化アルゴリズムは以下のように考えます。

立替のデータから全員の清算金額を計算する。
（支払った金額が多い人が正、少ない人が負となるように計算）
支払いが最も多い（受け取る金額が最も多い）人から順に並び替える。
支払いが最も多い人（最大債権者）に支払いが最も少ない人（最大債務者）が支払いを行う（清算）。
このときの精算金額は、最大債権者の金額（F）と最大債務者の金額（L）の絶対値を比較して、小さい金額を送金額とする。
```
\textrm{(送金額)} = \min(F,|L|)
```
送金額が0円になるまで2と3を繰り返す。

誰がいくらいくら払ったのか、またその人が本来いくら払うべきなのかを計算して、その差額を計算します。すると多く払っている人と少なく払っている人が出てきます。
そこから、送金額が大きくなる組み合わせ（最大債権者と最大債務者の組み合わせ）で順番に清算を行っていき、これを送金額が0円になるまで繰り返します。
そうすることで最終的な送金回数が少なくなるように清算を行うことができます。

アルゴリズムを実装する

ここから実際にアルゴリズムを実装していきます。
今回はPythonを使って実装を行います。

サンプルデータはJSONで以下のように定義します。
このデータはその人が実際に払った金額と本来払うべき金額の差額まで計算した状態です。多く払っている人が正の数となるようにしています。

main.py

sample_data = [
    {'member_name': 'A', 'price_to_get': 14318},
    {'member_name': 'B', 'price_to_get': 1198},
    {'member_name': 'C', 'price_to_get': -4252},
    {'member_name': 'D', 'price_to_get': -11262}
]

上で考えた清算最適化アルゴリズムを再帰関数として一つの関数に定義します。

paymentは清算前の貸し借りの金額データが入った配列で、liquidationには清算時に行う送金額を記録します。

paymentにあるデータを支払金額が多い人から順番（受け取る金額が多い順）にソートを行います。
paymentから最大債権者（最初）と最大債務者（最後）を取得して、送金額を計算します。

終了条件は総金額が0円の時としており、0円でない場合は債権者と債務者、送金額を記録したのちに再起呼び出しを行います。

main.py

def calculation(payment, liquidation=[]):
    # 支払金額が多い順に並べる（受け取る金額多い人が先頭）
    payment = sorted(payment, key=lambda p: p['price_to_get'], reverse=True)

    # 現在の最大債務者と最大債権者を取得
    creditor = payment[0]
    debtor = payment[-1]

    # 清算金額を算出
    amount = min(creditor['price_to_get'], abs(debtor['price_to_get']))

    # 清算金額が0円の場合は終了
    if amount == 0:
        return (payment, liquidation)

    # 債権者と債務者で清算を行い、再帰呼び出しを行う
    creditor['price_to_get'] -= amount
    debtor['price_to_get'] += amount
    liquidation.append({
        'debtor': debtor['member_name'],
        'creditor': creditor['member_name'],
        'amount': amount
    })

    return calculation(payment, liquidation)

清算の計算が終わったら、結果を出力します。
今回はmain関数で清算前の貸し借り金額、清算時の送金額、清算後の残債を表示するようにします。

main.py

def main():
    # total_balanceを取得（サンプルデータ）
    total_balance = sample_data

    # 清算前の貸し借り金額を表示
    print('清算前の貸し借り金額')
    for payment in total_balance:
        print(f"{payment['member_name']}: {payment['price_to_get']}")

    # 清算時の送金額を表示
    (payment, liquidation) = calculation(total_balance)

    print('-----------------')
    print('清算時の送金額')
    for l in liquidation:
        print(f"{l['debtor']} -> {l['creditor']}: {int(l['amount'])}")

    # 清算後の残債を表示
    print('-----------------')
    print('清算後の残債')
    for p in payment:
        print(f"{p['member_name']}: {int(p['price_to_get'])}")

    # 相殺金額
    print('-----------------')
    total = 0
    for p in total_balance:
        total += p['price_to_get']
    print(f'相殺金額: {int(total)}')


if __name__ == '__main__':
    main()

実装はここまでです。
ソースコードを実行してみます。

bash

$ python main.py

以下のように結果が表示されます。
人数以下の端数は清算されずに残ります。

bash

清算前の貸し借り金額
A: 14318
B: 1198
C: -4252
D: -11262
-----------------
清算時の送金額
D -> A: 11262
C -> A: 3056
C -> B: 1196
-----------------
清算後の残債
B: 2
A: 0
D: 0
C: 0
-----------------
相殺金額: 2

Walicaの計算アルゴリズムの検証（おまけ）

Walicaの清算アルゴリズムを疑っているわけではないですが、検証することが目的なので、Walicaから実際のデータを取得して清算金額が正しいかを、実装したアルゴリズムを使って確かめられるようにしてみたいと思います。

まずはWalicaのURLをコマンドライン引数で受け取れるようにします。

main.py

if __name__ == '__main__':
    # WalicaのURLを取得
    try:
        url = sys.argv[1]
    except IndexError:
        print('URLが入力されていません。')
        print('-----------------')
        url = None

    main(url)

Walicaのサーバーからデータを取得する関数を定義します。
WalicaのURLからgroup_idを取得して、清算前の貸し借り金額を取得します。

main.py

def get_total_balance(url):
    if url[-1] != '/':
        url += '/'

    group_id = url.split('/')[-2]
    print(f'Group ID: {group_id}')
    print('-----------------')
    api_url = f'https://manage-expence-api-prod.herokuapp.com/api/group/{group_id}/total_balance'

    try:
        response = requests.get(api_url)
    except requests.exceptions.RequestException as e:
        print('URLが正しくありません。')
        print(e)
        sys.exit(1)

    data = json.loads(response.text)
    return data

WalicaのURLが入力されたときはWalicaからデータを取得するようにして、URLがない場合はサンプルデータを使うようにします。

main.py

def main(url):
    # total_balanceを取得
    if url is None:
        total_balance = sample_data
    else:
        response = get_total_balance(url)
        base_currency_symbol = response['base_currency_symbol']
        total_balance = response['total_balance']

    # 以下省略

これで完成です。

実際のWalicaのデータと比較すると金額が一致していることが確認できるはずです。
Walicaの清算アルゴリズムが正しいことが確認できました。
送金の組み合わせの順番も同じ順番で表示されているので、もしかしたら同じアルゴリズムで計算されているのかもしれません。

今後は疑問に思っている友達がいたら、とりあえずこの記事を見てもらうようにしたいと思います笑

ソースコードはここから確認してください。
みなさんもぜひWalicaを使ってみてください！