栄養バランスの完璧な学食を検索する(Python3,BeautifulSoup)

#初めに
今年から大学生になりました。お昼ご飯に生協の食堂をちょくちょく利用しています。
生協の食堂のレシートには、選んだ学食の栄養バランスを示す「３群点数」という３つの数字が書かれています。(写真の赤線部。詳しい説明は[生協のサイト](http://www.univcoop.or.jp/service/food/three.html)をどうぞ)

<img src="https://qiita-image-store.s3.amazonaws.com/0/161252/f0f767ab-4ee6-8080-8ccd-421259e1bbb5.jpeg" width=33%>


レシートによると、一食での３群点数の目安は、男性の場合赤2点緑１点黄7点、女性の場合赤2点緑１点黄4点以上のようです。
さて、ここで疑問が生まれます。はたしてこの目安ぴったりとなるような学食は存在するのでしょうか？存在するとしたら、それはどんな組み合わせなのでしょうか？学食の3群点数は、それぞれのメニューが持つ３群点数の和として計算できます。そして幸いなことに、メニューごとの３群点数は[学食どっとコープ](http://gakushoku.coop)というサイトで取得できます。ここからデータをスクレイピングして、そのような学食が存在するのか検証しました。
#注意
・この記事では男性の3群点数(赤2点緑１点黄7点)を目安とします。
・検証する学食はあくまで「3群点数が目安と一致する」ものであり、実際に健康的な学食とはかぎりません。
・記事内では、メニューを「食堂で売っている各品々」という意味で、学食を「複数のメニューを組み合わせたもの」という意味で使っています
・同じメニューを二皿以上取ることはないと仮定しています。


#スクレイピング
スクレイピングには主にPython3とBeautifulsoupを使いました。http://gakushoku.coop/list_search.php へアクセスすると、全メニューの一覧が表示されます。ここから、個別のメニュー詳細ページのリンクを取得→Beautifulsoupで解析という流れでデータを集めました。今回必要なのはメニューの名前と3群点数のみですが、ついでなのでそのほかのデータも取得しています。

```python:scraping.py

#coding: utf-8
from urllib.request import urlopen
from bs4 import BeautifulSoup
import time
import pickle

# メニューに関する各種情報を取得する関数
def get_menu_data(soup, data):
    if data == "メニュー名":
        return soup.find("h4", class_="tt_clr_orange setmenutitle").text
    t = soup.find("img", alt=data).find_next("td")
    try:
        return [tag.text for tag in t.find_all("strong")]
    except:
        return "-"


def main():
    # メニュー一覧ページからそれぞれのメニューへのリンクを取得
    url = "http://gakushoku.coop/list_search.php"
    soup = BeautifulSoup(urlopen(url), "lxml")
    menu_links = []
    for a in soup.find_all("a"):
        menu_link = a.get("href")
        if menu_link and "menu_detail" in menu_link and menu_link not in menu_links:
            menu_links.append(menu_link)

    menus = []  # メニューの情報を保存するリスト
    base = "http://gakushoku.coop/"
    for i, menu_link in enumerate(menu_links):
        url = base+menu_link
        soup = BeautifulSoup(urlopen(url), "lxml")
        # メニューに関する情報を取得
        name = get_menu_data(soup, "メニュー名")
        price = get_menu_data(soup, "税込組価")
        calorie = get_menu_data(soup, "エネルギー量")
        allergen = get_menu_data(soup, "アレルギー物質")
        points = get_menu_data(soup, "3群点数")
        salt = get_menu_data(soup, "塩分")
        # 情報が入った辞書型オブジェクトを作り、リストに格納
        menus.append({"name": name, "price": price, "calorie": calorie,
                      "allergen": allergen, "points": points, "salt": salt})
        print("%03d/%d" % (i+1, len(menu_links)))
        time.sleep(1)  # サーバの負荷軽減のため
    # pickleとして保存
    with open("menus.pickle", "wb") as f:
        pickle.dump(menus, f)


if __name__ == '__main__':
    main()
```


これを実行すると、`menus.pickle`というファイルが作られます。これは辞書オブジェクトを要素に持つリスト、`menus`をpickle化したものです(pickleについては[公式ドキュメント](https://docs.python.jp/3.6/library/pickle.html)をご覧ください)。
`menus`内の辞書オブジェクトは次のような形をしています。

```
{'name': '若鶏の唐揚げ（Fried chicken ）', 'price': ['302'], 'calorie': ['361'], 'allergen': ['卵、小麦、乳、鶏肉、大豆'], 'p
oints': ['2.5', '0.1', '1.9'], 'salt': ['1.4']}
```
`'points'`の値が3群点数です。[赤,緑,黄]の順番で並んでいます。（文字列のまま格納していますが、数値のほうがいいかもしれません…）これらのデータを使い、3群点数が目安通りとなるような学食を探していきます。


#検索
３群点数をキーに、その点数ちょうどになるような学食を値に持つ辞書を作り、それをひたすら更新することで検索を行いました（説明下手）
実際のコードをご覧ください。

```python:search.py
#coding: utf-8
import pickle
from copy import deepcopy
# 点数同士の足し算にはdecimalを使う（理由は後述）
from decimal import Decimal


# 3群点数同士を足し算する関数
def add(a, b):
    ret = [Decimal(a[0])+Decimal(b[0]), Decimal(a[1]) +
           Decimal(b[1]), Decimal(a[2])+Decimal(b[2])]
    return ret


# ある3群点数の各数値が別の３群点数以下であるかを返す関数
def is_lower(a, b):
    return a[0] <= b[0] and a[1] <= b[1] and a[2] <= b[2]


def main():
    # pickle化したmenusを復元
    with open("menus.pickle", "rb") as f:
        menus = pickle.load(f)
    # menusを黄色の点数順にソート
    menus.sort(key=lambda x: float(x["points"][2]))
    # 検索結果を格納する辞書
    table = {}
    table.update({repr([0.0, 0.0, 0.0]): [[0.0, 0.0, 0.0], [[]]]})
    loop_count = 0
    is_changed = True
    while is_changed:
        is_changed = False
        copied_table = deepcopy(table)
        for values in copied_table.values():
            current_points = values[0]  # 現在注目している要素の3群点数
            lunches = values[1]  # 上の3群点数になる学食
            for lunch in lunches:
                for menu in menus:
                    # menusをソートしているので、現在のmenuとcurrent_pointsの黄点の和が7.0を超えたらそれ以降は考えなくてもいい。
                    if add(current_points, menu["points"])[2] > 7.0:
                        break
                    # menuが現在の学食でまだ選択されておらず、学食とメニューの3群点数の和が目安よりも少ないなら
                    if menu["name"] not in lunch and is_lower(add(current_points, menu["points"]), [2.0, 1.0, 7.0]):
                        # 現在の学食にmenuを加えて新しい学食を作る
                        copied_lunch = deepcopy(lunch)
                        copied_lunch.append(menu["name"])
                        copied_lunch.sort()
                        # 新しい学食の3群点数を計算する
                        points = add(current_points, menu["points"])
                        key = repr(points)
                        # tableを更新
                        if key not in table:
                            table.update({key: [points, [copied_lunch]]})
                            is_changed = True
                        else:
                            if copied_lunch not in table[key][1]:
                                table[key][1].append(copied_lunch)
                                is_changed = True
        loop_count += 1
        # 一回のループごとに結果を保存する
        with open("result%02d.txt" % loop_count, "w") as f:
            if "[Decimal('2.0'), Decimal('1.0'), Decimal('7.0')]" in table:
                f.write(
                    repr(table["[Decimal('2.0'), Decimal('1.0'), Decimal('7.0')]"]))
            else:
                f.write("None")
            print("saved:result%02d.txt" % loop_count)


if __name__ == '__main__':
    main()


```
足し算にfloatを使ったところ、時々1+1=1.99999996のように計算結果に誤差が含まれたので、計算にはdecimalを使っています。
#結果
上記のコードを実行するとresultXX.txt(XXは数字)というファイルが作られます。これらの中には、最大でXX個のメニューを選べると仮定した場合の、条件を満たす学食が書かれています。PCのスペックとコーディング力不足のせいで、私の環境ではresult05.txtまでしか生成できませんでした（もっと効率よくコード書けそうな予感…）。result05.txtは次のような内容になっています。

```plaintext:result05.txt（一部）
[[2.0, 1.0, 7.0], [['オクラの巣ごもりたまご(Soft-boiled egg with chopped okra)', 'ポテト＆コーンサラダ（Potato and corn salad）', '（大）釜玉うどん（(Large size)Udon noodles with poached egg_ green onion_ nori and tenkasu）'], ['ほうれん草のおひたし（Boiled spinach with dried bonito（from Ishinomaki））', 'ほうれん草の巣ごもりたまご（Soft-boiled egg nested in boiled spinach with sesame paste）', 'ポテト＆コーンサラダ（Potato and corn salad）', '（大）釜玉うどん（(Large size)Udon noodles with poached egg_ green onion_ nori and tenkasu）'], ['ほうれん草のおひたし（Boiled spinach with dried bonito（from Ishinomaki））', 'ゆずと豆乳のレアチーズ(Citron and tofu flavored gelatin cheesecake)', 'ポテト＆コーンサラダ（Potato and corn salad）', '（大）釜玉うどん（(Large size)Udon noodles with poached egg_ green onion_ nori and tenkasu）'], ['かぼちゃ煮（Simmered pumpkin）', 'とろろ（Grated yam）', 'オクラの巣ごもりたまご(Soft-boiled egg with chopped okra)', '（大）釜玉うどん（(Large size)Udon noodles with poached egg_ green onion_ nori and tenkasu）'], ['とろろ（Grated yam）', 'オクラの巣ごもりたまご(Soft-boiled egg with chopped okra)', 'レンコンきんぴら（Lotus root saut?ed in sugar and soy sauce）', '（大）釜玉うどん（(Large size)Udon noodles with poached egg_ green onion_ nori and tenkasu）'], ['かぼちゃ煮（Simmered pumpkin）', 'オクラの巣ごもりたまご(Soft-boiled egg with chopped okra)', '野菜生活１００（Mixed juice of vegetables and the fruit）', '（大）釜玉うどん（(Large size)Udon noodles with poached egg_ green onion_ nori and tenkasu）'], ['オクラの巣ごもりたまご(Soft-boiled egg with chopped okra)', 'レンコンきんぴら（Lotus root saut?ed in sugar and soy sauce）', '野菜生活１００（Mixed juice of vegetables and the fruit）', '（大）釜玉うどん（(Large size)Udon noodles with poached egg_ green onion_ nori and tenkasu）'], ['オクラの巣ごもりたまご(Soft-boiled egg with chopped okra)', 'チーズババロアシュークリーム(Cream puff with cheese bavarois) ', 'ポテト＆コーンサラダ（Potato and corn salad）', '醤油ラーメン（ramen noodles in soy-sauce flavored soup）'], ['ほうれん草のおひたし（Boiled spinach with dried bonito（from Ishinomaki））', 'ハニーマスタードチキン（Chicken cutlets with honey mustard sauce）', 'ポテト＆コーンサラダ（Potato and corn salad）', 'ワカメそば（Soba noodles with wakame seaweed）'], ['ほうれん草のおひたし（Boiled spinach with dried bonito（from Ishinomaki））', 'ハニーマスタードチキン（Chicken cutlets with honey mustard sauce）', 'ポテト＆コーンサラダ（Potato and corn salad）', 'ワカメうどん（Soba noodles with wakame seaweed）'], ['かけそば（Plain soba noodles）', 'きんぴらごぼう（Sauteed burdock kimpira style）', 'ハニーマスタードチキン（Chicken cutlets with honey mustard sauce）', 'ポテト＆コーンサラダ（Potato and corn salad）'], ['きつねそば（Zaru soba/udon （cool soba/udon noodles））', 'ひじき煮（Boiled hijiki （edible seaweed））', 'アスパラクリーミーカツ（Ham cutlet filled with asparagus and cream）', 'ポテト＆コーンサラダ（Potato and corn salad）'], ['アスパラクリーミーカツ（Ham cutlet filled with asparagus and cream）', 'ハンバーグ（照り焼きソース）(Hamburger steak with teriyaki sauce)', 'ポテト＆コーンサラダ（Potato and corn salad）', '白身魚フライ(Fried white meat fish)'], ['かき揚げそば（Soba noodles with mixed tempura）', 'ブリ照り煮（Boiled yellowtail with soy sauce）', 'ポテト＆コーンサラダ（Potato and corn salad）', '豆腐とわかめの味噌汁（Miso soup）'],...

```

これを見やすいように成型すると、こんな感じになります。

```plaintext:result05(edited).txt（一部）
オクラの巣ごもりたまご(Soft-boiled egg with chopped okra),ポテト＆コーンサラダ（Potato and corn salad）,（大）釜玉うどん（(Large size)Udon noodles with poached egg_ green onion_ nori and tenkasu）
ほうれん草のおひたし（Boiled spinach with dried bonito（from Ishinomaki））,ほうれん草の巣ごもりたまご（Soft-boiled egg nested in boiled spinach with sesame paste）,ポテト＆コーンサラダ（Potato and corn salad）,（大）釜玉うどん（(Large size)Udon noodles with poached egg_ green onion_ nori and tenkasu）
ほうれん草のおひたし（Boiled spinach with dried bonito（from Ishinomaki））,ゆずと豆乳のレアチーズ(Citron and tofu flavored gelatin cheesecake),ポテト＆コーンサラダ（Potato and corn salad）,（大）釜玉うどん（(Large size)Udon noodles with poached egg_ green onion_ nori and tenkasu）
かぼちゃ煮（Simmered pumpkin）,とろろ（Grated yam）,オクラの巣ごもりたまご(Soft-boiled egg with chopped okra),（大）釜玉うどん（(Large size)Udon noodles with poached egg_ green onion_ nori and tenkasu）
とろろ（Grated yam）,オクラの巣ごもりたまご(Soft-boiled egg with chopped okra),レンコンきんぴら（Lotus root saut?ed in sugar and soy sauce）,（大）釜玉うどん（(Large size)Udon noodles with poached egg_ green onion_ nori and tenkasu）
かぼちゃ煮（Simmered pumpkin）,オクラの巣ごもりたまご(Soft-boiled egg with chopped okra),野菜生活１００（Mixed juice of vegetables and the fruit）,（大）釜玉うどん（(Large size)Udon noodles with poached egg_ green onion_ nori and tenkasu）
オクラの巣ごもりたまご(Soft-boiled egg with chopped okra),レンコンきんぴら（Lotus root saut?ed in sugar and soy sauce）,野菜生活１００（Mixed juice of vegetables and the fruit）,（大）釜玉うどん（(Large size)Udon noodles with poached egg_ green onion_ nori and tenkasu）
オクラの巣ごもりたまご(Soft-boiled egg with chopped okra),チーズババロアシュークリーム(Cream puff with cheese bavarois),ポテト＆コーンサラダ（Potato and corn salad）,醤油ラーメン（ramen noodles in soy-sauce flavored soup）
ほうれん草のおひたし（Boiled spinach with dried bonito（from Ishinomaki））,ハニーマスタードチキン（Chicken cutlets with honey mustard sauce）,ポテト＆コーンサラダ（Potato and corn salad）,ワカメそば（Soba noodles with wakame seaweed）
ほうれん草のおひたし（Boiled spinach with dried bonito（from Ishinomaki））,ハニーマスタードチキン（Chicken cutlets with honey mustard sauce）,ポテト＆コーンサラダ（Potato and corn salad）,ワカメうどん（Soba noodles with wakame seaweed）
かけそば（Plain soba noodles）,きんぴらごぼう（Sauteed burdock kimpira style）,ハニーマスタードチキン（Chicken cutlets with honey mustard sauce）,ポテト＆コーンサラダ（Potato and corn salad）
.
.
.

```

一つひとつの行が条件を満たす学食の構成を表しています。全体の行数を数えたところ2855行あったので、現在生協の食堂では（少なくとも）2855通りの「健康的な」学食を食べることができるとわかりました。


#雑感・課題

- 主菜、副菜、主食がちゃんととある、おいしそうな学食が想像したより多かったです。
    - 「とんでもない組み合わせの学食がいっぱいあるんだろうな」と思っていたので、少し意外でした。
    - これとか普通においしそう。
    - ![gku.PNG](https://qiita-image-store.s3.amazonaws.com/0/161252/78c80ce2-8247-8d4a-19b1-7a9fa64b89b4.png)

- 一方で人間には思いつきそうもない組み合わせもあり、「この組み合わせで目安ぴったりになるの！？」と驚くこともありました。
    - 野菜がほとんどない＆デザートだらけの組み合わせ。ちゃんと目安ぴったりです。
    - ![gakushoku.PNG](https://qiita-image-store.s3.amazonaws.com/0/161252/3747c6d3-5986-f404-fcd1-20bcce32b2e6.png)
- 主に夜に作業していたので、お腹がすくことが多かったです！
    - 飯テロに自分から突っ込んでいくスタイル
 
今後はコードを今より効率的に書き換えて、5品より多く選択できる場合の組み合わせを調べたいです。また、3群点数だけではなく、塩分やカロリーなどを条件に入れた検索もやってみたいです。


今回使ったコードは[github](https://github.com/S-bite/lunch)に上げているので、もし必要な方がいましたらお使いください。