ポケコインを効率よく買いたいので整数計画問題に落とし込む

Pokemon Goを始めた。 最初のポケモンはピカチュウであった。 卵を複数入手し、10kmという長距離を歩かされるものもあり、インキュベーターは複数あった方が効率がよさそうだなと思い、初めてGoogle Playカードを買った。 1500円である。 いざチャージしたお金をポケコインに換金しようとすると、1円1コインではなく一度に換金するコインの量によって変わることがわかった。

さて、どのように買えば効率よく買えるのだろうか。パッと見、貪欲戦略で解決しそうな気がしないでもないが、整数計画問題に落とし込めば近似解ぐらいは得られそうである。 Pythonでは、SciPyかPuLPが線型計画問題のライブラリを備えているようなので、簡単にかけそうなPuLPで解いてみた。

import pulp

# Google Playの残金額
amount_of_money = 1500

# 線型計画問題の定義
problem = pulp.LpProblem('PokeCoinMaximised', pulp.LpMaximize)
x_1 = pulp.LpVariable('100pokecoin', 0, 10, 'Integer') 
x_2 = pulp.LpVariable('550pokecoin', 0, 10, 'Integer') 
x_3 = pulp.LpVariable('1200pokecoin', 0, 10, 'Integer') 
x_4 = pulp.LpVariable('2500pokecoin', 0, 10, 'Integer') 
x_5 = pulp.LpVariable('5200pokecoin', 0, 10, 'Integer') 
x_6 = pulp.LpVariable('14500pokecoin', 0, 10, 'Integer')

# 目的函数
problem += 100 * x_1 + 550 * x_2 + 1200 * x_3 + 2500 * x_4 + 5200 * x_5 + 14500 * x_6

# 制約条件
problem += 120 * x_1 + 600 * x_2 + 1200 * x_3 + 2400 * x_4 + 4800 * x_5 + 11800 * x_6 <= amount_of_money

status = problem.solve()
print("Status", pulp.LpStatus[status])
print(x_1.value(), x_2.value(), x_3.value(), x_4.value(), x_5.value(), x_6.value())

結果であるが、予想通りの結果であった。

Status Optimal
2.0 0.0 1.0 0.0 0.0 0.0

貪欲戦略でよいのでは、という結論である。

『Effective Debugging』Item 3: 事前条件と事後条件が満たされていることを確認する

『Effective Debugging』の続き。タイトルオンリーな気がしないでもない。

www.kinokuniya.co.jp

Effective Debugging

怪しい箇所を調べる際には事前条件と事後条件を確かめましょうという話。 ルーチン（懐かしい響きだ）の前後、ルーチンが呼び出された前後、重要なアルゴリズムの実行前後にブレイクポイントを置いて調べよう、チェックしようという話。 函数に渡す引数は定義域に収まっているか、とか返り値は妥当な値なのか、などを調べる。 まあ、タイトルオンリーなのでこれ以上は本文読んでねとしか書けないが、最後によいメッセージがあった。

In all cases verify, don't assume.

「すべてのケースを調べろ、想定するな。」と訳せるだろうか。 何かと調べる際には先入観が邪魔したり、「正しいはず」と調べもせずに断定してしまうことがあるが、それを戒める一文である。 プログラミングに限らない話であるので、なるべく意識していきたいと思った次第。

『Effective Debugging』Item 2: 問題を見抜くためのWeb検索にはクエリを引用符で囲む

『Effective Debugging』の続き。まさかのGoogle先生。

www.kinokuniya.co.jp

Effective Debugging

項目名は検索方法に関するTips（二重引用符でキーワードを囲んで検索すると完全一致になる）だが、項目自体はWebの活用方法に関するものである。 "It's quite rare these days to work in a location lacking Internet access..."とある通り、インターネットから隔離された環境で働くというのは珍しいと筆者は述べている。 Effectiveシリーズで筆者は大学の先生らしいのでアカデミックな内容が続くのかなと思っていたが検索を活用せよという項目があってびっくりした。 Stack Overflowの話、検索しても出てこなかった場合の話が続く。

Black Duck Open Hub Code Searchというサービスが紹介されていてへえと思いつつアクセスしたら今は利用できないという現実を突き付けられた。 *1

昔、プログラマの計算機にはコンパイラが無くコンパイルする場合はソースコードを発注先の社員にメールで送信してコンパイル結果を受け取るという現場の話をどこかで聞いた。 これは極端な例であるが、インターネットにつながっていないという現場は意外に多そうな気がする。

*1:ちゃんと校正されているのかな？