餃子の支払と財布のダイエット

先日、昼に会社の近所で餃子定食を食べに行きました。田町には餃子定食が食べれるところが数か所ありますが、その日行った所の餃子は一回り大きく、たっぷりと肉が詰まっいて食べごたえがあることから何気に気に入っていて、月に一回のペースで食べに行ってます。

さて、食べ終えて、日ごろから共にランチしている同僚と一通りの雑談をしてから会計に行ったところからが本題となります。

ここで皆さん、定食のお値段が 880 円というありきたりな設定だった場合、お財布から出す硬貨はどのように選びますか？

私はその時いつもの習慣から「四百円とっ…」と言いながら、財布にあった 100 円を４枚とキャッシュトレーに配置し、最後に千円札を小銭の横に添えるように出しました。（100 円より小さい硬貨が無かったためです。）

店主から受け取ったお釣りの 520 円を財布にしまって店を出た後、同僚からとある事実を知りました。

というのは、いつからか財布に貯まる硬貨の枚数を最小限に保つためにやっている習慣ですが、このように 880 円の会計をする時に 1400 円を出すというのは世間的には珍しいという事です。

皆さんも自分では何気に習慣としてやっていることが、周りの人から言われて初めてそうでないと気付いた事があるのではないでしょうか。その時の瞬間や他の人の習慣が知れる時は意味深ですよね。

おしまい。

P.S. これだけだと技術系の投稿にはならないので、財布の硬貨を最低枚数に保つ出し方のロジックを考えてみることにしました。

支払をロジック化

意外と難しいかった・・・結論から言うと、下記に少し考えたけど、いい方法がちょっとやそっとで思いつきそうにないので諦めました。

日本だと 1000 円や 10000 円などのように百十一の位が０の紙幣があるのでそれに合わせて組み合わせ選んでいるけど、どんな硬貨・紙幣の種類がある国にでも対応できる汎用なロジックはいいのが思いつかない…

取り敢えず日本の通貨の定義はこうかな

denominations = [1, 5, 10, 50, 100, 500, 1000, 10000]

アルゴリズム１：財布の中身を何も考えずに全部渡しそれに対して釣銭を計算してもらい、戻って来たお釣りから元々渡さなくても良かった通貨・紙幣を引く

最適な釣銭を求める処理はなんとなく書ける（キャッシュドロアの中は無限という前提）

def denomiate_amount(amount):
    denominated = {}
    for denomination in reversed(sorted(denominations)):
        denominated[denomination] = int(amount / denomination) * denomination
        amount -= denominated[denomination] 
    return denominated

すると、財布に 100 円が 4 枚と千円が 1 枚あったときに

wallet = {100: 4, 1000: 1}

880 円の食事をした場合

# 買い上げ額
price = 880

# お財布そのまま出す
tray = wallet

# お釣りの額を計算
change = sum(d * n for d, n in tray.items()) - price
if change < 0:
    raise # 足りない

# 釣銭の最適な組み合わせ
changed = denomiate_amount(change)

# 戻ってきた硬貨を引いた組み合わせ
optimal = {d: n - changed[d] for d, n in wallet.items()}

という感じで optimal に結果が求まる。

ただ、雑なロジックなため問題が直ぐに一つ思いつく：

財布の中に元々千円札が 11 枚あった場合、11,400 円を出して一万円札と 520 円のお釣りを貰うが、千円 11 枚と一万円札は相殺されないので、実際それを出すことになる。これって店に結構な嫌がらせだと思う…

奥が深そうなのでこの辺でお手上げとします。

綺麗なアルゴリズムが思いついた方は是非コメントをください。