自販機で１０００円を使い切りたいんじゃ！

この記事は `エンジニアと人生 Advent Calendar 2022` の19日目の記事です。18日目は h1d3mun3 さんの[業務引き継ぎの際の考慮ポイント](https://zenn.dev/h1d3mun3/articles/e26010e49195a2)でした。

https://adventar.org/calendars/7632



# 初めに

オフィスに通勤する回数が減った昨今ですが....
オフィスならどこにでもありますよね！自動販売機って！
![bending machine](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175242/4f063cb9-ce5b-c158-3e8a-7f34709a8bab.jpeg)


（引用：[ポッカサッポロ自動販売機](http://www.hachiyoh.co.jp/master/products/pokka.html)）

当然のことながら、自社でもフロアには自販機があります。

## 問題点①

会社の自販機は電子決済オンリーの仕様になっています。
一見すると問題なさそうに見えますが...

なんと**楽天Edy**しか使えない...
使い勝手が悪い...
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175242/4e0f13ff-a1b5-d3c9-d292-ba2a14697194.png" width="300">



（引用：[電子マネー 楽天Edy](https://edy.rakuten.co.jp/)）

`楽天Edy` は iPhone では使えないため、わざわざ `Edy` カードを持つ必要があります。Android の場合は、`Google Pay` 経由で使えるので、自分はこのためだけにデバッグ用に持っていた Android 端末を持ち歩いていました。

これでとりあえずはいいか！と思っていましたがまだ問題が...

## 問題点②

先に問題点だけ書くと、`Google Pay` が**1000円単位でしかチャージできない**ことです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175242/f0f19227-cb93-6a75-e973-946d7b2e806f.png" width="500">


（引用：[Google Pay™に楽天Edyを設定する](https://edy.rakuten.co.jp/howto/google/pay/)）

自販機の飲料は**100円単位ではなく10円単位で違う**ため、ほとんどの場合は使い切らずに端数が残ってしまいます。

さらに弊社の場合は、自社ビル割引なのか？中途半端に**1円単位**で安くなっているいるため、さらに**使い切るのが困難**になっています。

【実際の写真】

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175242/cb93a481-fded-2889-9bcc-173c3c33ddcf.jpeg" width="500">

## 理想

**自販機で１０００円を使い切りたいんじゃ！**

ということで、これをプログラミングで解決していきます。

# 発想

## 1. 条件

**１０００円を使い切るための組み合わせ**を考えていくことになります。
まず、フロアにある自販機の飲み物を列挙していきます。

<details>
<summary>飲料一覧を見る</summary>

- おいしい水 天然水：８９円
- Wilkinson Tansan：８９円
- Wilkinson Tansan Lemon：８９円
- ポカリスエット：８９円
- Welch's FRUIT WATER LEMON：８９円
- Welch's グレープ50ぶどう由来のポリフェノール：７９円
- リポビタンD：９６円
- 「届く強さの乳酸菌」W(ダブル) 「プレミアガセリ菌 CP2305」：９６円
- モンスターエナジー：１９０円
- モンスターエナジー ウルトラ：１９０円
- モンスター パイプラインパンチ：１９０円
- ダイドーブレンド微糖 世界一のバリスタ監修：８９円
- 極 ブラック 400g：９６円
- 極 カフェオレ 285g：９６円
- 極 微糖 285g：８９円
- 極 ブラック 285g：８９円
- ドトール　カフェ・オ・レ：８９円
- ワンダ ディープマウンテン：７９円
- ワンダ 金の微糖：７９円
- ワンダ モーニングショット：７９円
- ワンダ 特製カフェオレ：７９円
- ワンダ ごほうび抹茶ラテ
- カルピスウォーター：８９円
- なだ万監修 日本茶：８９円
- なだ万監修 ほうじ茶：８９円
- 十六茶麦茶：８９円
- 十六茶：８９円
- 和紅茶：８９円
- ドデカミン 500ml：９６円
- ドデカミンストロング：７９円
- 三ツ矢サイダー 500ml：８９円
- 三ツ矢100%オレンジミックス：８９円
- 三ツ矢サイダー レモン＆ライム：７９円
- 三ツ矢クラフトコーラ：７９円
- すっきり1日分のマルチビタミン：７９円
- さらさら毎日おいしくトマト：７９円
- カルピス(R)THE RICH：７９円
- バンホーテンココア：７９円
- ロイヤルミルクティー：７９円

</details>


これは値段別にすると４パターンに分類できました。

|79円|89円|96円|190円|
|:---:|:---:|:---:|:---:|
|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175242/3a82665a-e8a5-5ca1-14e8-0547a6bffc60.jpeg" width="150">|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175242/f4d33b30-a203-2d22-5d7d-619dd69828f8.jpeg" width="150">|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175242/102c0f2e-181f-2669-22d3-0a794c97d398.jpeg" width="140">|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175242/22b1bfa2-b56c-92a5-7965-cf8a8bfbade2.jpeg" width="140">|

この４つの料金の飲料を無制限に選択して、１０００円を作っていきます。


## 2. ナップサック問題から着想を得る

ここでパッと浮かんだのは**ナップサック問題**に近いなと言う印象です。

### - ナップサック問題とは？

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175242/16a10b5b-d738-7bfe-aa07-70ff9bb0255e.png" width="400">


> n 種類の品物（各々、価値 vi、重量 wi）が与えられたとき、重量の合計が W を超えない範囲で品物のいくつかをナップサックに入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいかという整数計画問題である。

（引用：[ウィキペディア ナップサック問題](https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C)）

ナップサック問題では、**値段**と**重さ**の２つを考慮する必要がありますが、今回は**値段だけ**なのでもう少し簡単かなと言う感じです。

さらにいえば、条件が１つなので`部分和問題`を考えれば良いことになります。

### - 部分和問題とは？

> 与えられた n 個の整数 a1,...,an から部分集合をうまく選んで、その集合内の数の和が与えられた数 N に等しくなるようにできるかどうかを判定する問題である。

>たとえば、「{1,3,7,10,13} の部分和で、和が 21 になるものは存在するか？」であれば存在する（{1,7,13}である）、が答えである。また「{2,4,6,8,10} の部分和で、和が 19 になるものは存在するか？」であれば、存在しない（どんな部分和も偶数にしかならない）、が答えである。

（引用：[ウィキペディア 部分和問題](https://ja.wikipedia.org/wiki/%E9%83%A8%E5%88%86%E5%92%8C%E5%95%8F%E9%A1%8C)）

のっていた例題が今回考えたいこととまさに同じです。

### - アプローチ

一旦、計算量のことは考えないとすると

- `深さ優先探索`（DFS: Depth First Search）
- `動的計画法`（DP: dynamic programming）

あたりが方法として上がってくるかと思います。

## 3. 深さ優先探索を使って導く

### - 理由

今回は

- 飲料４パターンの組み合わせ
- 合計値が１０００円
 
と言う**比較的小さい数字**であるため、こちらのほうが簡単に実装できると思います。

概算値としても

- 飲料は１個で１００円前後なので、10回前後の処理を行えば１つの処理が終わる
- 組み合わせは単純計算で `4^10 = 1048576 ≒ 100万` なので長くても数秒程度

と言うことも考えて`深さ優先探`を選択しています。

### - 実装

方針まで立てましたが、考えたくないので流行りの [ChatGPT](https://openai.com/blog/chatgpt/) に投げました。

![ChatGPT_1](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175242/3ef623a1-37a9-a0ba-cc45-f0921ac68a8a.png)

iOSエンジニアなので `Swift` で回答を求めました笑
そして実はこれ以外にも投げましたが...シンプルなこれが良かったです。


![ChatGPT_2](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175242/5064d21d-4141-99b9-4f5b-973391b70a10.png)

良さげな回答なんですが、結論から言うとこれでは**条件を満たせていません**。
（本件とは関係ないが、自動生成のコメントアウトまで日本語なのはちょっと感動）

上記のコードでは**有限個の数**しか満たせていません。そこでコードに少しだけ手を加えます。

```diff_swift
func unlimitedPartialSums(numbers: [Int], target: Int) -> [[Int]] {
    var result: [[Int]] = []
    let n = numbers.count
    
    func dfs(_ i: Int, _ sum: Int, _ partial: [Int]) {
-       if i == n {
-           if sum == target {
-               result.append(partial)
-           }
+       if sum == target {
+           result.append(partial)
+           return
+       }
+       if i == n || target < sum { // 無限に処理が発生しないようにする
            return
        }
        
        dfs(i + 1, sum, partial)
        dfs(i + 1, sum + numbers[i], partial + [numbers[i]])
+       dfs(i, sum + numbers[i], partial + [numbers[i]]) // 無限個選択を満たす
    }
    
    dfs(0, 0, [])
-   return result
+   return Array(Set(result)) // 重複した処理を取り除く
}
```

これを実行すると

```.swift
let result = unlimitedPartialSums(numbers: [79, 89, 96, 190], target: 1000)
print(result)
```

```
[
  [79, 79, 79, 79, 79, 79, 79, 79, 89, 89, 190], 
  [89, 89, 89, 89, 89, 89, 89, 89, 96, 96, 96], 
  [79, 89, 89, 89, 89, 89, 96, 190, 190]
]
```

無事に結果を得られました！
※ 見やすいように改行しています

少し見ずらいので、式を `Dictionary` にして返すように変形しました。


```diff_swift
- func unlimitedPartialSums(numbers: [Int], target: Int) -> [[Int]] {
-   var result: [[Int]] = []
+ func unlimitedPartialSums(numbers: [Int], target: Int) -> [[Int: Int]] {
+   var result: [[Int: Int]] = []
    let n = numbers.count
    
    func dfs(_ i: Int, _ sum: Int, _ partial: [Int: Int]) {
        if sum == target {
            result.append(partial)
            return
        }
        if i == n || target < sum {
            return
        }
        
+       var tmp = partial
+       tmp[numbers[i], default: 0] += 1
        
        dfs(i + 1, sum, partial)
-       dfs(i + 1, sum + numbers[i], partial + [numbers[i]])
-       dfs(i, sum + numbers[i], partial + [numbers[i]])
+       dfs(i + 1, sum + numbers[i], tmp)
+       dfs(i, sum + numbers[i], tmp)
    }
    
-   dfs(0, 0, [])
+   dfs(0, 0, [:])
    return Array(Set(result))
}
```

これを実行すると

```.swift
let result = unlimitedPartialSums(numbers: [79, 89, 96, 190], target: 1000)
print(result)
```

```
[
  [89: 5, 79: 1, 96: 1, 190: 2], 
  [79: 8, 190: 1, 89: 2], 
  [96: 3, 89: 8]
]
```

とても見やすくなりました！
どの**組み合わせが良いのかわかる**ようになりましたね！


# 終わりに

ちなみに最近は自販機で`楽天Pay`(QR決済)が使えるようになったらしく、iPhone で済むとのこと。なんなら**１０００円以上は１円単位でチャージできる**ので**こんなこと考えなくて良い**らしい。

というか、何買ったか逐一覚えてられないし、好きなものを縛られず飲みたいよな...

**あ〜〜スタバ飲みて〜〜**

こうして僕はオフィスの外のスタバに行くのであった。

![gekijou_end_kan.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175242/3e7eba5f-5540-dc6c-d5ce-088dc504ebfb.png)