Skip to content

Instantly share code, notes, and snippets.

@ara-ta3
Created December 29, 2014 14:16
Show Gist options
  • Save ara-ta3/77836ff77836178b1601 to your computer and use it in GitHub Desktop.
Save ara-ta3/77836ff77836178b1601 to your computer and use it in GitHub Desktop.
<?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];
}
@ara-ta3
Copy link
Author

ara-ta3 commented Dec 29, 2014

<?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],
            ],

        ];
    }
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment