Смятане на варианти - оптимизация на бройките ползван материал.
- Автор uphero
- Начална дата
Края на седмицата излизам отпуска. Може да ти ударя рамо.
Супер, благодаря.
Ще пиша.
При моите тестове работи, направо го изтествай сам:
PHP:
<?php
class CutInfo
{
private int $numberOfCuts;
private int $cutSize;
private int $requiredPipes;
private int $remainingSize;
public function __construct(int $currentPipeSize, int $requiredPipeSize, int $quantity)
{
$numberOfCuts = $currentPipeSize / $requiredPipeSize;
$cutSize = ceil($currentPipeSize / $numberOfCuts);
$requiredPipes = ceil($quantity / (int) $numberOfCuts);
$remainingSize = $currentPipeSize - ($requiredPipes > 1 ? $cutSize : $cutSize * $quantity);
$this->numberOfCuts = $numberOfCuts;
$this->cutSize = $cutSize;
$this->requiredPipes = $requiredPipes;
$this->remainingSize = $remainingSize;
}
public function getNumberOfCuts(): int
{
return $this->numberOfCuts;
}
public function getCutSize(): int
{
return $this->cutSize;
}
public function getRequiredPipes(): int
{
return $this->requiredPipes;
}
public function getRemainingSize(): int
{
return $this->remainingSize;
}
}
class Calculator
{
private int $defaultPipeSize;
private int $requiredPipes = 0;
private array $pipeCuts = [];
public function __construct(int $defaultPipeSize)
{
$this->defaultPipeSize = $defaultPipeSize;
}
public function addPipe(int $quantity, int $pipeSize): void
{
if ($pipeSize === $this->defaultPipeSize) {
$cutInfo = new CutInfo($this->defaultPipeSize, $pipeSize, $quantity);
$this->requiredPipes += $cutInfo->getRequiredPipes();
} else {
$this->calculateRequiredPipes($quantity, $pipeSize);
}
}
private function calculateRequiredPipes(int $quantity, int $pipeSize): void
{
if (count($this->pipeCuts) > 0) {
if (array_key_exists($pipeSize, $this->pipeCuts)) {
$availableCuts = $this->pipeCuts[$pipeSize];
if ($availableCuts > $quantity) {
$this->pipeCuts[$pipeSize] -= $quantity;
} elseif ($availableCuts === $quantity) {
unset($this->pipeCuts[$pipeSize]);
} else {
unset($this->pipeCuts[$pipeSize]);
$this->calculateRequiredPipes($quantity - $availableCuts, $pipeSize);
}
} else {
$smallestFittingSize = array_keys($this->pipeCuts)[0];
foreach ($this->pipeCuts as $pipesSize => $pipesQuantity) {
if ($pipesSize < $pipeSize) {
continue;
}
if ($pipesSize < $smallestFittingSize) {
$smallestFittingSize = $pipesSize;
}
}
if ($smallestFittingSize > 0) {
$availablePipes = $this->pipeCuts[$smallestFittingSize];
$cutInfo = new CutInfo($smallestFittingSize, $pipeSize, $quantity);
$requiredPipes = $cutInfo->getRequiredPipes();
$newSize = $cutInfo->getRemainingSize();
if ($availablePipes > $requiredPipes) {
$this->pipeCuts[$smallestFittingSize] -= $requiredPipes;
} elseif ($availablePipes === $requiredPipes) {
unset($this->pipeCuts[$smallestFittingSize]);
} else {
unset($this->pipeCuts[$smallestFittingSize]);
$this->calculateRequiredPipes($requiredPipes - $availablePipes, $pipeSize);
}
if ($newSize > 0) {
$this->pipeCuts[$newSize] = ($this->pipeCuts[$newSize] ?? 0) + $cutInfo->getRequiredPipes();
}
} else {
$cutInfo = new CutInfo($this->defaultPipeSize, $pipeSize, $quantity);
$this->requiredPipes += $cutInfo->getRequiredPipes();
}
}
} else {
$cutInfo = new CutInfo($this->defaultPipeSize, $pipeSize, $quantity);
$requiredPipes = $cutInfo->getRequiredPipes();
$this->requiredPipes += $requiredPipes;
$cutSizeLeft = $cutInfo->getRemainingSize();
$this->pipeCuts[$cutSizeLeft] = $requiredPipes;
}
}
public function showStorageSummary(): void
{
echo "$this->requiredPipes x {$this->defaultPipeSize}mm pipes required\n";
echo "========== REMAINING PIPE CUTS ==========\n";
foreach ($this->pipeCuts as $pipeSize => $quantity) {
echo "$quantity x {$pipeSize}mm\n";
}
echo "=========================================\n";
}
}
// Example
$storage = new Calculator(6000);
$storage->addPipe(20, 5000);
$storage->addPipe(4, 1000);
$storage->addPipe(2, 100);
$storage->addPipe(4, 200);
$storage->addPipe(3, 150);
$storage->showStorageSummary();Има ситуации, в които $numberOfCuts ще ти върне нулева (или около нулата стойност) и ще се издъни на $requiredPipes калкулацията, защото кастваш към int.
Тествай на @anonimen стойностите:
PHP:
$storage = new Calculator(10000);
$storage->addPipe(1, 6000);
$storage->addPipe(1, 5000);
$storage->addPipe(1, 3000);
$storage->addPipe(3, 2000);
$storage->showStorageSummary();Това е, понеже ме е домързяло да напиша няколко if-а и е попаднал размер, който няма как да покрие изискванията. Замени частта с foreach-а в Calculator с това:
Ето го преправен класа:
PHP:
<?php
//...
$smallestFittingSize = null;
foreach ($this->pipeCuts as $pipesSize => $pipesQuantity) {
if ($pipesSize < $pipeSize) {
continue;
}
if ($smallestFittingSize == null) {
if ($pipesSize > $pipeSize) {
$smallestFittingSize = $pipesSize;
}
} else {
if ($pipesSize < $smallestFittingSize) {
$smallestFittingSize = $pipesSize;
}
}
}
if ($smallestFittingSize !== null) {
//...Ето го преправен класа:
PHP:
<?php
class Calculator
{
private int $defaultPipeSize;
private int $requiredPipes = 0;
private array $pipeCuts = [];
public function __construct(int $defaultPipeSize)
{
$this->defaultPipeSize = $defaultPipeSize;
}
public function addPipe(int $quantity, int $pipeSize): void
{
if ($pipeSize === $this->defaultPipeSize) {
$cutInfo = new CutInfo($this->defaultPipeSize, $pipeSize, $quantity);
$this->requiredPipes += $cutInfo->getRequiredPipes();
} else {
$this->calculateRequiredPipes($quantity, $pipeSize);
}
}
private function calculateRequiredPipes(int $quantity, int $pipeSize): void
{
if (count($this->pipeCuts) > 0) {
if (array_key_exists($pipeSize, $this->pipeCuts)) {
$availableCuts = $this->pipeCuts[$pipeSize];
if ($availableCuts > $quantity) {
$this->pipeCuts[$pipeSize] -= $quantity;
} elseif ($availableCuts === $quantity) {
unset($this->pipeCuts[$pipeSize]);
} else {
unset($this->pipeCuts[$pipeSize]);
$this->calculateRequiredPipes($quantity - $availableCuts, $pipeSize);
}
} else {
$smallestFittingSize = null;
foreach (array_keys($this->pipeCuts) as $foundPipeSize) {
if ($foundPipeSize < $pipeSize) {
continue;
}
if ($smallestFittingSize == null) {
if ($foundPipeSize > $pipeSize) {
$smallestFittingSize = $foundPipeSize;
}
} else {
if ($foundPipeSize < $smallestFittingSize) {
$smallestFittingSize = $foundPipeSize;
}
}
}
if ($smallestFittingSize !== null) {
$availablePipes = $this->pipeCuts[$smallestFittingSize];
$cutInfo = new CutInfo($smallestFittingSize, $pipeSize, $quantity);
$requiredPipes = $cutInfo->getRequiredPipes();
$newSize = $cutInfo->getRemainingSize();
if ($availablePipes > $requiredPipes) {
$this->pipeCuts[$smallestFittingSize] -= $requiredPipes;
} elseif ($availablePipes === $requiredPipes) {
unset($this->pipeCuts[$smallestFittingSize]);
} else {
unset($this->pipeCuts[$smallestFittingSize]);
$this->calculateRequiredPipes($requiredPipes - $availablePipes, $pipeSize);
}
if ($newSize > 0) {
$this->pipeCuts[$newSize] = ($this->pipeCuts[$newSize] ?? 0) + $cutInfo->getRequiredPipes();
}
} else {
$cutInfo = new CutInfo($this->defaultPipeSize, $pipeSize, $quantity);
$this->requiredPipes += $cutInfo->getRequiredPipes();
}
}
} else {
$cutInfo = new CutInfo($this->defaultPipeSize, $pipeSize, $quantity);
$requiredPipes = $cutInfo->getRequiredPipes();
$this->requiredPipes += $requiredPipes;
$cutSizeLeft = $cutInfo->getRemainingSize();
$this->pipeCuts[$cutSizeLeft] = $requiredPipes;
}
}
public function showStorageSummary(): void
{
echo "$this->requiredPipes x {$this->defaultPipeSize}mm pipes required\n";
echo "========== REMAINING PIPE CUTS ==========\n";
foreach ($this->pipeCuts as $pipeSize => $quantity) {
echo "$quantity x {$pipeSize}mm\n";
}
echo "=========================================\n";
}
}Сега остатъците ти излизат грешно. Изчислява 3 тръби (което по принцип е грешно, защото размерите се събират и в 2) и връща, че има остатък 1 тръба от 1000мм, което грешно. Би трябвало да са ти останали някъде 10000мм, дали цяла тръба (което в случая няма как да е) или в няколко по-малки.
PHP:
<?php
define('PIPE_LENGTH_MM', 6000);
$demand = [
5000 => 20,
1000 => 4,
100 => 1,
];
print_r(calculatePipes($demand));
function calculatePipes(array $demand)
{
if (empty($demand)) return 0;
$usedPipes = 0;
$leftovers = [];
foreach ($demand as $requiredLength => $total) {
for ($i = 0; $i < $total; $i++) {
[$pipeLength, $isNew] = findPipe($requiredLength, $leftovers);
$usedPipes += (int) $isNew;
$remainingLength = $pipeLength - $requiredLength;
if ($remainingLength > 0) {
$leftovers[] = $remainingLength;
}
}
}
return ['used pipes' => $usedPipes, 'leftovers' => array_count_values($leftovers)];
}
function findPipe(int $requiredLength, array &$leftovers)
{
sort($leftovers);
$pipe = [PIPE_LENGTH_MM, true];
for ($i = 0; $i < sizeof($leftovers); $i++) {
$leftoverPipeLength = $leftovers[$i];
if ($leftoverPipeLength >= $requiredLength) {
$pipe = [$leftoverPipeLength, false];
array_splice($leftovers, $i, 1);
break;
}
}
return $pipe;
}Опростен вариант. Тези дни ще си поиграя малко повече да се опитам да докарам перфектен резултат и да покрия ситуации като случая, който анонимен даде.
Както каза и @pix3l ще помогне да дадеш няколко тестови случаи - лесни и сложни - да имам няколко теста.
Бах го, чувствам се като истински психопат, дебъгвам на бая градус...
Ся, 3 тръби изчислява, понеже в условието нямаше изискване за събиране и заваряване на остатъци.
Тука някъде не е изключено да изгърми със синтактична грешка, тествам от браузър на телефон с някакъв online php интерпретатор
Ако пак нещо не работи, ще го гледам след наколко дни, като изляза от реанимация, лека
Ся, 3 тръби изчислява, понеже в условието нямаше изискване за събиране и заваряване на остатъци.
Тука някъде не е изключено да изгърми със синтактична грешка, тествам от браузър на телефон с някакъв online php интерпретатор
Ако пак нещо не работи, ще го гледам след наколко дни, като изляза от реанимация, лека
PHP:
<?php
class CutInfo
{
private int $numberOfCuts;
private int $cutSize;
private int $requiredPipes;
private int $remainingSize;
public function __construct(int $currentPipeSize, int $requiredPipeSize, int $quantity)
{
$numberOfCuts = $currentPipeSize / $requiredPipeSize;
$cutSize = ceil($currentPipeSize / $numberOfCuts);
$requiredPipes = ceil($quantity / (int)$numberOfCuts);
$remainingSize = $currentPipeSize - ($requiredPipes > 1 ? $cutSize * (int)$numberOfCuts : $cutSize * $quantity);
$this->numberOfCuts = $numberOfCuts;
$this->cutSize = $cutSize;
$this->requiredPipes = $requiredPipes;
$this->remainingSize = $remainingSize;
}
public function getNumberOfCuts(): int
{
return $this->numberOfCuts;
}
public function getCutSize(): int
{
return $this->cutSize;
}
public function getRequiredPipes(): int
{
return $this->requiredPipes;
}
public function getRemainingSize(): int
{
return $this->remainingSize;
}
}
class Calculator
{
private int $defaultPipeSize;
private int $requiredPipes = 0;
private array $pipeDemands = [];
private array $pipeCuts = [];
public function __construct(int $defaultPipeSize)
{
$this->defaultPipeSize = $defaultPipeSize;
}
public function addPipe(int $quantity, int $pipeSize): void
{
if ($pipeSize === $this->defaultPipeSize) {
$cutInfo = new CutInfo($this->defaultPipeSize, $pipeSize, $quantity);
$this->requiredPipes += $cutInfo->getRequiredPipes();
} else {
$this->pipeDemands[$pipeSize] = ($this->pipeDemands[$pipeSize] ?? 0) + $quantity;
}
}
private function calculateRequiredPipes(int $quantity, int $pipeSize): void
{
if (count($this->pipeCuts) > 0) {
if (array_key_exists($pipeSize, $this->pipeCuts)) {
$availableCuts = $this->pipeCuts[$pipeSize];
if ($availableCuts > $quantity) {
$this->pipeCuts[$pipeSize] -= $quantity;
} elseif ($availableCuts === $quantity) {
unset($this->pipeCuts[$pipeSize]);
} else {
unset($this->pipeCuts[$pipeSize]);
$this->calculateRequiredPipes($quantity - $availableCuts, $pipeSize);
}
} else {
$smallestFittingSize = null;
foreach (array_keys($this->pipeCuts) as $foundPipeSize) {
if ($foundPipeSize < $pipeSize) {
continue;
}
if ($smallestFittingSize == null) {
if ($foundPipeSize > $pipeSize) {
$smallestFittingSize = $foundPipeSize;
}
} else {
if ($foundPipeSize <= $smallestFittingSize) {
$smallestFittingSize = $foundPipeSize;
}
}
}
if ($smallestFittingSize !== null) {
$availablePipes = $this->pipeCuts[$smallestFittingSize];
$cutInfo = new CutInfo($smallestFittingSize, $pipeSize, $quantity);
$requiredPipes = $cutInfo->getRequiredPipes();
$newSize = $cutInfo->getRemainingSize();
if ($newSize > 0) {
$quantity = $availablePipes < $requiredPipes
? $requiredPipes - $availablePipes
: $requiredPipes;
$this->pipeCuts[$newSize] = ($this->pipeCuts[$newSize] ?? 0) + $quantity;
}
if ($availablePipes > $requiredPipes) {
$this->pipeCuts[$smallestFittingSize] -= $requiredPipes;
} elseif ($availablePipes === $requiredPipes) {
unset($this->pipeCuts[$smallestFittingSize]);
} else {
unset($this->pipeCuts[$smallestFittingSize]);
$this->calculateRequiredPipes($requiredPipes - $availablePipes, $pipeSize);
}
} else {
$cutInfo = new CutInfo($this->defaultPipeSize, $pipeSize, $quantity);
$newSize = $cutInfo->getRemainingSize();
$this->requiredPipes += $cutInfo->getRequiredPipes();
$this->pipeCuts[$newSize] = ($this->pipeCuts[$newSize] ?? 0) + $cutInfo->getRequiredPipes();
}
}
} else {
$cutInfo = new CutInfo($this->defaultPipeSize, $pipeSize, $quantity);
$requiredPipes = $cutInfo->getRequiredPipes();
$this->requiredPipes += $requiredPipes;
$cutSizeLeft = $cutInfo->getRemainingSize();
$this->pipeCuts[$cutSizeLeft] = $requiredPipes;
}
}
public function showStorageSummary(): void
{
foreach ($this->pipeDemands as $size => $quantity) {
$this->calculateRequiredPipes($quantity, $size);
}
echo "$this->requiredPipes x {$this->defaultPipeSize}mm pipes required\n";
echo "========== REMAINING PIPE CUTS ==========\n";
foreach ($this->pipeCuts as $pipeSize => $quantity) {
echo "$quantity x {$pipeSize}mm\n";
}
echo "=========================================\n";
}
}
$storage = new Calculator(10000);
$storage->addPipe(1, 6000);
$storage->addPipe(1, 5000);
$storage->addPipe(1, 3000);
$storage->addPipe(3, 2000);
$storage->showStorageSummary();
Последно редактирано:
При 6,5,3,2,2,2 не ти трябват заварки. Реално се побират в две тръби, ако ги групираш като 6,2,2 и 5,3,2.
Но, защо имаш толкова много изчисления? Наивен вариант се постига доста по-просто. Пренаписах моя вариант в ООП вариант.
Като изключим хелпър класовете, логиката е съвсем проста.
Все още не съм седнал като хората да видя да дооправя логиката.
PHP:
<?php
class Logger
{
public static function log($msg = "", array $context = [], bool $prettyPrint = false): void
{
$jsonFlags = $prettyPrint ? JSON_PRETTY_PRINT : JSON_ERROR_NONE;
$context = !empty($context)
? json_encode($context, $jsonFlags)
: null;
printf("%s %s\n", $msg, $context);
}
}
class PipeDemandInfo
{
private int $quantity;
private int $length;
public function __construct(int $length, int $quantity)
{
if ($length <= 0) {
throw new InvalidArgumentException("Length must be greater than zero.");
}
if ($quantity <= 0) {
throw new InvalidArgumentException("Quantity must be greater than zero.");
}
$this->length = $length;
$this->quantity = $quantity;
}
public function getQuantity(): int
{
return $this->quantity;
}
public function getLength(): int
{
return $this->length;
}
}
class PipeDemandCalculator
{
private int $usedPipes = 0;
private int $defaultPipeLength;
/** @var PipeDemandInfo[] */
private array $pipesDemand = [];
/** @var int[] */
private array $leftovers = [];
public function __construct(int $defaultPipeLength)
{
$this->defaultPipeLength = $defaultPipeLength;
}
public function displaySummary(): void
{
Logger::log("========= Summary =========");
Logger::log(
context: [
'used pipes' => $this->usedPipes,
'leftovers' => array_count_values($this->leftovers),
],
prettyPrint: true
);
}
public function addPipeDemand(int $quantity, int $length): void
{
if ($length > $this->defaultPipeLength) {
throw new InvalidArgumentException(
sprintf("\$length must be less than or equal to %d.", $this->defaultPipeLength)
);
}
$this->pipesDemand[] = new PipeDemandInfo($length, $quantity);
}
public function calculate(): void
{
// always start with the longest pipes
usort($this->pipesDemand, fn(PipeDemandInfo $a, PipeDemandInfo $b) => $b->getLength() - $a->getLength());
foreach ($this->pipesDemand as $demandInfo) {
$this->calculateDemand($demandInfo);
}
}
private function calculateDemand(PipeDemandInfo $pipe): void
{
for ($i = 0; $i < $pipe->getQuantity(); $i++) {
$pipeLength = $this->findLeftoverPipe($pipe->getLength());
if ($pipeLength === null) {
$pipeLength = $this->defaultPipeLength;
$this->usedPipes++;
}
$remainingLength = $pipeLength - $pipe->getLength();
if ($remainingLength > 0) {
$this->leftovers[] = $remainingLength;
}
}
}
private function findLeftoverPipe(int $requiredLength): ?int
{
// always start from the shortest
sort($this->leftovers);
Logger::log(context: ['leftovers' => $this->leftovers]);
for ($i = 0; $i < sizeof($this->leftovers); $i++) {
$leftoverLength = $this->leftovers[$i];
if ($leftoverLength < $requiredLength)
continue;
array_splice($this->leftovers, $i, 1);
return $leftoverLength;
}
return null;
}
}
$calculator = new PipeDemandCalculator(6000);
$calculator->addPipeDemand(1, 100);
$calculator->addPipeDemand(20, 5000);
$calculator->addPipeDemand(4, 1000);
$calculator->calculate();
$calculator->displaySummary();При 6, 5, 3, 2, 2, 2, когато трябва да отрежеш 3, имаш избор дали да отрежеш от 5 или от 4. За да направиш най-оптималния избор, трябва да прегледаш следващите тръби в demand-а... което няма да е лесна задача, ако входа е прекалено голям. Аз просто започвам от най-късите изрезки. Като гледам, някои изчисления наистина са ненужни, най-вероятно съм пробвал различни варианти и не съм разчистил накрая.
Edit:
Понякога се чудя на себе си, защо толкова си усложнявам живота, като тръгвам да действам, без да помисля. Цялата работа се свежда до една проста сметка...
Edit:
Понякога се чудя на себе си, защо толкова си усложнявам живота, като тръгвам да действам, без да помисля. Цялата работа се свежда до една проста сметка...
PHP:
<?php
function calculateRequiredPipes(array $demand, int $pipeLength): array
{
$demandSum = array_sum($demand);
$remainingCut = $demandSum % $pipeLength;
$requiredPipes = $demandSum / $pipeLength;
if ($remainingCut > 0) {
$requiredPipes++;
}
return [
"requiredPipes" => (int) $requiredPipes,
"remainingLength" => $remainingCut > 0 ? $pipeLength - $remainingCut : 0,
];
}
$pipeLength = 10000;
$demand = [6000, 5000, 3000, 2000, 2000, 2000, 150];
$result = calculateRequiredPipes($demand, $pipeLength);
$requiredPipes = $result['requiredPipes'];
$remainingLength = $result['remainingLength'];
echo 'Required pipes: ' . $requiredPipes . PHP_EOL;
echo 'Remaining length: ' . $remainingLength. PHP_EOL;
Последно редактирано:
Просто изчисляване не винаги работи, а и няма как да знаеш точно какви изрезки са останали така, в случай, че реално искаме да знаем тази информация.
Като цяло крайния резултат може да е много различен според зависи последователността на тръбите. Един и същи деманд вкаран в различна последователност ще даде различен резултат.
В моя случай винаги започвам от най-дългите, но пък пробвам първо с най-късите от изрезките.
Трябва да се извъртят всички комбинации от деманда срещу изрезките. При големи входове, това ще е бавно.
Като цяло крайния резултат може да е много различен според зависи последователността на тръбите. Един и същи деманд вкаран в различна последователност ще даде различен резултат.
В моя случай винаги започвам от най-дългите, но пък пробвам първо с най-късите от изрезките.
Трябва да се извъртят всички комбинации от деманда срещу изрезките. При големи входове, това ще е бавно.
Ами вземи например оригиналния пример: 20х5000, 4х1000 и 1х100, и размер на тръбата 6000.
PHP Sandbox - Execute PHP code online through your browser
Run PHP code in your browser online with this tool in 400+ PHP versions
onlinephp.io
Получаваш 18 тръби и остатък 3900, което не е вярно. Само 20-те тръби по 5000 ще заемат 20 тръби.
Изглежда вече смята правилно. Имам странното чувство, че все пак ще има някакви едж кейсове, но не мога да намеря такива за сега. Ако някой намери да споделя.
Малко се престарах с хелпърите, но ми е по-лесно и изчистено така. Лог левела е зададен на Info. Който иска да проследи малко повече да го промени на Debug.
@uphero надявам се да ти свърши работа.
Малко се престарах с хелпърите, но ми е по-лесно и изчистено така. Лог левела е зададен на Info. Който иска да проследи малко повече да го промени на Debug.
@uphero надявам се да ти свърши работа.
PHP:
<?php
enum LogLevel: int
{
case Debug = 0;
case Info = 1;
}
class Logger
{
private function __construct()
{
}
public static function create(): Logger
{
return new Logger;
}
public function debug($msg = "", array $context = [], bool $prettyPrint = false): void
{
$this->log(LogLevel::Debug, $msg, $context, $prettyPrint);
}
public function info($msg = "", array $context = [], bool $prettyPrint = false): void
{
$this->log(LogLevel::Info, $msg, $context, $prettyPrint);
}
private function log(LogLevel $logLevel, $msg = "", array $context = [], bool $prettyPrint = false): void
{
if ($logLevel->value < LOG_LEVEL->value) return;
$jsonFlags = $prettyPrint ? JSON_PRETTY_PRINT : JSON_ERROR_NONE;
$context = !empty($context)
? json_encode($context, $jsonFlags)
: null;
printf("%s %s\n", $msg, $context);
}
}
class PipeDemandInfo
{
private int $quantity;
private int $length;
public function __construct(int $length, int $quantity)
{
if ($length <= 0) {
throw new InvalidArgumentException("Length must be greater than zero.");
}
if ($quantity <= 0) {
throw new InvalidArgumentException("Quantity must be greater than zero.");
}
$this->length = $length;
$this->quantity = $quantity;
}
public function getQuantity(): int
{
return $this->quantity;
}
public function getLength(): int
{
return $this->length;
}
}
class PipeDemandCalculator
{
private int $usedPipes = 0;
private int $defaultPipeLength;
/** @var PipeDemandInfo[] */
private array $pipesDemand = [];
/** @var int[] */
private array $leftovers = [];
private Logger $logger;
public function __construct(int $defaultPipeLength)
{
$this->defaultPipeLength = $defaultPipeLength;
$this->logger = Logger::create();
}
public function displaySummary(): void
{
$this->logger->info("========= Summary =========");
$this->logger->info(sprintf("> Pipe length: %dmm", $this->defaultPipeLength));
$this->logger->info("> Demands:");
foreach ($this->pipesDemand as $pipeDemandInfo) {
$this->logger->info(sprintf(" * %d x %dmm", $pipeDemandInfo->getQuantity(), $pipeDemandInfo->getLength()));
}
$this->logger->info("> Result:");
$this->logger->info(sprintf(" * Total pipes used: %d", $this->usedPipes));
$this->logger->info(sprintf(" > Leftover cuts: %d", sizeof($this->leftovers)));
foreach (array_count_values($this->leftovers) as $length => $quantity) {
$this->logger->info(sprintf(" * %d x %dmm", $quantity, $length));
}
}
public function addPipeDemand(int $quantity, int $length): void
{
if ($length > $this->defaultPipeLength) {
throw new InvalidArgumentException(
sprintf("\$length must be less than or equal to %d.", $this->defaultPipeLength)
);
}
$this->pipesDemand[] = new PipeDemandInfo($length, $quantity);
}
public function calculate(): void
{
// always start with the longest pipes
usort($this->pipesDemand, fn(PipeDemandInfo $a, PipeDemandInfo $b) => $b->getLength() - $a->getLength());
foreach ($this->pipesDemand as $demandInfo) {
$this->logger->debug("Demanded length", [$demandInfo->getLength()]);
$this->calculateDemand($demandInfo);
}
}
private function calculateDemand(PipeDemandInfo $pipeDemandInfo): void
{
for ($i = 0; $i < $pipeDemandInfo->getQuantity(); $i++) {
$pipeLength = $this->findLeftoverPipe($pipeDemandInfo->getLength());
if ($pipeLength === null) {
$pipeLength = $this->defaultPipeLength;
$this->usedPipes++;
}
$remainingLength = $pipeLength - $pipeDemandInfo->getLength();
if ($remainingLength > 0) {
$this->leftovers[] = $remainingLength;
}
}
}
private function findLeftoverPipe(int $requiredLength): ?int
{
// always start from the shortest
sort($this->leftovers);
$this->logger->debug(context: ['leftovers' => $this->leftovers]);
$smallestDemandedPipe = $this->pipesDemand[sizeof($this->pipesDemand) - 1];
$totalLeftovers = sizeof($this->leftovers);
for ($i = 0; $i < $totalLeftovers; $i++) {
$leftoverLength = $this->leftovers[$i];
$logContext = ['leftover length' => $leftoverLength, 'required length' => $requiredLength];
if ($leftoverLength < $requiredLength) {
$this->logger->debug('Leftover length is smaller than the required. Skip to next...', $logContext);
continue;
}
$remainingLength = $leftoverLength - $requiredLength;
if ($remainingLength > 0 && $remainingLength < $smallestDemandedPipe->getLength() && $i < array_key_last($this->leftovers)) {
$this->logger->debug(
'Cutting from this leftover pipe leaves a cut smaller than the smallest demanded pipe. Skip, if not last iteration.',
array_merge($logContext, ['smallest demanded length' => $smallestDemandedPipe->getLength()])
);
continue;
}
array_splice($this->leftovers, $i, 1);
return $leftoverLength;
}
return null;
}
}
const LOG_LEVEL = LogLevel::Info;
$calculator = new PipeDemandCalculator(6000);
$calculator->addPipeDemand(4, 1000);
$calculator->addPipeDemand(20, 5000);
$calculator->addPipeDemand(1, 100);
$calculator->calculate();
$calculator->displaySummary();
Logger::create()->info();
$calculator = new PipeDemandCalculator(6000);
$calculator->addPipeDemand(20, 5000);
$calculator->addPipeDemand(4, 1500);
$calculator->addPipeDemand(12, 150);
$calculator->calculate();
$calculator->displaySummary();
Logger::create()->info("\n\n>>>>>>>> Hard to achieve cases below (@anonimen) <<<<<<<<\n");
$calculator = new PipeDemandCalculator(10000);
$calculator->addPipeDemand(1, 6000);
$calculator->addPipeDemand(1, 5000);
$calculator->addPipeDemand(1, 3000);
$calculator->addPipeDemand(3, 2000);
$calculator->calculate();
$calculator->displaySummary();
Logger::create()->info();
$calculator = new PipeDemandCalculator(20000);
$calculator->addPipeDemand(1, 12000);
$calculator->addPipeDemand(1, 10000);
$calculator->addPipeDemand(1, 6000);
$calculator->addPipeDemand(3, 4000);
$calculator->calculate();
$calculator->displaySummary();
Последно редактирано: