読者です 読者をやめる 読者になる 読者になる

CTOからの挑戦状2016 2ndを手伝った際に書いたPythonコードを晒してみる。

この記事はVOYAGE GROUPのAdvent Calendar 2016 11日目の記事として書かれています。 techlog.voyagegroup.com

みなさんこんにちは。ara_ta3 と言います。
今回はVOYAGE GROUPとサポーターズで行ったイベント
CTOからの挑戦状 2016 2nd にて採点したり、
学生向けに解答を用意したりしたのでその時の話をします。

supporterz.jp

参加された学生の方に参考になれば幸いですし、
今回はPythonでのLintや型ヒント + mypyの実装も記載しているので、
それらの使い方の参考にもなれば幸いです。

CTOからの挑戦状 2016 2nd とは?

  • 問題を解いて賞金が得られる
  • 問題はLV1, LV2, LV3がある
  • LV1は早い者勝ちで賞金 が得られる
  • LV2, LV3はCTO含む3人のエンジニアがコードを読み、評価順に基づいて賞金が得られる
    • 例えば
      • 変数や、メソッド、関数の命名がある程度適切か
      • 適度に処理がメソッド、関数に切り分けられているか
      • テストケースは適切か
    • みたいなところを見たりしました。

問題について

LV1 ~ LV3の問題はgistに記述していて、それぞれ下記URLになります。
問題はピザや寿司の割引クーポンの最適化問題という感じですね。

Level.1 - 2016 2nd - Challenge CTO of VOYAGE GROUP · GitHub

Level.2 - 2016 2nd - Challenge CTO of VOYAGE GROUP · GitHub

Level.3 - 2016 2nd - Challenge CTO of VOYAGE GROUP · GitHub

これらの問題を自分も解いてみたので、
そのコードで気をつけた所などをつらつらと書いてみようかと思います。
Pythonの解答数が最も多かったので、私もPythonで書いてみました。
Versionは3.5.2です。

書いてみたコード

準備

Python詳しくなかったので、開発環境周りをとりあえず調べてみました。

[PR]Pythonの環境については別途Qiitaで記事も書いているので是非ご覧いただければと・・・ qiita.com

ざっとやったこととしては

みたいなところです。

LV1

問題は簡単に言うと、
複数の割引クーポンを使ってピザ・寿司の支払金額を出来る限り少なくすると言ったものでした。

問題
Level.1 - 2016 2nd - Challenge CTO of VOYAGE GROUP · GitHub

私の解答
CTO Challenge 2016 2nd LV1 · GitHub

主に書いたコードは下記のような感じです。
単純に高い割引額のクーポンから使って行けば良さそうですね。
とりあえずLV1のケースをテストしました。
for文の中くらいのスコープなら適当な変数名でもいいけど、
少し広めなスコープのときは妥当そうな命名をつけるようにしました。

また、"準備" の部分に色々書いたりしましたが、
このタイミングではあまり複雑じゃなかったのでmypyは入れませんでした。

lowest_amount_for_using_coupon = 1000


def select_optimum_combination(amount, coupons):
    if amount <= lowest_amount_for_using_coupon:
        return []
    sorted_coupons = sorted(coupons, reverse=True)
    rest = amount
    used_coupons = []
    for c in sorted_coupons:
        if rest < c:
            break
        rest -= c
        used_coupons.append(c)

    return used_coupons


def test_select_optimum_combination_case1():
    selected = select_optimum_combination(1000, [500, 500, 200, 100, 100, 100])
    assert selected == []


def test_select_optimum_combination_case2():
    selected = select_optimum_combination(1210, [])
    assert selected == []


def test_select_optimum_combination_case3():
    selected = select_optimum_combination(1210, [500, 500, 200, 100, 100, 100])
    assert selected == [500, 500, 200]


def test_select_optimum_combination_case4():
    selected = select_optimum_combination(1530, [500, 500, 200, 100, 100, 100])
    assert selected == [500, 500, 200, 100, 100, 100]


def test_クーポンが降順になっていなくても割引額が高い順に割り引いてくれること():
    selected = select_optimum_combination(1530, [500, 200, 100, 500, 100, 100])
    assert selected == [500, 500, 200, 100, 100, 100]

LV2

LV2では少し仕様が増えました。
入力がLV1では金額でしたが、メニューに変わりました。
また、クーポンの使用回数に制限が加わりました。
さらにメニューの種類によって使えるクーポンが増えました。
めんどくさいですね

問題
Level.2 - 2016 2nd - Challenge CTO of VOYAGE GROUP · GitHub

私の解答
CTO Challenge 2016 2nd LV2 · GitHub

CouponSelectorというサービスクラスにロジックを入れました。
テスト済のLV1で使った関数はそのまま利用したかったので、
CouponSelectorクラスのクラスメソッドとしてリファクタリングしました。
このタイミングで型ヒントを入れてみました。
メソッドの引数にCouponやMenuクラスを含むDictやListなどの少し複雑な型を渡したくなり、
それら以外は渡さないで欲しいことを明示的にわかるようにしたくて入れました。
Python3.5.2現在では型ヒントだけではPythonの処理系はなにもしてくれないのですが、
mypyで意図しない型の入力がないか確認しています。

coupon_selector.py

from typing import List, Dict
from functools import reduce
from collections import Counter
from menu import Menu

Coupon = int


class CouponSelector():
    def __init__(self,
                 limitation_of_coupons: Dict[Coupon, int],
                 coupons_available_for_pizza: List[Coupon],
                 lowest_amount_for_using_coupon: int
                 ) -> None:
        self.limitation_of_coupons = limitation_of_coupons
        self.coupons_available_for_pizza = coupons_available_for_pizza
        self.lowest_amount_for_using_coupon = lowest_amount_for_using_coupon

    def select_optimum_combination_by_menus(
            self,
            menus: List[Menu],
            coupons: List[Coupon]):

        amount = reduce(lambda amount, m: amount + m.price, menus, 0)
        available_coupons = _filter_limited_coupons(
            coupons,
            self.limitation_of_coupons
        )
        if not _pizza_exists(menus):
            available_coupons = [c for c in available_coupons
                                 if c not in self.coupons_available_for_pizza]
        return self.select_optimum_combination(amount, available_coupons)

    def select_optimum_combination(self, amount: int, coupons: List[Coupon]):
        if amount <= self.lowest_amount_for_using_coupon:
            return []
        sorted_coupons = sorted(coupons, reverse=True)
        rest = amount
        used_coupons = []
        for c in sorted_coupons:
            if rest < c:
                break
            rest -= c
            used_coupons.append(c)

        return used_coupons


def _pizza_exists(menus: List[Menu]):
    return any(m.is_pizza() for m in menus)


def _filter_limited_coupons(
        coupons: List[Coupon],
        coupon2limit: Dict[Coupon, int]):
    counter = Counter(coupons)
    for c, n in counter.items():
        counter[c] = min(coupon2limit[c], n)
    return list(counter.elements())

menu.py

from typing import Dict, List, Tuple


class Menu(object):
    def __init__(self, name, price):
        self.name = name
        self.price = price

    def is_pizza(self):
        return type(self) == PizzaMenu


class PizzaMenu(Menu):
    def __init__(self, name, size, price):
        super(PizzaMenu, self).__init__(name, price)
        self.size = size


class SideMenu(Menu):
    def __init__(self, name, price):
        super(SideMenu, self).__init__(name, price)

テストケースはこちら

LV3

LV3ではセットメニューという概念が加わりました。
クーポンを使うよりもセットメニューの方がお得など、なんとなくありそうな仕様ですね。
セットメニュー特定のサイドメニューが無料になるものもあれば、
任意のサイドメニューが無料になるもの、
具体的な割引額が決まっているものもあります。
またセットメニューを頼める時間帯が決まっているものもあるようです。
仕様がめんどくさいですね。

クーポンの割引額とセットメニューの割引額をそれぞれで出して両者を比較すればいいかなと考えました。
なので比較する部分を除くと、LV2から追加されたのはSetMenuのディスカウント額を計算するプログラムのみです。

問題
Level.3 - 2016 2nd - Challenge CTO of VOYAGE GROUP · GitHub

私の解答
CTO Challenge 2016 2nd LV3 · GitHub

SetMenuDiscounterというサービスクラスを作成しました。
処理の流れは
注文されたメニューと注文された時間から利用可能なセットメニュー一覧を取得し、
一覧の中で最も高い割引額のセットメニューを決めて返す。
と言ったものです。
工夫したのは、クーポンが利用可能か判定する部分を関数で表現しました。
仕様に1種類しかないので、抽象化するにはまだ早いかなと考えたためです。
今見返してみて、 SetMenuDiscount クラスのどのメソッドを見るべきが悩んだので、
privateメソッドかどうかも意識して書けばよかったなと思いました。

from datetime import datetime
from typing import List, Tuple, Callable
from menu import Menu


class SetMenuDiscounter():
    def __init__(self, discounts: List[SetMenuDiscount])->None:
        self.discounts = discounts

    def decide_discount(self,
                        ordered: List[Menu],
                        current_time: datetime
                        )->Tuple[SetMenuDiscount, int]:

        availables = [d for d in self.discounts
                      if d.is_available(ordered, current_time)]
        if not availables:
            return (None, 0)

        best, *rest = availables
        best_discount = best.calculate_discount(ordered)
        for d in rest:
            p = d.calculate_discount(ordered)
            if best_discount < p:
                best = d
                best_discount = p
        return (best, best_discount)


class SetMenuDiscount(object):
    def __init__(self, name: str,
                 required_menus_combinations: List[List[Menu]],
                 available_time_rules: List[Callable[[datetime], bool]],
                 discount_target_menus: List[Menu],
                 discount: int = None)->None:
        self.name = name
        self.required_menus_combinations = required_menus_combinations
        self.available_time_rules = available_time_rules
        self.discount_target_menus = discount_target_menus
        self.discount = discount

    def is_available(self, ordered_menus: List[Menu],
                     ordered_time: datetime)->bool:
        return self.in_available_period(ordered_time) \
            and self.is_matched(ordered_menus)

    def is_matched(self, ordered_menus: List[Menu])->bool:
        ordered_menu_set = set(ordered_menus)
        for combination in self.required_menus_combinations:
            c = set(combination)
            if c.intersection(ordered_menu_set) == c:
                return True
        return False

    def in_available_period(self, ordered_time: datetime)->bool:
        if self.available_time_rules is None:
            return True
        return any(map(lambda fn: fn(ordered_time), self.available_time_rules))

    def get_target_discount_menus(self, ordered_menus: List[Menu])->List[Menu]:
        t = set(self.discount_target_menus).intersection(set(ordered_menus))
        return list(t)

    def has_amount_discounts(self)->bool:
        return self.discount is not None

    def has_menu_discounts(self)->bool:
        return len(self.discount_target_menus) > 0

    def calculate_discount(self, ordered_menus: List[Menu])->int:
        price = 0
        if self.has_menu_discounts():
            menus = self.get_target_discount_menus(ordered_menus)
            prices = map(lambda m: m.price, menus)
            m = max(prices, default=0)
            price = max(price, m)
        if self.has_amount_discounts():
            price = max(price, self.discount)
        return price

テストケース

まとめ

CTOからの挑戦状 2016 2ndの際に書いたLV1, LV2, LV3のコードを晒してみました。
それぞれほんの少しですが、意図や工夫した点を書いてみました。
工夫した点を少しまとめると

  • coreなコード(ここで言うとcoupon selector)に仕様的なものが含まれないようにしました。
    • クーポンの具体的な割引額や使える枚数の制限など。
  • パフォーマンスを考えるよりも処理の流れがわかりやすくなるように心がけました。
    • クーポンが1億枚手元にあるからそこから選ぼうということはあまりないかなと考えてます。
  • 変数などの命名は出来る限りわかりやすくするようにしました。
  • Lintや型チェックなどを入れてテストを書かなくてもエラーがある程度わかるようにしました。

説明がわかりづらい、ここなんでこんなクソ実装なんだ!
とかありましたら是非我らがAJITOでお話でもできればと思うので、お声がけください!w

voyagegroup.com

感想

  • テストケースに不備があったらごめんなさい・・・指摘頂ければ幸いです。
  • あまり触ったことないコードに触るとき形(コーディング規約やLintなど)から入るといい感じにそれっぽくかけるから良い
    • ただし、エディタ設定沼にはまらないように注意
  • CTOからの挑戦状のコード書くの大変・・・w
  • 型ヒントとライブラリで頑張るならコンパイルでわかる(言語がサポートしてくれている)方が個人的にはいいなぁ