「サイゼリヤで1000円あれば最大何kcal摂れるのか」をなでしこでDPで解いてみた。

# 前書き

N番煎じもいいところですが「サイゼリヤで1000円あれば最大何kcal摂れるのか」が流行っているようので．

* [サイゼリヤ1000円ガチャをつくってみた(Heroku + Flask + LINEbot)](https://qiita.com/marusho_summers/items/a2d3681fac863734ec8a)
* [「サイゼリヤで1000円あれば最大何kcal摂れるのか」を量子アニーリング計算(Wildqat)で解いてみた。](https://qiita.com/hodaka0714/items/cf44b4ece992a39b5be4)
* [「サイゼリヤで1000円あれば最大何kcal摂れるのか」をSMTソルバー(Z3)で解いてみた。](https://qiita.com/tanakh/items/a1fb13f78e0576415de3)
* [「サイゼリヤで1000円あれば最大何kcal摂れるのか」を整数計画法ソルバー(PuLP)で解いてみた。](https://qiita.com/YSRKEN/items/dfc8604eb8598e5e9076)
* [「サイゼリヤで1000円あれば最大何kcal摂れるのか」をマルコフ連鎖モンテカルロで解いてみた。](https://qiita.com/kaityo256/items/b9a146d806dcb4f6edf9)
* [「サイゼリヤで1000円あれば最大何kcal摂れるのか」をExcel のソルバーでで解いてみた。](https://qiita.com/miki_iwa/items/5e0434da8b1150c21741)
* [【Excel】サイゼリヤ1000円で摂れるカロリーの最大値をVLOOKUP関数だけで求める方法](https://www.waenavi.com/entry/20190519/1558269886)
* [「サイゼリヤで1000円あれば最大何kcal摂れるのか」をTeX言語で計算する ～TeX言語で動的計画法(DP)～](https://doratex.hatenablog.jp/entry/20190520/1558323856)

**もともとの趣旨はたぶん『最適化手法/ソルバーをいろいろやってみる面白さ』だったはず**なんですが，どうせお祭りだから深夜のテンションということで自分の好きな言語の紹介をさせてもらいます．明日になったら恥ずかしくなって消すかも．

DPで解けるんだったらたぶんなでしこでも回るはず．なでしこだったら「誰でも簡単プログラマー」なはずなので読めばわかるコードになるはずで，きっとDP書いても何やってるかわかるはずだと期待．

# なでしことは

日本語プログラミング言語．v1の方を使います．
https://nadesi.com/top/

# データの準備
@marusho_summers さんのGitHubから拝借（ありがとうございます）．

```nadesiko:DBダウンロード.nako
データベースURLは『https://github.com/marushosummers/Saizeriya_1000yen/raw/master/sensai/saizeriya.db』
データベース保存先は母艦パス＆「saizeriya.db」
データベースURLをデータベース保存先へHTTPダウンロード
終わり
```

なでしこではメインフォームを母艦と呼びます．ひまわりのころからの慣習です．
そんな由来で「母艦パス」でスクリプトファイルと同じパスを指定できます．

# 読み込みテスト

```nadesiko:DB読み込みテスト.nako
データベース保存先は母艦パス＆「saizeriya.db」
データベースはデータベース保存先をSQLITE3開く
「SJIS」にSQLITE3出力コード設定
データ＝データベースで「select * from menu」をSQLITE3実行してCSV取得

表示用グリッドとはグリッド
そのアイテムはデータ
そのレイアウトは全体
```
標準でSQLite3が叩けます．そして3行でマトリクスを可視化できます．
素晴らしいですよね．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/37191/305fa097-a047-d605-5dce-46c427ad0058.png)

# 全探索
せっかくなので全探索も．
ただしガチでやると返ってこなくなるので **全部はやらず20メニュー削ります**．

```nadesiko:全探索.nako
# 読み込み
データベース保存先は母艦パス＆「saizeriya.db」
データベースはデータベース保存先をSQLITE3開く
「SJIS」にSQLITE3出力コード設定
データ＝データベースで「select * from menu」をSQLITE3実行してCSV取得

# 見出し列の削除
データの0個目を配列削除

# ガチでやると終わらないのでデータを減らす (TT
20回、データの0を配列削除

# 値段とメニュー名とカロリーの抽出
メニュー名一覧はデータの1個目を表列取得
値段一覧はデータの4個目を表列取得
カロリー一覧はデータの5個目を表列取得

# 初期化
最終カロリー = -1
最終注文一覧 = 「」
最終値段 = 0円
メニュー数はメニュー名一覧の配列要素数

# 全探索
●考える（注目メニューまで注文一覧と値段でカロリーを）
	もし，注目メニュー＝メニュー数ならば
		# これ以上メニューはないので、
		# カロリーが最大の場合には出力する変数を書き換える
		もしカロリーが最終カロリー以上ならば
			最終カロリーはカロリー
			最終注文一覧は注文一覧
			最終値段は値段
		戻る

	# 注目要素を採用したときの値段
	採用時値段は値段＋値段一覧[注目メニュー]

	# 注目メニューを選ぶと値段オーバーするか
	もし、採用時値段が1000円以下ならば
		# 注目要素を選んでも値段がオーバーしないので
		# 注目要素は選ぶことを考える
		採用時カロリーはカロリー＋カロリー一覧[注目メニュー]
		採用時注文一覧は注文一覧＆改行＆メニュー名一覧[注目メニュー]
		注目メニュー+1まで採用時注文一覧と採用時値段で採用時カロリーを考える

	# 注目メニューは選ばないとき
	注目メニュー+1まで注文一覧と値段でカロリーを考える

# よーく考える
0まで空と0円で0を考える

# 出力
出力注文一覧は最終注文一覧の配列上下空行削除して『と』で配列結合
「最終カロリーは{最終カロリー}kcal
最終値段は{最終値段}円
最終注文一覧は{出力注文一覧}です」と言う

終わり
```
関数定義は「●」で始めて，引数リストを後ろにつけます．
なでしこには「助詞」という概念があって，引数に助詞をつけて渡すことになっています．助詞がキーワード引数のような役割を果たしていて，順序を入れ替えても問題なく関数を叩けるわけです．
複数の助詞を同じ仮引数に割り当てることもできて，例えば『「こんにちは」と言う』と『「こんにちは」を言う』は同じ動作です．

余談ですが「言う」と「いう」は別の関数となっていて，前者がなでしこが内部で実装しているメッセージボックスです．こちらは右クリックメニューでメッセージをコピーできるなどちょっと便利．

「円」とかは勝手に無視してくれるので，理解しやすい（？）コードが書けるということになっています．

20秒ほどで答えは出てくるのですが，**20メニュー削っているのでこれはダメ．**
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/37191/d41635ce-84a7-7c33-341c-2ce6b3a2880f.png)

# DP

動的計画法(DP)で解ける，という話はTeXの方が既にされているので省略します．
なでしこでDP書いたら初心者でも何やってるか追いやすいんじゃないかと期待して，深夜のテンションで書きました．

```nadesiko:DP.nako
# 読み込み
データベース保存先は母艦パス＆「saizeriya.db」
データベースはデータベース保存先をSQLITE3開く
「SJIS」にSQLITE3出力コード設定
データ＝データベースで「select * from menu」をSQLITE3実行してCSV取得

# 見出し列の削除
データの0個目を配列削除

# 値段とメニュー名とカロリーの抽出
メニュー名一覧はデータの1個目を表列取得
値段一覧はデータの4個目を表列取得
カロリー一覧はデータの5個目を表列取得

# 初期化
メニュー数はメニュー名一覧の配列要素数
最適選択時カロリー表[メニュー数][1000] = 0
最適選択時値段差表[メニュー数][1000] = 0

# それぞれのメニューについて、ある値段のときに注文すべきか考える
注目メニューで0からメニュー数-1まで繰り返す
	注目メニュー値段は値段一覧[注目メニュー]
	注目メニューカロリーはカロリー一覧[注目メニュー]
	次メニューは注目メニュー+1
	# 「ある値段」を順番に検討する
	値段で0円から1000円まで繰り返す
		# 注目メニューを選ばなかったときの値段は
		非採用時カロリーは最適選択時カロリー表[注目メニュー][値段]
		# 考えている値段が注目メニューの値段を超えているか検討
		もし、値段が注目メニュー値段以上ならば
			# 注目メニューを注文するのにお金を払うとして、その金額を払う直前での最適選択を考える
			採用時残金は値段-注目メニュー値段
			# そのメニューを選んだときの最適選択した場合でのカロリー
			採用時カロリーは最適選択時カロリー表[注目メニュー][採用時残金]+注目メニューカロリー
			
			# 結局そのメニューは選ぶべきだったのか
			もし、採用時カロリーが非採用時カロリー以下ならば
				最適選択時カロリー表[次メニュー][値段]は非採用時カロリー
				最適選択時値段差表[次メニュー][値段]は値段
			違えば
				最適選択時カロリー表[次メニュー][値段]は採用時カロリー
				最適選択時値段差表[次メニュー][値段]は採用時残金
		違えば # そもそも買えない
			最適選択時カロリー表[次メニュー][値段]は非採用時カロリー
			最適選択時値段差表[次メニュー][値段]は値段

最終カロリーは最適選択時カロリー表[メニュー数][1000円]

# 各メニューを注文したのかを確認
最終注文一覧は空
最終値段は0円
値段は1000円
注目メニューでメニュー数-1から0まで繰り返す
	次メニューは注目メニュー+1
	注目メニュー値段は値段一覧[注目メニュー]
	採用時残金は値段-注目メニュー値段
	もし、最適選択時値段差表[次メニュー][値段]が採用時残金ならば
		最終注文一覧にメニュー名一覧[注目メニュー]を配列追加
		最終値段は最終値段＋注目メニュー値段
	値段は最適選択時値段差表[次メニュー][値段]

# 出力
出力注文一覧は最終注文一覧を『と』で配列結合
「最終カロリーは{最終カロリー} kcal
最終値段は{最終値段}円
最終注文一覧は{出力注文一覧}です」と言う

終わり
```

Qiitaはなでしこのシンタックスハイライトに対応していないため読みづらいので，なでしこエディタで開いて大事なあたりのスクリーンショットを貼っておきます．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/37191/2b9f22dc-a5de-97cf-461d-844d60b085d5.png)

先人たちと同じ答えが返ってきているので一安心．なでしこでも1秒かからず．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/37191/f9b7661e-4ab6-6a6f-6bb5-7d727059a17a.png)

# 結論

DPは別になでしこで書いてもわかりやすくなるわけではないし，むしろC++とかで書いたほうがわかりやすい．
でもなでしこ便利だから使ってみてほしい・・・．