Create a gist now

Instantly share code, notes, and snippets.

@ara-ta3 /Makefile Secret
Last active Jan 3, 2017

CTO Challenge 2016 2nd LV1
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)
target_coupons = sorted_coupons
candidates = []
while target_coupons:
selected = _select_optimum_combination(amount, target_coupons)
candidates.append(selected)
highest_discount = target_coupons[0]
target_coupons = [c for c in target_coupons if c != highest_discount]
return max(candidates, key=lambda cs: sum(cs)) if candidates else []
def _select_optimum_combination(amount, coupons):
rest = amount
used_coupons = []
for c in 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]
def test_200円クーポンのみの方がオトクな場合():
selected = select_optimum_combination(1200, [500, 200, 200, 200, 200, 200, 200])
assert selected == [200, 200, 200, 200, 200, 200]
pip=bin/pip
python=bin/python
pep8=bin/pep8
pyflakes=bin/pyflakes
pytest=bin/pytest
run: $(python)
$< main.py
test: $(pytest)
$< main.py
install: $(pip)
$< install -r requirements.txt
$(pytest): $(pip)
$(MAKE) install
$(pyflakes): $(pip)
$(MAKE) install
$(pep8): $(pip)
$(MAKE) install
$(python):
virtualenv . -p python3
$(pip):
virtualenv . -p python3
clean:
rm -rf ./bin
rm -rf ./lib
rm -rf ./include
pytest
flake8
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment