satetsu888のブログ

アラサーwebエンジニアのブログ

スチームオーブンレンジが欲しい人のための数理問題入門

サンドラッグが1000店舗記念だとかで、キャンペーンをやっている。

サンドラッググループ1000店舗達成ご愛顧感謝キャンペーン-TOP-

どうやら、5000円分以上または3000円分以上のレシートを送るとスチームオーブンレンジをはじめいろいろ当たるらしい。 最近オーブンレンジを買い換えようかと思っていて、なおかつ家の目の前にあるサンドラッグに日々生活費を落としている身としてはこれほど好都合なキャンペーンはない。 これは応募するしかないと思いつつも、1回の買い物は5000円もいかないので、日々の買い物レシートを貯めていたらずいぶんいっぱいになってしまった。

キャンペーンに応募するために、レシートの合計金額が5000円を越えるようにグループを作る必要があって、なおかつできるだけたくさん応募したい。 そして最後にあまるレシートは、中途半端な金額になってしまうよりは3000円コースに応募できるようにあまって欲しい。

これはいわゆる集合分割問題というやつを解く必要があるようだ。 集合分割問題の概要については下記のQiitaを眺めるのが手っ取り早い。

qiita.com

集合{M}とか部分集合{S}とかコスト{c_j}とかにカジュアルに出てこられると、スチームオーブンレンジドリブンなエンジョイ勢としては早くも投げだしたくなるが、ざっくりいうとこういうことだ、

  • 集合{M} → 全部のレシート
  • 部分集合{S} →応募するレシートの組み合わせ
  • コスト{c_j}{S}の組み合わせとしての良さ
    • 合計5000円ぴったりだと最高だし、8000円だと微妙でもっと無駄がない組み合わせがありそう、2000円しかないとダメ みたいな感じ

そして、レシートの組み合わせそれぞれについての良さを{weight}としてデータ構造を作ってやれば、あとは紹介されているライブラリ(このQiita書いた人がつくったっぽい)が組み合わせを適切に計算してくれるという話。

さて、僕の手元にあるレシートの各金額は下記の通りだ。

https://raw.githubusercontent.com/satetsu888/partition-of-a-set-for-sundrug/master/data.txt

これくらいの数なら手で適当に組み合わせてもそれなりにいい感じにできそうな気もしたが、まだ応募期間が終わってなくて期限ギリギリまでレシートが増え続けることを考えると、機械的に組み合わせを決定できるにこしたことはない。 世の中のたいていの手でやったほうが早そうに見えることというのは、わりと低くない確率でちょっとだけ条件が変わってもう一度やりなおしたり、計算したのに間違えててもう一度やり直したり、せっかくはじき出した結果をなくしてもう一度やりなおしたりすることになるし、なんでも再現性高くコンピュータでやってくのがよい。21世紀だし。

そしてスチームオーブンレンジ欲しさに初めて書いたPythonコードを晒しておく

calc partition of a set for sundrug

今回やらなくてはいけない主な処理はだいたい汎用的なものなので、見よう見まねで既存ライブラリを繋げば動く

itertools.combinations で各レシートの組み合わせを簡単に列挙できて大変便利。 その組み合わせについてcalc_weightで各グループのスコアを計算している、5000を越えると1ずつ上がっていく、3000~4999の間は3000からの距離の50倍をスコアにした。 そして計算量をがんばって押さえ込むために、upper_limitを設定し、それを超えているグループは最初から組み合わせ計算にいれない。 できた組み合わせの元データ上のindex、と重みをセットにして組み合わせ計算ライブラリに放り込む。

当初は全体の最適解を計算しようと思ったのに、組み合わせが膨大すぎてスーパーコンピュータでもないと終わらない感じだったので、 諦めてレシートを3分割してそれぞれの中で組み合わせを作っている。 しかも順序が固定だとそれなりの解にも到達しないことがあったのでランダムソートまでしていて、stableな結果は出力されない。 まあ今回は最適解よりレシートが追加された時に機械的に何度でも解を出すのが目的だし、良いことにしよう(負け惜しみ)。

結果以下のようなものが得られて、5000円コースに7本、3000円コースに3本応募できることがわかった。

calc partition of a set for...
[383, 2217, 518, 412, 760, 1387, 1964, 4944, 1281, 579, 1084, 2017, 306, 1008]
create 16383 groups
finish calc weight
cut lower
317
cut upper
14885
calc
1181
=RESULT=
[518, 4944]
sum:5462

[2217, 1964, 1008]
sum:5189

[383, 760, 1281, 579]
sum:3003

[412, 1387, 1084, 2017, 306]
sum:5206


calc partition of a set for...
[2985, 888, 794, 417, 898, 1661, 659, 1370, 537, 880, 977, 1615, 949]
create 8191 groups
finish calc weight
cut lower
245
cut upper
6911
calc
1035
=RESULT=
[2985, 794, 1661, 537]
sum:5977

[417, 659, 977, 949]
sum:3002

[888, 898, 1370, 880, 1615]
sum:5651


calc partition of a set for...
[2819, 178, 1068, 1965, 1125, 810, 851, 1090, 563, 500, 414, 1381, 813]
create 8191 groups
finish calc weight
cut lower
369
cut upper
6618
calc
1204
=RESULT=
[2819, 1068, 851, 414]
sum:5152

[1125, 563, 500, 813]
sum:3001

[178, 1965, 810, 1090, 1381]
sum:5424

手作業でもなんでも、これより良い組み合わせを作れるぞという方は至急連絡いただきたい。(キャンペーンの応募は12/7までだよ!)

コードの実行が終わらなくて、並列計算とかクラウドの計算リソースとかも考えたけど、集合分割問題に特化したアルゴリズムが並列計算できるのかどうか全然知らないのと、組み合わせ爆発したデータの計算はクラウドに重課金くらいじゃ済まない気がするのでやめた。 そこにお金使うなら普通にスチームオーブンレンジ買うよね・・・