Я работаю над Advent of Code, чтобы практиковать TDD и изучать PHPSpec. Я застрял в 17-й день, который, по сути, представляет собой головоломку для смены монет.
Эльфы снова купили слишком много eggnog — на этот раз 150 литров. Чтобы поместить все это в ваш холодильник, вам нужно переместить его в меньшие контейнеры. Вы проводите инвентаризацию вместимости имеющихся контейнеров.
Например, предположим, у вас есть контейнеры объемом 20, 15, 10, 5 и 5 литров. Если вам нужно хранить 25 литров, есть четыре способа сделать это:
- 15 и 10
- 20 и 5 (первые 5)
- 20 и 5 (вторая 5)
- 15, 5 и 5
Полностью заполняя все контейнеры, сколько различных комбинаций контейнеров может вмещать все 150 литров eggnog?
Вот мой код Я написал тест, используя примеры выше. combinations
метод должен вернуться 4
согласно примеру, но возвращает 3. Похоже, он не в состоянии справиться с тем фактом, что имеется более одного контейнера объемом 5 литров.
Любые предложения, пожалуйста?
<?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;
});
}
}
Используйте индексы массива доступных контейнеров в качестве значений комбинации.
Других решений пока нет …