I'm working on Advent of Code as a way to practice TDD and learn PHPSpec. I'm stuck on Day 17, which is essentially the coin change puzzle.
The elves bought too much eggnog again - 150 liters this time. To fit it all into your refrigerator, you'll need to move it into smaller containers. You take an inventory of the capacities of the available containers.
For example, suppose you have containers of size 20, 15, 10, 5, and 5 liters. If you need to store 25 liters, there are four ways to do it:
- 15 and 10
- 20 and 5 (the first 5)
- 20 and 5 (the second 5)
- 15, 5, and 5
Filling all containers entirely, how many different combinations of containers can exactly fit all 150 liters of eggnog?
Here's my code. I wrote a test using the examples above. The combinations method should return 4 per the example, but it returns 3. It doesn't seem to be able to handle the fact that there's more than one container of size 5 litres.
Any suggestions please?
<?php
namespace Day17;
class Calculator
{
private $containers = [];
public function combinations($total, array $containers)
{
$combinations = $this->iterate($total, $containers);
return count($combinations);
}
/**
* http://stackoverflow.com/questions/12837431/find-combinations-sum-of-elements-in-array-whose-sum-equal-to-a-given-number
*
* @param $array
* @param array $combinations
* @param array $temp
* @return array
*/
private function iterate($sum, $array, $combinations = [], $temp = [])
{
if (count($temp) && !in_array($temp, $combinations)) {
$combinations[] = $temp;
}
$count = count($array);
for ($i = 0; $i < $count; $i++) {
$copy = $array;
$elem = array_splice($copy, $i, 1);
if (count($copy) > 0) {
$add = array_merge($temp, array($elem[0]));
sort($add);
$combinations = $this->iterate($sum, $copy, $combinations, $add);
} else {
$add = array_merge($temp, array($elem[0]));
sort($add);
if (array_sum($combinations) == $sum) {
$combinations[] = $add;
}
}
}
return array_filter($combinations, function ($combination) use ($sum) {
return array_sum($combination) == $sum;
});
}
}
