Compares and finds the cheapest options for online shopping (prices, shipping, vouchers).

OnlineShopper

<?php

// Online - Shops
// --------------
//
// NOTE:
//	- Shipping costs conditions must be valid PHP expressions.
//	- Prices must be integers with the decimals included, so 5.00 becomes 500.
//	- The shipping cost conditions have to be ordered from lowest to greatest, otherwise computation will be wrong.
//
$shops = [
	'ro' => [
		'rosebikes.de', [
			'< 10000'	=> 495,
			'>= 10000'	=> 0
		]
	],
	'br' => [
		'bruegelmann.de', [
			'< 2500'	=> 799,
			'>= 2500'	=> 599,
			'>= 5000'	=> 0
		]
	],
	'cy' => [
		'cycling24.de', [
			'< 7500'	=> 300,
			'>= 7500'	=> 0
		]
	]
];


// Shop - Items
// ----------------
//
// NOTE:
//	- Prices must be integers with the decimals included, so 5.00 becomes 500.
//
$items = [
	['SHIMANO DEORE XT BR-T780 HR', 'br', 2790],
	['SHIMANO DEORE XT BR-T780 VR', 'br', 2590],
	['SHIMANO DEORE XT BR-T780 HR', 'ro', 2150],
	['SHIMANO DEORE XT BR-T780 VR', 'ro', 2150],
	['SHIMANO DEORE XT BL-T780 BREMSHEBEL SET', 'br', 4990],
	['SHIMANO DEORE XT BL-T780 BREMSHEBEL SET', 'ro', 3300],
	['SHIMANO TOURNEY TX RD-TX800 SCHALTWERK 7/8-FACH', 'br', 1190],
	['SHIMANO TOURNEY TX RD-TX800 SCHALTWERK 7/8-FACH', 'br', 1095],
	['Shimano CN-HG40 Kette 7/8-fach', 'br', 990],
	['Shimano CN-HG40 Kette 7/8-fach', 'cy', 820]
];

// Shop - Items
// ----------------
//
// NOTE:
//	- Prices must be integers with the decimals included, so 5.00 becomes 500.
//	- Only the most valuable voucher will be used. There is no support for multiple vouchers.
//
$vouchers = [
	'br' => [
		'>9900' => 1000
	],
	'ro' => [
		'>5000' => 1000
	]
];

$onlineShopper = new OnlineShopper($items, $shops, $vouchers);
$onlineShopper->printCheapestOption();


/**
 * Online Shopper
 * 
 * Finds the cheapest combination of different online shops for a list of shopping items.
 * 
 * @author Michael Haeuslmann <haeuslmann@gmail.com>
 * 
 * @todo Add color to highlight the cheapest option.
 * @todo Add support for optional items (e.g. I want one of the following different items, but I don't care which of them I get).
 */
class OnlineShopper
{
	const SHOP_NAME_KEY = 0;
	const SHOP_SHIPPING_KEY = 1;

	const ITEM_NAME_KEY = 0;
	const ITEM_SHOP_KEY = 1;
	const ITEM_PRICE_KEY = 2;

	/** @var array */
	private $items;
	
	/** @var array */
	private $shops;

	/** @var array */
	private $vouchers;

	public function __construct(array $items, array $shops, array $vouchers)
	{
		$this->items = $items;
		$this->shops = $shops;
		$this->vouchers = $vouchers;
	}

	/**
	 * @param array $items
	 * @param array $shops
	 * 
	 * @return void
	 */
	public function printCheapestOption()
	{
		$combinations = [];
		$item_count = $this->findNumberOfUniqueItems($this->items);

		foreach ($this->computeItemCombinations($this->items) as $combination) {
			// we need all items and no combinations with only one or other missing items
			if (count($combination) !== $item_count) {
				continue;
			}

			// combinations have the correct number of items, but still have bad combinations
			// e.g. without one of each item or combinations with duplicate items from different shops
			$uniqueItems = [];
			foreach ($combination as $shopItem) {
				if (in_array($shopItem[self::ITEM_NAME_KEY], $uniqueItems)) {
					// if this is a bad combination skip the whole combination = 2 levels of foreach
					continue 2;
				}
				$uniqueItems[] = $shopItem[self::ITEM_NAME_KEY];
			}
			$combinations[$this->generateCombinationUID($combination)] = $combination;
		}

		$shippingCostForCombinations = $this->computeShippingCostForCombinations($combinations);
		$vouchersForCombinations = $this->computeVouchersForCombinations($combinations);
		$totalsForCombinations = $this->computeTotalsForCombinations(
			$combinations,
			$shippingCostForCombinations,
			$vouchersForCombinations
		);
		
		arsort($totalsForCombinations);
		foreach ($totalsForCombinations as $combinationUID => $total) {
			echo PHP_EOL.str_repeat('=', 100).PHP_EOL."Combination: $combinationUID".PHP_EOL.str_repeat('-', 100).PHP_EOL;
			foreach ($combinations[$combinationUID] as $item) {
				printf(
					"\t%-50s --> %.2f (%s)".PHP_EOL,
					$item[self::ITEM_NAME_KEY],
					$item[self::ITEM_PRICE_KEY] / 100,
					$this->shops[$item[self::ITEM_SHOP_KEY]][self::SHOP_NAME_KEY]
				);
			}
			echo str_repeat('-', 100).PHP_EOL;
			printf(
				"\tTotal price for this combination: %.2f".PHP_EOL.
					"\t(incl. shipping cost of %.2f)".PHP_EOL.
					"\t(incl. vouchers worth %.2f)".PHP_EOL,
				$total / 100,
				$shippingCostForCombinations[$combinationUID] / 100,
				$vouchersForCombinations[$combinationUID] / 100
			);
			echo str_repeat('=', 100).PHP_EOL;
		}
	}

	/**
	 * @param array $combinations
	 * @param array $shippingCostForCombinations
	 * @param array $vouchersForCombinations
	 * 
	 * @return array
	 */
	private function computeTotalsForCombinations(
		array $combinations,
		array $shippingCostForCombinations,
		array $vouchersForCombinations
	)
	{
		$totalsForCombinations = [];
		foreach ($combinations as $combinationUID => $combination) {
			$total = 0;
			foreach ($combination as $shopItem) {
				$total += $shopItem[self::ITEM_PRICE_KEY];
			}

			$shippingCost = 0;
			if (isset($shippingCostForCombinations[$combinationUID])) {
				$shippingCost = $shippingCostForCombinations[$combinationUID];
			}

			$vouchers = 0;
			if (isset($vouchersForCombinations[$combinationUID])) {
				$vouchers = $vouchersForCombinations[$combinationUID];
			}
			
			$totalsForCombinations[$combinationUID] = $total + $shippingCost - $vouchers;
		}
		return $totalsForCombinations;
	}

	/**
	 * @param array $combinations
	 * 
	 * @return array
	 */
	function computeShippingCostForCombinations(array $combinations)
	{
		$shippingCostForCombinations = [];

		foreach ($combinations as $combinationUID => $combination) {
			// compute the total cost per shop
			$totalPerShop = [];
			foreach ($combination as $item) {
				if (!isset($totalPerShop[$item[self::ITEM_SHOP_KEY]])) {
					$totalPerShop[$item[self::ITEM_SHOP_KEY]] = 0;
				}
				$totalPerShop[$item[self::ITEM_SHOP_KEY]] += $item[self::ITEM_PRICE_KEY];
			}

			// compute shipping cost for each shop
			$finalShippingCost = 0;
			foreach ($totalPerShop as $shopId => $total) {
				// check which shipping conditions apply for the shop
				$cost_for_shop = 0;
				foreach ($this->shops[$shopId][self::SHOP_SHIPPING_KEY] as $condition => $cost) {
					if (eval("return $total $condition;")) {
						$cost_for_shop = $cost;
					}
				}
				$finalShippingCost += $cost_for_shop;
			}
			$shippingCostForCombinations[$combinationUID] = $finalShippingCost;
		}		

		return $shippingCostForCombinations;
	}

	/**
	 * @param array
	 * 
	 * @return array
	 */
	private function computeVouchersForCombinations(array $combinations)
	{
		$vouchersForCombinations = [];
		foreach ($combinations as $combinationUID => $combination) {
			$totalPerShop = [];
			foreach ($combination as $item) {
				if (!isset($totalPerShop[$item[self::ITEM_SHOP_KEY]])) {
					$totalPerShop[$item[self::ITEM_SHOP_KEY]] = 0;
				}
				$totalPerShop[$item[self::ITEM_SHOP_KEY]] += $item[self::ITEM_PRICE_KEY];
			}

			$totalVouchers = 0;
			foreach ($totalPerShop as $shopId => $total) {
				// only the last and highest Voucher will be used
				$finalVoucher = 0;
				foreach ($this->vouchers[$shopId] as $condition => $voucherValue) {
					if (eval("return $total $condition;")) {
						$finalVoucher = $voucherValue;
					}
				}
				$totalVouchers += $finalVoucher;
			}
			$vouchersForCombinations[$combinationUID] = $totalVouchers;
		}
		return $vouchersForCombinations;
	}

	/**
	 * Often many shops offer the same item, this method checks for
	 * a unique item count.
	 * 
	 * @param array
	 * 
	 * @return int
	 */
	private function findNumberOfUniqueItems(array $items)
	{
		$count = [];
		foreach ($items as $item) {
			$count[$item[self::ITEM_NAME_KEY]] = 0;
		}
		return count($count);
	}

	/**
	 * @param array
	 * 
	 * @return string
	 */
	private function generateCombinationUID(array $combination)
	{
		$uid = '';
		foreach ($combination as $shopItem) {
			$uid .= $shopItem[self::ITEM_NAME_KEY].$shopItem[self::ITEM_SHOP_KEY].$shopItem[self::ITEM_PRICE_KEY];
		}
		return sha1($uid);
	}

	/**
	 * Computes all possible combinations of an array.
	 * 
	 * Taken from: https://www.safaribooksonline.com/library/view/php-cookbook/1565926811/ch04s25.html
	 * 
	 * @param array
	 * 
	 * @return array
	 */
	private function computeItemCombinations($array)
	{
	    // initialize by adding the empty set
	    $results = array(array( ));

	    foreach ($array as $element) {
	        foreach ($results as $combination) {
	            array_push($results, array_merge(array($element), $combination));
	        }
	    }

	    return $results;
	}
}