CTO Challenge 2016 2nd LV1

main.py

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]

Makefile

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

requirements.txt

pytest
flake8