CTOからの挑戦状 L3

cto-challenge-level3.php

<?php

class CouponMaster
{
    const COUPON_TYPE_RATE = 'rate';
    const COUPON_TYPE_FIXED = 'fixed';

    private $coupons = [
        '10%' => [
            'type' => self::COUPON_TYPE_RATE,
            'discount' => 0.1,
            'maxUses' => 1,
        ],
        '500' => [
            'type' => self::COUPON_TYPE_FIXED,
            'discount' => 500,
            'maxUses' => 1,
        ],
        '700' => [
            'type' => self::COUPON_TYPE_FIXED,
            'discount' => 700,
            'maxUses' => 1,
            'sameTimeUses' => ['1000'],
            'terms' => ['2014-08-01 00:00:00', '2014-08-31 23:59:59'],
        ],
        '1000' => [
            'type' => self::COUPON_TYPE_FIXED,
            'discount' => 1000,
            'maxUses' => 1,
            'sameTimeUses' => ['700'],
            'terms' => ['2014-08-25 00:00:00','2014-08-27 23:59:59'],
        ],
    ];

    public function getDiscount($couponType, $amount)
    {
        if( !array_key_exists($couponType, $this->coupons) )
        {
            return 0;
        }

        $coupon = $this->coupons[$couponType];
        if( $coupon['type'] === self::COUPON_TYPE_RATE )
        {
            return $amount * $this->coupons[$couponType]['discount'];
        }
        return $this->coupons[$couponType]['discount'];
    }

    public function getSameTimeUseCoupons($couponType)
    {
        if( !array_key_exists($couponType, $this->coupons) )
        {
            return [];
        }
        if( !array_key_exists('sameTimeUses', $this->coupons[$couponType]))
        {
            return [];
        }
        return $this->coupons[$couponType]['sameTimeUses'];
    }

    public function getMaxNumberOfCoupon($couponType)
    {
        return array_key_exists($couponType, $this->coupons)?
            $this->coupons[$couponType]['maxUses']:
            0;
    }

    public function inAvailableTerm($couponType, \DateTime $currentTime = null)
    {
        if( !array_key_exists($couponType, $this->coupons) )
        {
            return false;
        }
        if( !isset($this->coupons[$couponType]['terms']) )
        {
            return true;
        }

        if( is_null($currentTime) )
        {
            $currentTime = new \DateTime();
        }

        list($start, $end) = $this->coupons[$couponType]['terms'];

        $startTime = new \DateTime($start);
        $endTime = new \DateTime($end);
        return $startTime <= $currentTime && $currentTime <= $endTime;
    }
}

class Candidate
{
    private $coupons;
    private $numberOfUsedCoupons;
    private $discount;

    public function __construct(array $coupons)
    {
        $this->coupons = $coupons;
        $this->numberOfUsedCoupons = array_sum($this->coupons);
        $this->discount = null;
    }

    public function calculateDiscount($amount, CouponMaster $couponMaster)
    {
        $discounts = array_map(function($numberOfCoupon,$type) use ($amount, $couponMaster) {
            $discount = $couponMaster->getDiscount($type, $amount);
            return $discount * $numberOfCoupon;
        },$this->coupons, array_keys($this->coupons));

        $this->discount = array_sum($discounts);
        return $this->discount;
    }

    public function getCoupons()
    {
        return $this->coupons;
    }

    public function getDiscount()
    {
        return $this->discount;
    }

    public function getNumberOfUsedCoupons()
    {
        return $this->numberOfUsedCoupons;
    }

    public function compare(Candidate $otherCandidate)
    {
        if( $this->getDiscount() < $otherCandidate->getDiscount() )
        {
            return $otherCandidate;
        }

        if( $this->getDiscount() !== $otherCandidate->getDiscount() )
        {
            return $this;
        }

        if( $this->getNumberOfUsedCoupons() > $otherCandidate->getNumberOfUsedCoupons() )
        {
            return $otherCandidate;
        }
        return $this;
    }
}

class Filter
{

    public static function filterOutOfTermsCoupons(array $couponList, CouponMaster $couponMaster, $dateString)
    {
        $currentTime = null;
        if( !is_null($dateString) )
        {
            $currentTime = new \DateTime($dateString);
        }

        $validCoupons = array_filter($couponList, function($couponType) use($couponMaster, $currentTime){
            return $couponMaster->inAvailableTerm($couponType, $currentTime);
        });
        return $validCoupons;
    }

    /**
     * クーポン=>枚数 の形にした後、限度枚数を超えたものを切り捨てる
     * @param array $couponList
     * @param CouponMaster $couponMaster
     * @return array
     */
    public static function filterOutOfLimitCoupons(array $couponList, CouponMaster $couponMaster)
    {
        $typeToNumberOfCoupons = array_reduce($couponList, function($typeToNumberOfCoupons, $couponType){
            if( array_key_exists($couponType, $typeToNumberOfCoupons) )
            {
                $typeToNumberOfCoupons[$couponType]++;
            }
            else
            {
                $typeToNumberOfCoupons[$couponType] = 1;
            }
            return $typeToNumberOfCoupons;
        }, []);

        array_walk($typeToNumberOfCoupons, function(&$numberOfCoupon, $type) use ($couponMaster) {
            $maxCouponCount = $couponMaster->getMaxNumberOfCoupon($type);
            $numberOfCoupon = min($maxCouponCount, $numberOfCoupon);
        });
        return $typeToNumberOfCoupons;
    }
}

/**
 * 1. 入力をフィルタ
 * 2. 最適解の候補を上げる
 * 3. 候補の中から最適解を選ぶ
 *
 * @param $amount
 * @param array $myCouponList
 * @param $dateString
 * @return array
 */
function selectOptimalCoupons($amount, array $myCouponList, $dateString)
{
    $couponMaster       = new CouponMaster();
    $availableCoupons   = filterCoupons($myCouponList, $couponMaster, $dateString);
    $candidates         = divideIntoCandidates($availableCoupons, $couponMaster);
    $optimalCandidate   = selectOptimalCandidate($candidates, $amount, $couponMaster);
    return $optimalCandidate->getCoupons();
}

/**
 * 入力されたクーポンのうち利用できないものをフィルタリングする
 *
 * @param array $couponList
 * @param CouponMaster $couponMaster
 * @param String $dateString 時刻を指定する場合に利用
 * @return array クーポンの種類 => 枚数 の形
 */
function filterCoupons(array $couponList, CouponMaster $couponMaster, $dateString = null)
{

    $validCoupons = Filter::filterOutOfTermsCoupons($couponList, $couponMaster, $dateString);
    $typeToNumberOfCoupons = Filter::filterOutOfLimitCoupons($validCoupons, $couponMaster);

    return $typeToNumberOfCoupons;
}

function divideIntoCandidates(array $couponTypeToNumberOfCoupons, CouponMaster $couponMaster)
{
    $candidates = [];
    foreach($couponTypeToNumberOfCoupons as $type => $couponTypes)
    {

        $sameTimeUsesCoupons = $couponMaster->getSameTimeUseCoupons($type);
        if( empty($sameTimeUsesCoupons) )
            continue;

        $coupons[$type] = $couponTypeToNumberOfCoupons[$type];

        foreach($sameTimeUsesCoupons as $type)
        {
            if( array_key_exists($type, $couponTypeToNumberOfCoupons) )
                $coupons[$type] = $couponTypeToNumberOfCoupons[$type];
        }
        $maxNumCombination = count($coupons);
        for($i=2;$i<=$maxNumCombination;$i++)
        {
            foreach(array_chunk($coupons, $i, true) as $c)
            {
                $candidates[] = new Candidate($c);
            }
        }
    }
    foreach(array_chunk($couponTypeToNumberOfCoupons, 1, true) as $coupons)
    {
        $candidates[] = new Candidate($coupons);
    }
    return $candidates;
}

/**
 * @param array[Candidate] $candidates
 * @param $amount
 * @param CouponMaster $couponMaster
 * @return null
 */
function selectOptimalCandidate(array $candidates, $amount, CouponMaster $couponMaster)
{
    $optimalCandidate = null;
    foreach($candidates as $candidate)
    {
        $candidate->calculateDiscount($amount, $couponMaster);
        if( is_null($optimalCandidate) )
        {
            $optimalCandidate = $candidate;
        }
        $optimalCandidate = $optimalCandidate->compare($candidate);
    }
    return $optimalCandidate;
}

<?php
require_once "level3.php";

class Test_Level3 extends PHPUnit_Framework_TestCase
{
    /**
     * @dataProvider data_与えられた仕様
     */
    public function test_selectOptimalCouponsが仕様通り返すこと(
        $amount,
        $myCouponList,
        $dateString,
        $expected
    )
    {
        $actual = selectOptimalCoupons($amount,$myCouponList, $dateString);
        $this->assertEquals($expected, $actual);
    }

    public function data_与えられた仕様()
    {
        return [
            /* $amount, $myCouponList, $dateString, $expected */
            [
                2200,
                ['500','500','700','1000'],
                '2014-07-31',
                [
                    '500' => 1,
                ],
            ],
            [
                2200,
                ['500','500','700','700','1000'],
                '2014-08-01',
                [
                    '700' => 1,
                ]
            ],
            [
                2200,
                ['500','500','700','1000','1000'],
                '2014-08-25',
                [
                    '700' => 1,
                    '1000' => 1,
                ]
            ],
            [
                2200,
                ['500','500','700','1000'],
                '2014-09-01',
                [
                    '500' => 1,
                ]
            ],
            [
                12000,
                ['1000','10%'],
                '2014-08-27',
                [
                    '10%' => 1,
                ],
            ],

        ];
    }
}