cto-challenge-level2.php

<?php

/**
 * 入力を{ 割引額 => 枚数 }の形に変える
 * 枚数制限に引っかかる分を取り除く
 * 同時利用可能でないクーポンリストを分ける（複数のクーポンリストにする）
 * 複数のクーポンリストから割引額が多いものを返す。
 * @param $amount
 * @param $myCouponList
 * @return array
 */
function selectOptimalCoupons($amount, $myCouponList)
{
    $parsedCoupons              = parseInput($myCouponList);
    $availableCoupons           = filterUnAvailableCoupons($parsedCoupons);
    $candidatesOfOptimalCoupons = divideCannotSameTimeUseCoupons($availableCoupons);
    return selectMaxDiscountCoupons($amount,$candidatesOfOptimalCoupons);
}

function parseInput(array $couponList)
{
    $parsed = [];
    foreach($couponList as $discount)
    {
        if( array_key_exists($discount, $parsed) )
        {
            $parsed[$discount]++;
        }
        else
        {
            $parsed[$discount] = 1;
        }
    }
    $sorted   = $parsed;
    krsort($sorted);
    return $sorted;
}

function filterUnAvailableCoupons($couponList)
{
    $maxOfCoupons = [
        100 => 3,
        500 => 1,
    ];

    $availableCoupons = [];
    foreach($couponList as $discount => $nCoupon)
    {
        if(!array_key_exists($discount, $maxOfCoupons))
        {
            $availableCoupons[$discount] = $nCoupon;
            continue;
        }
        $maxOfCoupon = $maxOfCoupons[$discount];
        $availableCoupons[$discount] = ($maxOfCoupon < $nCoupon) ?
            $maxOfCoupon:
            $nCoupon;
    }
    return $availableCoupons;
}

function divideCannotSameTimeUseCoupons(array $availableCouponList)
{
    $canSameTimeUseWithOthersOrNot = [
        50 => true,
        100 => true,
        500 => false,
    ];
    $original = $availableCouponList;
    $candidates = [];
    foreach(array_keys($availableCouponList) as $discount)
    {
        if( $canSameTimeUseWithOthersOrNot[$discount] === false)
        {
            $candidates[] = [$discount => $availableCouponList[$discount]];
            unset($original[$discount]);
        }
    }
    $candidates[] = $original;
    return $candidates;
}

function selectMaxDiscountCoupons($amount, array $candidates)
{
    $maxDiscount = 0;
    $usedCoupons = [];
    foreach( $candidates as $coupons)
    {
        list($discount, $tmpUsedCoupons) = findSumDiscountAndUsedCoupons($amount, $coupons);
        if($maxDiscount < $discount)
        {
            $maxDiscount = $discount;
            $usedCoupons = $tmpUsedCoupons;
        }
    }
    return $usedCoupons;
}

function findSumDiscountAndUsedCoupons($amount, $coupons)
{
    $usedCoupons = array_fill_keys(array_keys($coupons), 0);
    $sumDiscount = 0;
    foreach( $coupons as $discount => $nCoupon )
    {
        while($amount >= $discount && ($nCoupon - $usedCoupons[$discount]) > 0)
        {
            $amount -= $discount;
            $sumDiscount += $discount;
            $usedCoupons[$discount]++;
        }
    }
    return [$sumDiscount, $usedCoupons];
}

<?php
require_once "level2.php";

class Test_Level2 extends PHPUnit_Framework_TestCase
{

    /**
     * @dataProvider data_入力に想定される支払金額とクーポンと出力結果
     */
    public function test_selectOptimalCouponsが仕様を満たすこと(
        $amount,
        $myCouponList,
        $expected
    )
    {
        $actual = selectOptimalCoupons($amount,$myCouponList);
        $this->assertEquals($expected, $actual);
    }

    public function data_入力に想定される支払金額とクーポンと出力結果()
    {
        return [
            [
                100,
                [],
                [],
            ],
            [
                100,
                [50,50,100],
                [100 => 1, 50 => 0],
            ],
            [
                470,
                [50,50,50,100,100,100,100,100,500],
                [100 => 3,50 => 3],
            ],
            [
                590,
                [50,100,100,100,100,500,500],
                [500 => 1],
            ],
            [
                1230,
                [50,50,50,50,50,50,100,100,100,100,100,500,500],
                [100 => 3, 50 => 6],
            ],
            [
                550,
                [50,50,50,50,50,50,100,100,100,100,100,500,500],
                [100 => 3, 50 => 5],
            ],

        ];
    }
}