この記事はVOYAGE GROUPのAdvent Calendar 2016 11日目の記事として書かれています。 techlog.voyagegroup.com
みなさんこんにちは。ara_ta3 と言います。
今回はVOYAGE GROUPとサポーターズで行ったイベント
CTOからの挑戦状 2016 2nd にて採点したり、
学生向けに解答を用意したりしたのでその時の話をします。
参加された学生の方に参考になれば幸いですし、
今回は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
ざっとやったこととしては
- コーディング規約を読む
- flake8を入れてLintをかけるようにする
- 型ヒントをつけてmypyを利用して型ヒントに合わない場合エラーが出るようにする
みたいなところです。
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)
テストケースはこちら
- https://gist.github.com/ara-ta3/3e3a97380a56f4fbb016f51e938c2c57#file-lv1_test-py
- https://gist.github.com/ara-ta3/3e3a97380a56f4fbb016f51e938c2c57#file-lv2_test-py
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でお話でもできればと思うので、お声がけください！ｗ
感想
- テストケースに不備があったらごめんなさい・・・指摘頂ければ幸いです。
- あまり触ったことないコードに触るとき形(コーディング規約やLintなど)から入るといい感じにそれっぽくかけるから良い
- ただし、エディタ設定沼にはまらないように注意
- CTOからの挑戦状のコード書くの大変・・・ｗ
- 型ヒントとライブラリで頑張るならコンパイルでわかる(言語がサポートしてくれている)方が個人的にはいいなぁ
